DAG内の特定のノードのセットを通るすべてのパスを見つけるにはどうすればよいですか？

Question

アプリケーションのユーザーによって分類されたアイテムのリスト（下の青いノード）があります。カテゴリ自体をグループ化して分類できます。

結果の構造は、有向非巡回グラフ（DAG）として表すことができます。はグラフのトポロジの下部にあるシンクで、上部のカテゴリはソースです。一部のカテゴリは明確に定義されている場合がありますが、多くはユーザー定義になり、非常に乱雑になる可能性があります。

例：

_{（ソース： theuprightape.net ）}

その構造で、次の操作を実行します。

• 特定のノード（ヨーロッパのすべてのアイテム）の下にあるすべてのアイテム（シンク）を見つける
• n個のノードのセットのすべてを通過するすべてのパス（存在する場合）を検索します（すべてのアイテムがexample.comからSMTP経由で送信されます）
• すべてのノードの下にあるすべてのノードを検索します（交差点：ゴイッシュブラウンフード）

最初の方法は非常に単純です。ノードから開始し、すべての可能なパスを最後までたどり、そこでアイテムを収集します。しかし、より速いアプローチはありますか？すでに通過したノードを覚えておくことは、おそらく不必要な繰り返しを避けるのに役立ちますが、さらに最適化がありますか？

2番目の方法についてはどうすればよいですか？最初のステップは、セットの各ノードの高さを決定し、どのノードから開始するかを決定し、セットの残りを含むすべてのパスを見つけることです。しかし、これは最良の（または優れた）アプローチですか？

Wikipediaにリストされているグラフトラバーサルアルゴリズムはすべて、特定のノードまたは2つのノード間の最短またはその他の最も効果的なルート。私は両方とも私が望んでいるものではないと思いますか、またはこれが私の問題にどのように適用されるかを確認できませんでしたか？他にどこを読むべきですか？

Answer 1

私には、3つの質問すべてで基本的に同じ操作をしているように見えます。あなたは常に、「ノードYの下のすべてのXを検索します。ここで、XはタイプZです」。必要なのは、「すべてのノードをノードの下に配置する」ための一般的なメカニズム（Q3を解決）で、「nodetype = sink」の結果をフィルター処理できます（Q1を解決）。 Q2には、開始点（ノードセット）と終了点（開始点の下のシンク）があるため、ソリューションセットは、指定された開始ノードからシンクまでのすべてのパスになります。したがって、基本的にはツリーを使用することをお勧めします。基本的なツリートラバーサルアルゴリズムを使用することをお勧めします。

Answer 2

グラフが非周期的であるという事実にもかかわらず、引用する操作は、制御フローグラフ分析の同様の側面を思い出させます。 ドミナンスに基づいた豊富なアルゴリズムセットがあります。たとえば、3番目の操作は、コンピューティングの優位フロンティアを思い起こさせます。一時的に＆quot; entry＆quot;を導入すると、アルゴリズムが直接機能すると思います。および「終了」ノード。エントリノードは、「指定されたノードのセット」を接続します。出口ノードがシンクを接続します。

ロバートタージャンの基本アルゴリズムも参照してください。