c++ - 傻瓜的迭代/动态拓扑排序

Question

我目前正在用 C++ 实现动态 DAG 图——它将通过 UI 显示给用户，节点/边的插入/删除将是常见操作。

图表的规模可能从非常小的规模到很大的规模不等——我的目标是支持数百万个节点。

因此，我正在寻找一种不会占用太多内存空间的最佳数据结构，同时也在寻找一种通过对拓扑排序的节点进行快速多线程迭代来快速插入/删除的方法 (因此多个节点可以并行执行)。

我还没有做任何分析，看看每次修改完成时重新计算完整图的拓扑排序的天真方法是否会削减它，但为了学习，我想我宁愿找到一种“更聪明”的方式。

我不知道如何处理图的多线程迭代，但一开始我偶然发现了一些与迭代/动态拓扑排序步骤相关的论文，问题是它们是有点太聪明了，我无法理解。它涉及理论/数学方面，缺乏可以帮助我理解正在发生的事情的具体实现示例。

这是此类论文的示例:A Labeling Approach to Incremental Cycle Detection .

由于缺少诸如“Iterative/Dynamic Topological Sorting for Dummies”之类的论文，是否有人对主题有任何提示？

Answer 1

动态拓扑排序算法(未测试)。

从拓扑排序的顶点序列开始。

1. 如果添加了一个没有边的顶点，则将其插入序列中的任意位置。
2. 如果删除了一条边或一个顶点，什么都不做。
3. 如果添加了前向边(从排序较低的顶点到排序较高的顶点)，什么也不做。
4. 如果添加新的向后边 A→B，则将 B 直接移到 A 之后。将 B 的出边标记为新边。根据需要重复第 3 点和第 4 点。 (如果可以移动多个顶点，则从排序最低的顶点开始；如果要移动的顶点有多个新的传入边，则从排序最高的顶点中选择一个)。如果在此过程中两次遇到相同的顶点，则报告一个循环。

算法本身不检测循环，但您可以将循环搜索限制在移动的顶点子集中。