重み付けされた 2 つの DAG (有向非巡回グラフ) があり、それらを 1 つにマージする必要があるため、トポロジー順序を取得できます (場合によっては 2 つ以上になる可能性があります)。問題は、グラフはそれぞれ非循環的ですが、一緒に循環を形成できることです。また、グラフが大きい (100k 以上のノード、500k 以上のエッジ)。グラフをマージする賢い方法はありますか? すべてのグラフを「一度に」トラバースするアルゴリズムも同様に優れています。
編集：
「マージ」とは、サイクルが作成されない場合、両方のグラフのすべてのエッジと頂点を組み合わせることを意味します (もちろん、重みを保持します)。エッジが既に存在する場合は、より大きな重みを使用したいと考えています。
アイデアは、2 つの非巡回グラフで開始すると、後で結果を単純に「修正」するよりも利点が得られるということです (これは、NP 困難なフィードバック アーク セットを見つけることを意味するため、それを避けたいと考えていました)。
ご提案いただきありがとうございます。
1 つの問題は、複数のソリューションが存在する可能性があることです。
たとえば、DAG {(a,b),(a,c)} および {(b,a),(b,c)} を考えてみましょう。これらを 2 つの異なる方法で「マージ」できます。
解の数は、2 つのグラフを結合するサイクルの数と組み合わせて増加するため、大きなグラフの場合、それらを「マージ」できる方法はおそらく膨大な数に上ります。
どの DAG が他の DAG よりも「優れている」かを判断するのに役立つ基準はありますか?
そうでない場合は、頂点が両方のグラフで同じであると仮定します。
V = V1 U V1
隣接リストがあると仮定しましょう。V1 と V2 のすべての頂点 v について、エッジがつながる頂点で隣接リストを並べ替えることができます ((頂点、重み) ペアの場合は、頂点で並べ替えます)。グラフが小さいため、これはそれほど高価でsummation degree(v)*log(degree(v))はないはずです。それほど悪くはないはずです。
この後、V1 と V2 のすべての頂点 v に対して繰り返し、V1 と V2 の v の隣接リストのマージ ソートを実行できます。これは、マージ ソートを使用して 2 つのソートされた配列の和集合を見つけることに似ていますが、両方で発生する要素を見つける場合にのみ、より大きなエッジを選択できます。