如何调用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）。

最终的关卡信息不仅允许拓扑比较​​节点，而且包含其他有用的信息。例如：

• 与级别= 1的每个节点没有传入的连接（每个路径从它们中的一个开始）。所以任何DAG枚举都可以从它们开始。
• 最长路径（边缘的数目）不能长于（最大电平+ 1）

我假定对于某些人工数据（n个节点，每个节点（N）连接到节点（ 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

Answer 2

可能有人曾经想过这件事，但由于它的最坏情况是线性的，所以我很难指出你在一篇描述它的研究文章中。该算法解决的问题的名称是“增量拓扑排序”（或动态的，其中边缘删除也是可能的）。

Answer 3

考虑一个DAG，由两个长度为n的“并行”有向路径共享起始节点和最后一个节点组成。这里的图层编号比拓扑顺序更具限制性。在拓扑顺序中，可以将来自路径A的倒数第二个节点放在来自路径B的第二个节点之前，即使其层数较大。