我在 VF2 算法实现方面遇到问题。在很多情况下,一切似乎都工作得很好,但是有一个问题我无法解决。
该算法不适用于以下示例。在此示例中,我们正在比较两个相同的图表(见下图)。起始顶点为 0。 在 s0 内部计算的集合 P 存储所有顶点对的幂集。
下面是有关 VF2 的出版物中包含的伪代码,我的实现基于该伪代码。
/*右侧的注释描述了我理解代码的方式:
我不确定创建 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)}) - 即使图是同构的。
我在这里做错了什么?
最佳答案
我认为要知道你的问题“我在这里做错了什么”,有必要在此处包含一些代码。您根据论文中提供的伪代码自己重新实现了代码?或者您在一些图形处理包的帮助下进行匹配?
对我来说,我没有时间深入研究细节,但我也使用图形,所以我尝试使用 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}
关于algorithm - VF2算法-实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19883567/