4

我有一个 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、直系父母：A
  • C、直系父母：A

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

  • C、直系父母：A、B

但是 A 是 B 的父级，不满足要求 2，因此 A 从 C 的直接父级中删除，我们有

  • C、直系父母：B

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

  1. 通过 BFS 检查 B 是否是 A 的父级。如果是这样，不要添加边缘。（这确保没有循环）
  2. 通过 BFS 检查 A 是否已经是 B 的父级。如果是这样，请不要添加边缘。
  3. 找到 A 的父级与 B 的直接父级的交集。这是通过通过 BFS 找到 A 的每个父级来完成的。从 B 的直接父级中删除交集，并将 A 添加为 B 的直接父级。（2 和 3 确保满足要求 2）

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

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

我曾想过使用拓扑排序，但它必须横穿整个图，这对于我的第 1 步和第 2 步来说是最坏的情况。添加新节点时，排序将被打乱。所以我每次插入都必须运行拓扑排序，所以它不会产生任何好处。对于第 3 步，必须找到 A 的整个父母集。这个过程相当缓慢，因为平均而言它横穿了图表的相当一部分。

我怎样才能使它更有效率？

4

2 回答 2

4

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

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

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

于 2009-08-12T13:25:54.157 回答
0

不知道您的实现，但建议您添加索引。每个行索引必须存储对 metaparent-metachild

metaparent - 是链接中的父级：父级、父级父级、...

metachid - 是链接中的孩子：孩子，孩子的孩子，...

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

于 2009-08-12T12:06:17.157 回答