首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >Dummies的迭代/动态拓扑排序

Dummies的迭代/动态拓扑排序
EN

Stack Overflow用户
提问于 2014-07-15 01:55:19
回答 2查看 1.8K关注 0票数 4

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

图形的大小可能从非常小的规模到大的规模--我的目标是支持数百万个节点。

因此,我正在寻找一种优化的数据结构,它不会占用内存中太多的空间,但也可以通过拓扑排序节点上的快速多线程迭代(因此多个节点可以并行执行)实现快速插入/删除。

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

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

下面是这样一篇论文的一个例子:增量周期检测的一种标号方法

由于缺乏诸如“Dummies的迭代/动态拓扑排序”这样的论文,是否有人对主题有任何提示?

EN

回答 2

Stack Overflow用户

发布于 2014-07-15 17:25:07

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

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

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

该算法本身并不检测循环,但是您可以将循环搜索限制在被移动的顶点的子集上。

票数 2
EN

Stack Overflow用户

发布于 2015-06-19 05:09:29

的确有关于动态拓扑的工作。

Pearce & Kelly http://homepages.ecs.vuw.ac.nz/~djp/dts.html有一个他们声称既简单又实用的算法。它们还提供了一个C++实现。通过介绍,他们讨论了更简单的变体。

下面是关于这个问题的一些后续工作,按时间顺序排列。后来的方法往往比以前的方法更复杂。即使没有,后来的论文可能会假设你已经读过之前的文章了。你显然是从这份名单上的最后一篇论文开始的,这篇论文可能已经跳入了深度。

  • http://www.cs.princeton.edu/~sssix/papers/dto-icalp08.pdf
  • http://dl.acm.org/citation.cfm?ID=1496890
  • http://dl.acm.org/citation.cfm?ID=2071382
  • http://arxiv.org/pdf/1310.8381.pdf (你在问题中提到的)
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/24748744

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档