2

我对 VF2 算法实现有疑问。在许多情况下,一切似乎都运行良好,但是有一个问题我无法解决。

该算法不适用于下面的示例。在此示例中,我们正在比较两个相同的图表(见下图)。起始顶点为 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() 集是否有效,如下所述。对的幂集按字典顺序依次通过对的第一个值和第二个值进行迭代。

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

真的

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

于 2014-06-25T11:12:35.023 回答