algorithm - 这个DAG拓扑重组怎么调用呢？

Question

我对有向无环图 (DAG) 很感兴趣，在阅读维基百科上的拓扑排序后，我没有发现任何特别提及涉及层编号的方法(尽管层是在绘图中被广泛提及)。使用这种方法，图形在技术上不是拓扑排序的，但知道每个节点都包含正确的层数(级别)，我们总是可以判断一个特定节点是否比另一个拓扑“更大”。另一方面，只要我们没有有序列表，就无法在拓扑上枚举节点(尽管这可以通过比较节点级别的最终常规排序来完成)。

这种方法允许实现任意连接，同时保持级别信息的正确性。步骤可以是:

• 对于任何新添加的节点(没有任何连接)应用的级别是 1。
• 如果请求两个节点之间的连接(从 m 到 n)并且 n.level > m.level 那么它们只是简单地连接起来，不需要为其他节点修复级别。
• 如果对于请求的连接(从 m 到 n)n.level<=m.level 那么我们将 n.level 更改为 (m.level + 1) 并递归检查 n 的任何依赖项是否有类似的级别增加(或不增加)如果递归步骤上的级别兼容)。
• 如果我们保留递归输入的节点列表，那么我们可以检测到循环尝试并实现某种撤消操作(将所有受影响节点的级别返回到以前的值)

对于任何一组已知节点和它们之间的连接，我们只需添加所有应用 level=1 的节点，并尝试在它们之间应用所有已知连接(忽略和撤消 cicles)。

最终级别的信息不仅允许在拓扑上比较节点，还包含其他有用的信息。例如:

• level = 1 的每个节点都没有传入连接(每条路径都从其中一个开始)。所以任何 DAG 枚举都可以从它们开始。
• 最长路径(边数)不能长于(最大层数+1)

我想对于一些人工数据(n 个节点，每个 Node(n) 连接到 Node(n + 1))这个算法可能会非常慢。但是对于真实世界的数据，我尝试了它(维基百科类别 - 800,000 个节点 - 2,000,000 个连接)时间不错(5-10 分钟)并且级别和循环尝试的数量很低(369 个级别，1000 次循环尝试)

那么这种方法是新的还是众所周知的，只是没有广泛出现在维基百科和其他资源中？既然不是排序(技术上)，是不是应该叫数据重组？

Answer 1

有一些论文是关于逐步维护图中节点的拓扑顺序的，其中对您描述的算法进行了修改。

如果图形有 n 个节点和 m 条边，则每次插入一条边都会花费 O(m + n) 时间。论文问插入k条边需要多少时间？简单地说，O(k * (n + m))。但事实上，对于足够大的 k，您可以显示更好的上限 - 例如 O(k * sqrt(m + n))。

下面是一些链接，还有更多:

http://igitur-archive.library.uu.nl/math/2007-0725-201647/2005-011.pdf

http://arxiv.org/abs/0802.1059

http://www.siam.org/proceedings/soda/2009/SODA09_120_benderm.pdf