問題タブ [subgraph]

グラフG =(V, E)、V に属するサブセットS 、およびSに属さないGのすべての頂点を含むサブセットS'が与えられた場合、 SとSのノード間のエッジの総数をカウントしたい' .

この問題を O(n^2) よりも複雑に解決できるアルゴリズム。

次のような 3 つのオブジェクト (Vertex、Edge、Graph) と 1 つの関数 (topo_sort) を持つ軽量のグラフ ライブラリを作成しました。

フラットな DAG を使用している場合、これは正常に機能しています。しかし、私が達成したいのは、私が描いたこの図でわかるように、メイン グラフにサブグラフ(またはネストされたグラフ)を追加することです。

これはまだ DAG なので、これで関数を実行すると、通常の topo_sort出力は次のようになります。

ただし、サブグラフの頂点が処理される前に、サブグラフが依存するすべての頂点が「処理」される場合、私の好ましい出力は次のようになります。

しかし、次のリソースは見つかりませんでした。

• サブグラフの一部としてグラフの頂点を「マーク」または「保存」する方法は?
• サブグラフの依存関係に基づいて頂点をソートする方法（上記の例のように）？
• サブグラフを独立したグラフとして取得または処理する方法は?

私の問題を十分に詳しく説明できればと思いますが、何か不足している場合はお知らせください。不足している部分について質問を広げます。

前もって感謝します！

編集：

私はこれ（Boost Graph Library、BGL）を見つけましたが、私が抱えている非常によく似た（またはまったく同じ？）問題を解決しているように見えますが、C ++に慣れていないので、それがどのようになっているのかわかりません動作していて、正確には何をしているのか--しかし、私はこれをここに入れました。多分誰かが私の質問に答えるのに役立つと思うでしょう..

編集2：

Pythonだけでなく疑似コードも受け付けます！もちろん、既存のpythonライブラリがこれを知っていれば興味がありますが、graph-toolsたとえば、私はそのような巨大なライブラリを使用したくありません.

perl スクリプトでドット ファイルを作成します。これは、同じノードを含むサブグラフです。例えば：

これらのサブグラフが同じ名前空間を使用していることはわかっているため、結果の出力は混乱しています。

各サブグラフで、以下のように、それらを一意にすることができbbますbb_1。

しかし、すべてのサブグラフのすべてのノードを一意にすることは困難です。

各サブグラフを「厳密」にするか、別の名前空間を使用する方法はありますか?

ここにグラフが表示されています。ノード B_0、B_1 がタイプ B、C_0、C_1 のノードに属しているノードにだけ。C_2、C_3 はタイプ C のノードに属します。ここで、この例で定義されているような基準を満たすことができる複数のサブグラフを見つけたいと思います -

基準 -

1. サブグラフには、タイプ A のノードが 1 つ、タイプ B のノードが 1 つ、タイプ C のノードが 1 つ、タイプ D のノードが 1 つ含まれます。
2. サブグラフには、タイプ A のノードからタイプ B の 1 つのノードへの 1 つのエッジ、タイプ B とタイプ C を接続する 1 つのエッジ、およびタイプ C とタイプ D を接続する 1 つのノードがあります。
3. サブグラフには、サブグラフからタイプ B ノードに向かうタイプ A からのエッジが 1 つ、タイプ B からタイプ C ノードの外側に向かうエッジが 1 つ、タイプ D からタイプ E の外側に向かうエッジが 1 つ含まれます。

今、この説明は次のように結果を与えるはずです-

1. サブグラフ :: A_0、B_0、C_1、D_1
2. サブグラフ :: A_0、B_0、C_0、D_0
3. サブグラフ :: A_0、B_1、C_2、D_2
4. サブグラフ :: A_0、B_1、C_3、D_3

そのようなサブグラフを見つけることができるアルゴリズムがあるかどうか知りたいですか? 可能な組み合わせをすべて作ってアルゴリズムを考えてみました。ただし、これはサブグラフのノード数に対して指数関数的になります。したがって、それを計算する効率的な方法が存在するかどうかを知りたいです。または、グラフ理論に同様の性質の問題が存在する場合は?

無向グラフがありますG。は頂点と辺の集合なのでG「データベース」として持っておきたい。

Hこれで、 のサブグラフであることが保証されGているクエリ グラフができました。Hのどの部分に対応するかをどのように把握できGますか?

Hこの質問は、ここにある既存のものとは異なりGます。

VF2 アルゴリズムの実装に問題があります。多くの場合、すべてが完全に機能しているように見えますが、解決できない問題があります。

以下の例では、アルゴリズムは機能しません。この例では、2 つの同一のグラフを比較しています (下の画像を参照)。開始頂点は 0 です。s0 内で計算されるセット P は、頂点のすべてのペアのパワーセットを格納します。

以下は、実装のベースとなった VF2 に関する出版物に含まれている疑似コードです。

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B51AD0DAEDF60D6C8AB589A39A570257?doi=10.1.1.101.5342&rep=rep1&type=pdf

http://www.icst.pku.edu.cn/intro/leizou/teaching/2012-autumn/papers/part2/VF2%20A%20%28sub%29Graph%20Isomorphism%20Algorithm%20For%20Matching%20Large%20Graphs. pdf

/* の右側のコメントは、コードの理解方法を説明しています。

以下で説明するように、 P() セットの作成が有効かどうかはわかりません。ペアのべき集合は、ペアの最初の値、次に 2 番目の値によって、辞書式順序で反復されます。

アルゴリズムが s4 に進むと、関数から戻るときに、適切な頂点の一致に関する情報が失われます。グラフが同型であっても、サブグラフ同型 ({(0,0),(1,1),(2,2),(5,3),(6,4)}) を検索することになります。

ここで何が間違っていますか？