VF2算法#

图同构测试的VF2算法的实现。

使用此模块的最简单接口是调用networkx.is_Isomorphic（）。

介绍#

图匹配器和有向图匹配器负责以预定的方式匹配图或有向图。这通常意味着检查同构，尽管其他检查也是可能的。例如，可以检查一个图的子图是否与第二个图同构。

匹配是通过句法可行性来完成的。也可以检查语义的可行性。然后，可行性被定义为两个函数的逻辑与。

为了包括语义检查，应该对（di）graphmatcher类进行子类化，并且应该重新定义语义_可行性（）函数。默认情况下，语义可行性函数始终返回true。其结果是在g1和g2的匹配中不考虑语义。

实例#

假设g1和g2是同构图。验证如下：

>>> from networkx.algorithms import isomorphism
>>> G1 = nx.path_graph(4)
>>> G2 = nx.path_graph(4)
>>> GM = isomorphism.GraphMatcher(G1, G2)
>>> GM.is_isomorphic()
True

gm.mapping存储从g1到g2的同构映射。

>>> GM.mapping
{0: 0, 1: 1, 2: 2, 3: 3}

设G1和G2是同构的有向图。验证如下：

>>> G1 = nx.path_graph(4, create_using=nx.DiGraph())
>>> G2 = nx.path_graph(4, create_using=nx.DiGraph())
>>> DiGM = isomorphism.DiGraphMatcher(G1, G2)
>>> DiGM.is_isomorphic()
True

digm.mapping存储从g1到g2的同构映射。

>>> DiGM.mapping
{0: 0, 1: 1, 2: 2, 3: 3}

子图同构#

图论文献对上述表述的含义可能会模棱两可，我们现在试图澄清它。

在vf2文献中，映射m被称为图子图同构iff m是g2和g1子图之间的同构。因此，说g1和g2是图子图同构就是说g1的子图同构于g2。

其他文献使用短语“子图同构”，如“g1没有与g2同构的子图”。另一个用法是同构的in副词。因此，如果说g1和g2是同构的子图，就是说g1的子图是同构的g2。

最后，“子图”一词可以有多种含义。在此上下文中，“子图”始终表示“节点诱导子图”。不直接支持边诱导子图同构，但是应该能够使用nx.line_graph（）执行检查。对于未被诱导的子图，术语“单态”优于“同构”。

设g=（n，e）是一个具有一组节点n和一组边e的图。

如果g’=（n’，e’）是子图，则：

n'是n e的子集'是e的子集

如果g’=（n’，e’）是节点诱导的子图，则：

n'是n的子集'e'是n'中与e相关的节点中的边的子集

如果g'=（n'，e'）是边诱导子图，则：

n'是n中节点的子集，与e中的边相关，'e'是e的子集

如果g’=（n’，e’）是单态，则：

n'是n'的子集，e'是n'中e相关节点的边集的子集

注意，如果g'是g的节点诱导子图，则它始终是g的子图单态，但不总是相反，因为单态可以具有较少的边。

工具书类#

[1] Luigi P.Cordella，Pasquale Foggia，Carlo Sansone，Mario Vento，

“匹配大图的（子）图同构算法”，《IEEE模式分析与机器智能汇刊》，第26卷，第10期，第1367-1372页，2004年10月。http://ieeexplore.ieee.org/iel5/34/29305/01323804.pdf

[2] L.P.Cordella，P.Foggia，C.Sansone，M.Vento，“改进型

《匹配大图形的算法》，第三届IAPR-TC15模式识别中基于图形表示的研讨会，Cen，第149-159页，2001年。https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.5342

另请参阅#

语法可行性()、语义可行性()

笔记#

该实现处理有向图和无向图以及多图。

一般来说，子图同构问题是NP完全问题，而图同构问题很可能不是NP完全问题（尽管不存在多项式时间算法）。

图匹配器#

GraphMatcher.__init__(G1, G2[, node_match, ...])

初始化图形匹配器。

GraphMatcher.initialize()

重新初始化算法的状态。

GraphMatcher.is_isomorphic()

如果g1和g2是同构图，则返回true。

GraphMatcher.subgraph_is_isomorphic()

如果g1的子图与g2同构，则返回true。

GraphMatcher.isomorphisms_iter()

g1和g2之间的生成器过度同构。

GraphMatcher.subgraph_isomorphisms_iter()

g1和g2子图之间的同构上的生成器。

GraphMatcher.candidate_pairs_iter()

迭代器遍历g1和g2中的候选节点对。

GraphMatcher.match()

扩展同构映射。

GraphMatcher.semantic_feasibility(G1_node, ...)

如果将g1_节点映射到g2_节点在语义上可行，则返回true。

GraphMatcher.syntactic_feasibility(G1_node, ...)

如果添加（g1_节点、g2_节点）在语法上可行，则返回true。

有向图匹配器#

DiGraphMatcher.__init__(G1, G2[, ...])

初始化图形匹配器。

DiGraphMatcher.initialize()

重新初始化算法的状态。

DiGraphMatcher.is_isomorphic()

如果g1和g2是同构图，则返回true。

DiGraphMatcher.subgraph_is_isomorphic()

如果g1的子图与g2同构，则返回true。

DiGraphMatcher.isomorphisms_iter()

g1和g2之间的生成器过度同构。

DiGraphMatcher.subgraph_isomorphisms_iter()

g1和g2子图之间的同构上的生成器。

DiGraphMatcher.candidate_pairs_iter()

迭代器遍历g1和g2中的候选节点对。

DiGraphMatcher.match()

扩展同构映射。

DiGraphMatcher.semantic_feasibility(G1_node, ...)

如果将g1_节点映射到g2_节点在语义上可行，则返回true。

DiGraphMatcher.syntactic_feasibility(...)

如果添加（g1_节点、g2_节点）在语法上可行，则返回true。

比赛助手#

categorical_node_match(attr, default)

返回类别节点属性的比较函数。

categorical_edge_match(attr, default)

返回类别边缘属性的比较函数。

categorical_multiedge_match(attr, default)

返回类别边缘属性的比较函数。

numerical_node_match(attr, default[, rtol, atol])

返回数值节点属性的比较函数。

numerical_edge_match(attr, default[, rtol, atol])

返回数值边缘属性的比较函数。

numerical_multiedge_match(attr, default[, ...])

返回数值边缘属性的比较函数。

generic_node_match(attr, default, op)

返回泛型属性的比较函数。

generic_edge_match(attr, default, op)

返回泛型属性的比较函数。

generic_multiedge_match(attr, default, op)

返回泛型属性的比较函数。