プロパティのリストを表すDAGがあります。これらのプロパティは、a> bの場合、aがbに向けられたエッジを持つようなものです。これも推移的であるため、a>bおよびb>cの場合、aはcに向けられたエッジを持ちます。
ただし、aはbに向けられたエッジを持ち、bはcに向けられたエッジを持っているため、aからcへの向けられたエッジは不要です。これらの余分なエッジをすべて削除するにはどうすればよいですか？最小スパニングツリーアルゴリズムを使用することを考えていましたが、この状況で適用する適切なアルゴリズムが何であるかはよくわかりません。
各ノードとそのすべての出力エッジから深さ優先探索を実行し、特定のエッジを使用せずに特定のノードに到達できるかどうかを比較できると思いますが、これはひどく非効率的で遅いようです。
アルゴリズムが完了すると、出力はグラフと一致する順序ですべてのノードの線形リストになります。したがって、aにb、c、およびdへの3つの有向エッジがある場合。bとcもそれぞれdに向けられたエッジを持ち、出力はabcdまたはacbdのいずれかになります。
これは、推移還元問題と呼ばれます。正式には、最小限の (エッジが最も少ない) 有向グラフを探しています。その推移閉包は、入力グラフの推移閉包と同じです。(上記のウィキペディアのリンクの図は、それを明確にしています。)
どうやらこの問題を解決するための効率的なアルゴリズムが存在し、推移閉包 (つまり、推移リンクを削除する代わりに追加するというより一般的な逆問題) を生成するのと同じ時間がかかりますが、Aho, Garey による1972 年の論文へのリンクはUllman のダウンロードには 25 ドルかかります。
編集: Scott Cotton'sにはgraphlibJava 実装が含まれています! この Java ライブラリは非常によく構成されているようです。
実際、もう少し調べてみると、私が本当に求めているのはTopologicalsortだと思います。
これらが有向エッジを持つすでに n 個のノードである場合:
実際には、これは単なる順序付けアルゴリズムであり、全体の複雑さは o(0.5n^2) になるはずです。
1 つの問題は、1 つのノードの親ノードをループしたい場合、エッジをログに記録するためにより多くのメモリが必要になるため、子から親までトレースバックできることです。これは、M より大きい左のノードから 1 つのノードを選択するステップ 3 で改善できます。これは、どのノードが残っているかを知るためにノードのリストを保持する必要があることを意味します。