2

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 番目の値によって、辞書式順序で反復されます。

PROCEDURE Match(s)
  INPUT: an intermediate state s; the initial state s0 has M(s0)=empty
  OUTPUT: the mappings between the two graphs
  IF M(s) covers all the nodes of G2 THEN
    OUTPUT M(s)
  ELSE
    Compute the set P(s) of the pairs candidate for inclusion in M(s)
    /*by powerset of all succesors from already matched M(s) if not empty or
    /*predestors to already matched M(s) if not empty
    /*or all possible not included vertices in M(s)
    FOREACH (n, m)∈ P(s)
      IF F(s, n, m) THEN
    Compute the state s ́ obtained by adding (n, m) to M(s)
    /*add n to M1(s), exclude from T1(s)
    /*add m to M2(s), exclude from T2(s)
    /*M1(s) is now M1(s'), other structures belong to s' too
    CALL Match(s′)
      END IF
    END FOREACH
    Restore data structures
    /*Return all structures as from before foreach
  END IF
END PROCEDURE

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

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

4

1 に答える 1

2

「ここで何が間違っているのか」という質問を知るには、ここにコードの一部を含める必要があると思います。論文で提示された疑似コードに基づいて、自分でコードを再実装しましたか? または、いくつかのグラフ処理パッケージの助けを借りてマッチングを行っていましたか?

私には詳細を掘り下げる時間がありませんでしたが、グラフも扱っているので、networkx (Python パッケージ) と Boost 1.55.0 ライブラリ (グラフ用の非常に広範な C++ ライブラリ) を試してみました。あなたの例と、1000 個のノード、1500 個のエッジを持つグラフの別の例は、正しい一致を返します (グラフをそれ自体と一致させる簡単なケース)。

import networkx as nx
G1 = nx.Graph()
G2 = nx.Graph()

G1.clear()
G2.clear()

G1.add_nodes_from(range(0,7))
G2.add_nodes_from(range(0,7))
G1.add_edges_from([(0,1), (1,2), (2,3), (3,4), (2,5), (5,6)])
G2.add_edges_from([(0,1), (1,2), (2,3), (3,4), (2,5), (5,6)])

from networkx.algorithms import isomorphism
GM = isomorphism.GraphMatcher(G2,G1)
print GM.is_isomorphic()
GM.mapping

真実

Out[39]: {0: 0、1: 1、2: 2、3: 3、4: 4、5: 5、6: 6}

于 2014-06-25T11:12:35.023 に答える