给有其他限制条件的有向无环图添加一条边。

Question

4

我有一个DAG。我有一个操作，用于在两个节点之间添加边。

如果B可以从A到达，则B是A的父节点。如果B可以直接从A到达（不经过其他节点），则B是A的直接父节点。

该图的要求如下：

1.没有循环。 2.对于任何节点，都有一组直接父节点P [1]，P [2]，P [3]… P [i]不是P [j]的父节点，其中i和j都是任意整数。

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

例如，有3个节点

A，直接父节点：无 B，直接父节点：A C，直接父节点：A

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

C，直接父节点：A，B

但是A是B的父节点，不符合要求2，因此从C的直接父节点中删除A，并且我们有

C，直接父节点：B

目前这是我所做的：从A到B添加边缘（这个A成为B的父节点）

检查B是否是A的父节点。如果是，则不添加边缘。（这确保了没有循环）通过BFS检查A是否已经是B的父节点。如果是，则不添加边缘。查找A的父节点与B的直接父节点的交集。通过BFS查找A的每个父节点来完成此操作。从B的直接父节点中删除交集，并将A添加为B的直接父节点。

这很慢。它在5k节点级别崩溃（我希望它处理少于100k节点的任何图形），速度变得不可接受，添加节点边缘需要0.02秒。

我有一种感觉，步骤1和2可以使用其他算法在1步中完成。

我考虑使用拓扑排序，但必须遍历整个图形，这是我的步骤1和2的最坏情况。当添加新节点时，排序将被破坏。因此，我必须为插入运行拓扑排序，以便它不会产生任何好处。对于步骤3，必须找到A的所有父节点。该过程相当缓慢，因为平均而言，它要遍历图形的相当一部分。

如何使其更有效？

- Chao Xu

2个回答

0

不知道你的实现情况，但建议你添加索引。每行索引必须存储元父-元子对

元父 - 是链接中的父级：父级、父级的父级等

元子 - 是链接中的子级：子级、子级的子级等

因此，对于图A->B->C，存在以下索引： A-B、B-C、A-C 在B->C之间添加显式边会导致断言失败，因为这样的条目已经存在。因此，算法的复杂度从n^2降至ln(n)

- Dewfy

我认为维护这样一个“可达性缓存”的时间和空间成本实际上会使性能变得更糟。想想缓存中的条目数量。 - Wim Coenen

如果您遵循以下两种策略，就不会占用太多内存：（1）使用位对节点进行编码和Lempel Ziv压缩，这样最受欢迎的节点就具有最短的索引。(2)将节点索引连接成二进制字符串。因此，对于大约100k个节点的示例，您将消耗近300k的两倍内存。 - Dewfy

缓存中可能的条目数随n^2增加。对于100k个节点，缓存最多可以有50亿个条目（100,000^2个可能的配对，除以2，因为它是一个DAG）。你还坚信吗？ - Wim Coenen

但是您已经设置了限制（请参见您自己的＃2），这种类型的图形将近似于树。我的解决方案提供了非常接近300k的结果。请查看数据结构“trie”-A-B，A-C只会放置一次A。 - Dewfy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Wim Coenen · Accepted Answer

你的问题归结为“在DAG中插入边是否可以比O(v+e)更快？”根据要求(1)。要求(2)是一个更局部的约束条件，不需要检查整个图。

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

毫无疑问，有一些技巧可以提高预期性能，具体取决于您的DAG的属性以及它如何随时间变化。这似乎是一个活跃的研究课题。例如，我想对于某些图形，将节点聚类可能是有益的。然后，在聚类子DAG内插入边仅需要在聚类内进行检查。但是，您需要一个适当的聚类策略，并支持在添加节点等时廉价地更新聚类。