与えられた部分グラフGがigraphを使用して別のより大きなグラフG'の部分グラフであるかどうかを確認したいと思います。頂点またはエッジのいずれかのラベル付けが異なる場合、答えをFalseにしたいので、これはサブグラフ同型の問題ではないことに注意してください。両方のグラフに同じエッジラベルと頂点ラベルがあり、GがG'のサブグラフである場合にのみ、答えをTrueにします。igraphでこれを達成するにはどうすればよいですか？ありがとう。
質問する
1146 次
1 に答える
1
頂点/エッジ ラベルの意味がわかりませんが、igraph の VF2 サブ同形アルゴリズムは頂点/エッジの色をサポートしていることに注意してください。2 つの頂点またはエッジは、それらの色が同じである場合に一致できます。Python から igraph を使用している場合は、クラスのsubisomorphic_vf2メソッドを確認してください。GraphR から igraph を使用している場合は、graph.subisomorphic.vf2機能を確認してください。これらは両方ともigraph_subisomorphic_vf2、C 層の関数によってサポートされています。
更新:文字列は整数ではなくラベルとして使用されるため (VF2 同型アルゴリズムが期待する)、最初にそれらを整数インデックスに変換する必要があります。それ以外の場合、VF2 は必要なことを実行できるはずです。igraph の Python インターフェイスの例:
>>> g = Graph.Formula("A --> B --> C")
>>> g2 = Graph.Formula("A --> B")
>>> g.get_subisomorphisms_vf2(g2, color1=[0,1,2], color2=[0,1])
[[0, 1]]
>>> g.get_subisomorphisms_vf2(g2, color1=[0,1,2], color2=[0,2])
[]
于 2013-02-21T17:35:30.643 に答える