問題タブ [subgraph]

私はこれをインターネット上で2、3日連続で検索してきましたが、今のところうまくいきません.

サブグラフ同型のライブラリと実装が世の中にたくさんあることは知っていますが、それらはすべて重み付けされていないグラフで機能します。たとえば、最も普及している 2 つのアルゴリズムは、VF2 と Uleman のアルゴリズムです。ここで、私の質問は次のとおりです。グラフ (G) とクエリ グラフ (g) が与えられた場合、g が G のサブグラフ (および同形) であるかどうかを確認できるメソッドはありますか? (以下はグラフのエッジ リスト表現であることに注意してください。)

この場合、g は部分グラフであり、G と同型ですが、次のようなものがあるとします。

g はもはや G のサブグラフではなく、同型ではありません。

UPDATE : どちらのグラフも無向です。

Webで調べたのですが、答えが見つかりませんでした。

NetworkX でノードをサブグラフとして定義できるかどうか知っていますか?

より良い質問をさせてください: 形状 (正方形、円、三角形など) であるいくつかのノードで構成されるグラフがあります。各ノードをサブグラフとして定義したいと思います。サブグラフのノードは、形状のコーナー ポイントである必要があります (三角形の場合: 3 つのコーナー ポイントがあるため、3 つのノードのサブグラフ)。もちろん、このサブグラフの作成は、開始グラフに影響を与えるべきではありません。

例：

• 「正方形」と「三角形」の 2 つのノードで構成される DiGraph。
• 「四角」と「三角」の境目
• ノード "square" は、4 つのノード (コーナー ポイントごとに 1 つ) を含むサブグラフです。
• これらのノードを接続するエッジ。
• ノード "triangle" は、3 つのノード (コーナー ポイントごとに 1 つ) を含むサブグラフです。
• これらのノードを接続するエッジ。

NetworkXでそれを行うことは可能ですか? ヘルプや提案は大歓迎です。

入力された大きなグラフからサブグラフ内の特定の数のノードを持つすべての可能な誘導サブグラフ (グラフレット) を抽出するために networkx を使用できるかどうか、またはジョブを実行できる別のパッケージがあるかどうか疑問に思っていますか? たとえば、ネットワークx隣接リスト形式で示されている大きなグラフがある場合、

グラフ G:

次のようになります

3 つのノードでグラフレットを抽出したい場合、アルゴリズムは私を返す必要があります

サブグラフ1:

[(1,2),(1,3)] subgraph2:

[(1,3),(1,7)] subgraph3:

[(3,4),(3,5),(4,5)]

subgraph4,subgraph5,subgraph6...

以下は、@Hooked が提案した質問のコードです。n=3 としましょう

出力は次のようになります

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

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

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

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

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