合并两个DAG的高效算法 [英] Efficient algorithm for merging two DAGs
问题描述
我有两个加权DAG（有向无环图），需要将它们合并为一个，因此我可以进行拓扑排序（在某些情况下可以超过两个）。问题在于，每个图都是非循环的，但可以一起形成一个循环。而且，这些图很大（100k +个节点，500k +个边）。
是否有聪明的方法来合并图形？同样好的算法是一次遍历所有图形。
I have two weighted DAGs (directed acyclic graphs) and need to merge them into one, so I can get a topological ordering (it could be more than two in some cases). The problem is that the graphs are acyclic each, but can form a cycle together. Also, the graphs are large (100k+ nodes, 500k+ edges). Is there a clever way to merge the graphs? Equally good would be an algorithm to traverse all graphs "at once".
编辑：
按合并 我的意思是，如果两个图的所有边和顶点不创建循环，则将它们合并在一起（当然保留权重）。如果边缘已经存在，我想使用更大的权重。
By "merge" I mean combining all edges and vertices of both graphs together (preserving weights of course), if they do not create cycles. If an edge already exists I want to use the greater weight for it.
这个想法是，从两个非循环图开始应该比简单地固定结果更具优势。之后（这意味着要找到一个难点的NP反馈弧集，所以我想避免这种情况。）
The idea is that starting with two acyclic graphs should give an advantage over simply "fixing" the result afterwards (this would imply to find the feedback arc set which is NP hard so I wanted to avoid that).
谢谢您的建议。
推荐答案
一个问题是可能存在多个解决方案。
One issue is that there is may be more than one solution.
例如考虑DAG {（a，b），（a，c）}和{（b，a），（b，c）}。您可以通过两种不同的方式合并这些内容：
Consider for instance the DAGs {(a,b),(a,c)} and {(b,a),(b,c)}. You can "merge" these in two different ways:
- {（a，b），（a，c），（b，c ）}
- {（a，c），（b，a），（b，c）}
解决方案的数量与两个图的并集中的循环数成正比增长，因此对于您的大图，可能有很多方法可以合并它们。
The number of solutions grows combinatorially with the number of cycles in the union of the two graphs, so for your big graphs there is probably a huge number of ways you can "merge" them.
您是否有一个标准可以帮助您确定哪个DAG比另一个DAG更好？
Do you have a criterion which could help you decide which DAG is "better" than another?
这篇关于合并两个DAG的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
