指示されたグラフでの効率的な検索

Question

何百万もの頂点とエッジを備えた指示グラフがあります。一連の頂点が与えられます。それらが「start_points」と呼ばれていると仮定しましょう。 「end_points」と呼ばれる別の頂点セットも与えられます。問題は、どのend_pointsがどのstart_pointsから到達できるかを見つけることです。

これが例です：

START_POINTS: S1 S2 S3 S4 S5 S6 S7 ... 
END_POINTS  : E1 E2 E3 E4 E5 E6 E7 ... 

アルゴリズムは、次のことを伝えることができるはずです。

S1 can reach to E1, E2, E6
S2 can reach to E9, E10
S3 cannot reach any END_POINT
S4 can reach to .....
....

end_pointsの一部は、start_pointから到達しない場合があります。

さて、問題は次のとおりです。それを実装する最も効率的な方法は何ですか？

各start_pointから1つずつ開始して、深さfirst検索（またはBFSを使用して到達可能なend_pointsを見つけようとしました。ただし、start_pointsが非常に多いため、多くの時間がかかります（End_pointsもたくさんあります）。

start_pointsのトレースされたパスの間に大きなオーバーラップがあるため、検索を最適化できます。どのパスがどのend_pointsに到達できるかを覚えておく必要があります。これを達成するための最も効率的な方法は何ですか？これはよく知られている問題かもしれませんが、私はまだ解決策を見つけることができませんでした。

1月6日に編集：

HighBandWidthのアイデアを実装しようとしました（Keith Randallが提案したものと同様の方法で）：各ノードについて、このノードが開始ポイントまたはエンドポイントでない場合、すべての入力を出力に接続し、ノードを削除します。

foreach NODE in NODES
    Skip if NODE is START_POINT or END_POINT
    foreach OUTPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
    end
    foreach INPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
        foreach OUTPUT_NODE of NODE
            Connect INPUT_NODE to OUTPUT_NODE
        end
    end
    Remove NODE from NODES
end

これは非常に高速で始まり、主に残りのノードの入力/出力カウントが非常に大きくなり、ループのためにネストされているため、パフォーマンスを殺すためです。どのようにそれをより効率的にすることができるかという考えはありますか？

Answer 1

グラフをプルーズして、開始ノードまたはエンドノードに表示されないすべてのノードを取り除き、インバウンドノードからのエッジでそれらのアウトバウンドターゲットに置き換えます。それが完了したら、他のすべてのノード（開始または終了ノード）を通過し、これらのノードを削除せずに、インバウンドノードからアウトバウンドノードにエッジを追加します。いくつかのDjikstraのような反復では、スタートから終了エッジを残しておく必要があります。

Answer 2

これはやり過ぎかもしれませんが、あなたはチェックアウトしたいかもしれません ディクストラ. 。仮想ノードのルーティングテーブルを作成するとき、私は過去にそれを使用しました。この場合、すべてのノードの値は1になります。つまり、各ノードは同じトラベルワイズのコストです。

Answer 3

まず、実行します 強く接続されたコンポーネント アルゴリズム。次に、接続されたすべてのコンポーネントを単一のノードに縮小します。次に、aを実行します トポロジーの種 グラフの。次に、単一のパスで、グラフ内の各ノードに到達できるスタートノードを計算できます（各スタートノードsをセット{s}に初期化し、各ノードでトポロジ順に着信エッジの結合を実行します）。

答えは＃startノード *＃endノードと同じくらい大きく、大きくなる可能性があるという点で潜在的な問題があります。回答をより簡潔にする可能性があるため、シングルノードに収縮する大きなSCCがいくつかあることを願っています（同じSCCのすべての開始ノードが同じ場所に到達できるため、セットで1つの代表者のみを使用する必要があります）。