boost-graph - 特定の頂点のみを介して接続されている頂点のブースト グラフのトポロジカル ソート

Question

一連の依存関係を表す大きなグラフがあります。

• A -->B
• A -->C
• B -->F
• C -->G
• D -->E
• に --> に
• ファ→ハ
• ふ→い
• ち→か
• J -->K

B を開始ノードとして指定すると、結果は次のようになる必要があります: BFIHK

B から到達できないため、他のノードは必要ありません。

ユーザーはノードを指定できます。すべてのパスとそれらのパス内のノードを収集し、それらのノードのトポロジ ソートを出力する必要があります。

現在、私はこれを実装しています

1. 新しいグラフを作成する

2. 指定されたノードからすべての発信エッジを抽出します。

3. それらのエッジをグラフに追加します。これらのエッジからノードを取得し、それらを新しいグラフに追加します。

4. 手順 3 のノードごとに、(2) と (3) を繰り返します。

5. その新しいグラフでトポロジカル ソートを実行し、ノードの順序を取得します。

   これを行うための他のより良い方法、またはノードのサブセットのトポロジカルな並べ替えを見つけるための既知のアルゴリズムはありますか?

Answer 1

depth_first_visit() 関数と、boost が提供する訪問者パターンを調べます。訪問者パターンを使用すると、ツリーが検索されるときに頂点とエッジを調べることができます。depth_first_visit() 関数を使用すると、特定の頂点から DFS 検索を開始できます。