c# - 特定のプロパティによって分離されている有向グラフ内のサブグラフを見つける

Question

グラフ理論の語彙の知識が少ないことをお許しください。

問題を一般的な英単語でしか説明できません。誰かが私を正しい方向に向けたり、検索する用語を教えてくれるかもしれません。

この問題は、ビジュアル プログラミング言語の実装の一部として発生しました。頂点は関数/メソッドであり、エッジは関数間でデータを転送します。現在、次の問題があります。

Collection< TItem >型の頂点 A の出力をTItem型の頂点 B の入力に接続することができます。次に、 TItem型の頂点 B の出力を、Collection< TItem >型の入力頂点 C に出力します。これは、頂点 B の周りにforeach関数をラップして、B の関数を A からのコレクション内の各項目に適用し、新しい項目をコレクションとして C の入力に出力する必要があることをコンパイラに伝えます。したがって、A から B へのエッジは多対 1 接続で、B から C へは 1 対多です。

実際の問題は、1対多の接続で囲まれている/分離されている(有向)サブグラフを見つけるアルゴリズムは何ですか? コンパイラがこの特定のサブグラフの周りに foreach 関数をラップするように? この図で問題を視覚化しようとしました：

Answer 1

グラフにはそのようなサブグラフが複数存在する可能性があることに注意してください。

それぞれを見つけるには、グラフ内のすべてのノードにアクセスし、親/子を数えて、それが目的のセットのメンバーであるかどうかを判断し、マークされたすべてのノードをそれぞれのサブグラフまたはクリークに分離します。クリークを操作するための一般的な手順は、Wikipedia: The Clique Problemにあります。

Answer 2

次のアルゴリズムをお勧めします。

ステップ 1すべてのノードをウォークスルーします。青いノードが見つかった場合は、有向グラフで深さ優先検索を実行して、そこから到達可能な白いノードのセットを見つけます。DFS の実行中に青いノードを通過しないでください。ノードのセットとともに、DFS 中に検出した開始の青色ノードと発信の青色ノードを保存します。

複数の白いノードのセットと、着信および発信する青いノードに関する情報が得られます。

（ご了承ください、私のマウスの描画スキルは本当に悪いです）

ステップ 2ご覧のとおり、重複している可能性があります。これを解決するには、次の 2 つの可能性があります。

• 後でばらばらなセットのデータ構造を使用して、重複するセットをマージします。これにより、O(n² + m)の最悪のケースのランタイムが発生します。

• 標準の DFS アルゴリズムを変更して、オーバーラップを最初から作成しないようにします。以前に探索したセットのいずれかで既に見たノードに到達すると、それが検出されます。その後、サブグラフをさらに調査する必要はありませんが、現在調査されているセットと重複するセットが後でマージされることを記録します。その後、結合グラフで接続されたコンポーネントを見つけることができます。これにより、 O(n + m)ランタイムが得られ、はるかに優れています。

最終的には、白いノードとそれぞれの着信および発信の青いノードのばらばらなセットのコレクションになります。