我目前正在用C++实现动态DAG图-它将通过用户界面显示给用户,插入/删除节点/边将是常见的操作。
图形的大小可能从非常小的规模到大的规模--我的目标是支持数百万个节点。
因此,我正在寻找一种优化的数据结构,它不会占用内存中太多的空间,但也可以通过拓扑排序节点上的快速多线程迭代(因此多个节点可以并行执行)实现快速插入/删除。
我还没有做过任何分析,看一种天真的方法在每次修改时重新计算一个拓扑类型的完整图是否会减少它,但为了学习,我想我宁愿找到一种“更聪明”的方法。
我不知道如何处理图的多线程迭代,但首先,我偶然发现了一些与迭代/动态拓扑排序步骤有关的论文,问题是它们对我来说有点太聪明了。它深入到理论/数学方面,缺乏具体的实现示例,可以帮助我理解正在发生的事情。
下面是这样一篇论文的一个例子:增量周期检测的一种标号方法。
由于缺乏诸如“Dummies的迭代/动态拓扑排序”这样的论文,是否有人对主题有任何提示?
发布于 2014-07-15 17:25:07
动态拓扑算法(未经测试)。
从拓扑排序的顶点序列开始。
该算法本身并不检测循环,但是您可以将循环搜索限制在被移动的顶点的子集上。
发布于 2015-06-19 05:09:29
的确有关于动态拓扑的工作。
Pearce & Kelly http://homepages.ecs.vuw.ac.nz/~djp/dts.html有一个他们声称既简单又实用的算法。它们还提供了一个C++实现。通过介绍,他们讨论了更简单的变体。
下面是关于这个问题的一些后续工作,按时间顺序排列。后来的方法往往比以前的方法更复杂。即使没有,后来的论文可能会假设你已经读过之前的文章了。你显然是从这份名单上的最后一篇论文开始的,这篇论文可能已经跳入了深度。
https://stackoverflow.com/questions/24748744
复制相似问题