在有其他限制的情况下向有向无环图添加边
我有一个 DAG。 我有这个操作来在两个节点之间添加一条边。
如果 A 可从 B 到达，则 B 是 A 的父级。 如果 A 可以从 B 到达，而无需通过另一个节点，则 B 是 A 的直接父节点。
该图的要求是：
- 无循环。
- 对于任何节点，都有一个直接父节点列表 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 的父级）
- 通过 BFS 检查 B 是否是 A 的父级。 如果是，则不要添加边。（这确保没有循环）
- 通过 BFS 检查 A 是否已经是 B 的父级。 如果是这样，请勿添加边缘。
- 找到 A 的父级与 B 的直接父级的交集。 这是通过 BFS 找到 A 的每个父级来完成的。 从 B 的直接父级中删除交集，并将 A 添加为 B 的直接父级。（2 和 3 确保它满足要求 2）
这很慢。 它在 5k 节点级别崩溃（我正在寻找它来处理任何少于 100k 节点的图），速度变得不可接受，添加节点边缘需要 0.02 秒。
我有一种感觉，第 1 步和第 2 步可以使用其他算法一步完成。
我想过使用拓扑排序，但它必须横穿整个图，这是我的步骤 1 和 2 中最糟糕的情况。 当添加新节点时，顺序将被打乱。 所以我每次插入时都必须运行拓扑排序，所以它不会产生任何好处。 对于第 3 步，必须找到 A 的整个父母集。 这个过程相当缓慢，因为平均来说它横穿了图表的相当一部分。
我怎样才能使这个更有效率？
I have a DAG. I have this operation to add a edge between two nodes.
If A is reachable from B, then B is A's parent. If A is reachable from B without going though another node, then B is A's direct parent.
Requirements for this graph are:
- No cycles.
- For any node, there is a list of direct parents P[1],P[2],P[3]... P[i] is not a parent of P[j] for any i and j.
If adding a edge, requirement 1 is not met, the edge is not constructed.
If adding a edge, requirement 2 is not met, the edge is constructed, but the direct parents will be modified in a way such that requirement 2 is met.
For example, there are 3 nodes
- A, direct parents: none
- B, direct parents: A
- C, direct parents: A
now, if I add a edge between B and C, we have
- C, direct parents: A,B
but A is a parent of B, doesn't meet requirement 2, thus A is removed from C's direct parent, and we have
- C, direct parents: B
Currently here is what I did:
Add edge from A to B (this A become B's parent)
- Check if B is A's parent by BFS. If so, do not add the edge.(this make sure there is no cycles)
- Check if A is already B's parent by BFS. If so, do not add the edge.
- Find the intersection of A's parent with B's direct parent. This is done by find every parent of A though BFS. Remove the intersection from B's direct parent, and add A as a direct parent of B.(2 and 3 make sure it meet requirement 2)
This is slow. It breaks down at 5k node level(I'm looking for this to handle any graph with less than 100k nodes), the speed become not acceptable, 0.02 second for adding a node edge.
I have a feeling step 1 and 2 can be done in 1 step with some other algorithm.
I thought of using topological ordering, but it have to transverse the entire graph, which is the worst case for my step 1&2. The ordering will be disrupted when the new node is added. so I have to run a topological ordering every time for a insert, so it doesn't create any benefit.
For step 3, the entire set of A's parents have to be found. The process is fairly slow, as on average it transverse a decent part of the graph.
How can I make this more efficient?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
不知道您的实现情况，但建议您添加索引。
每个行索引必须存储元父元-元子元
对元父元 - 是链接中的父元：父元，父元的父元，...
metachid - 链接中的子元：子元，子元的子元，...
所以对于图 A- >B->C 存在以下索引：
AB、BC、AC
在 B->C 之间添加显式边缘会导致断言，因为此类条目已经存在。 因此算法的复杂度从n^2降低到ln(n)
Don't know about your implmentation, but recommend you add indexing.
Each row index must store pairs metaparent-metachild
metaparent - is parent in link: parent, parent-of-parent,...
metachid - is child in link: child, child-of-child, ...
so for graph A->B->C exists following indexes:
A-B, B-C, A-C
Adding explicit edge between B->C causes an assertion since such entry already exist. So complexity of algorithm reduces from n^2 to ln(n)
您的问题归结为“在 DAG 中插入边可以比 O(v+e) 更快完成吗？” 按要求（1）。 要求 (2) 是一个更局部的约束，不需要检查整个图。
我认为答案是否定的：在最坏的情况下，你不能做得比
O(v+e)更好（其中v是节点/顶点的数量，< code>e 是边数）。毫无疑问，有一些技巧可以提高预期性能，具体取决于 DAG 的属性及其随时间的变化情况。 这似乎是一个活跃的研究课题。 例如，我想对于某些图来说，它可能对集群节点有益。 然后，在集群内插入边只需要在集群子 DAG 内进行检查。 但是，您需要一个适当的集群策略，并支持在添加节点等时以廉价的方式更新集群。
Your question comes down to "Can inserting edges in a DAG be done faster than O(v+e)?" as per requirement (1). Requirement (2) is a more local constraint that doesn't require checking the entire graph.
I think the answer is no: you can't do better than
O(v+e)in the worst case (wherevis the number of nodes/vertices andeis the number of edges).No doubt there are tricks to improve expected performance, depending on the properties of your DAG and how it changes over time. This appears to be an active research topic. For example, I imagine for some graphs it might be beneficial to cluster nodes. Inserting edges within a cluster then only requires checks within the cluster sub-DAG. But then you'd need a proper clustering strategy with support for cheaply updating the clustering when adding nodes, etc.