添加边缘以指导其他限制的无环图

Question

我有一个DAG。我有这个操作来在两个节点之间添加一条边。

如果A可以从B到达，那么B是A的父亲。如果A不需要经过另一个节点就可以从B到达，那么B就是A的直接父节点。

对于该曲线图的要求是：

1. 没有循环。
2. 对于任何节点，都有一个直接父节点P [1]，P [2]，P [3] ...的列表。对于任何i和j，P [i]不是P [j]的父亲。

如果添加一条边，不满足要求1，则不构造边。 如果添加边，则不满足要求2，则会构建边，但直接父项将以符合要求2的方式进行修改。

例如，有3个节点

• A，直接父母：无
• B，直接父母：甲
• C，直接父母：甲

现在，如果我在B和C之间加了一条边，我们有

• C，直系父母： A，B

但A是B的父，不符合要求2，因此，一个是由C的直接父删除，我们有

• C，直接家长：乙

目前这里是我做过什么： 从A添加边B（这方面的一个成为B的母公司）

1. 检查B是由BFS A的母公司。如果是这样，不要添加边缘（这确保没有周期）
2. 检查B是否已经是B的父母。如果是这样，请不要添加边缘。
3. 查找A的父母与B的直接父母的交集。这是通过找到B的每个父母来完成的。删除B的直接父母的交集，并添加A作为B的直接父代。（2和3确保它符合要求2）

这很慢。它在5k节点级别发生故障（我正在寻找这个处理任何小于100k节点的图形），速度变得不可接受，0.02秒用于添加节点边缘。

我有一种感觉，第1步和第2步可以用一些其他算法完成。

我想过使用拓扑排序，但它必须横跨整个图，这是我的第一步的最坏情况1 & 2.添加新节点时排序会中断。所以我必须每次为插入运行拓扑排序，所以它不会产生任何好处。 对于第3步，必须找到整个A的父母。这个过程相当缓慢，因为它平均横跨图的一个体面的部分。

我该如何提高效率？

Answer 1

您的问题归结为“可以在DAG中插入边缘的速度比O（v + e）快吗？”根据要求（1）。需求（2）是一个更局部的约束，不需要检查整个图。

我认为答案是否定的：在最坏的情况下（v是节点/顶点的数量，e是边数），你不可能比O(v+e)做得更好。

毫无疑问，有一些技巧可以提高预期的性能，具体取决于您的DAG的特性以及它随时间的变化。这似乎是一个活跃的研究课题。例如，我想象一下某些图表可能对群集节点有利。在群集内插入边缘只需要在群集子DAG内进行检查。但是，那么您需要一个适当的群集策略，支持在添加节点时便宜地更新群集等。

Answer 2

不知道你的暗示，但建议你添加索引。 每一行索引必须储存对metaparent-metachild

metaparent - 是链接父母：父母，父母的父母，...

metachid - 是孩子链接：儿童，儿童的孩子，...

因此对于图A-> B-> C存在以下索引： AB，BC，AC 在B-> C之间添加显式边将导致断言，因为此条目已存在。因此，算法的复杂度从n^2降低到ln（n）