VF2 算法#

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

使用此模块最简单的接口是调用 is_isomorphic 函数。

引言#

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

匹配通过语法可行性来完成。也可以检查语义可行性。因此，可行性被定义为这两个函数的逻辑与（AND）。

要包含语义检查，应子类化 (Di)GraphMatcher 类，并重新定义 semantic_feasibility 函数。默认情况下，语义可行性函数始终返回 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 被称为图-子图同构（graph-subgraph isomorphism），当且仅当 M 是 G2 与 G1 的一个子图之间的同构。因此，说 G1 和 G2 是图-子图同构的，就是说 G1 的一个子图与 G2 同构。

其他文献使用短语“子图同构”（subgraph isomorphic），例如在“G1 没有与 G2 同构的子图”中。另一种用法是作为同构的副词。因此，说 G1 和 G2 是子图同构的，就是说 G1 的一个子图与 G2 同构。

最后，“子图”一词可以有多种含义。在此上下文中，“子图”始终指“节点诱导子图”（node-induced subgraph）。边缘诱导子图同构（Edge-induced subgraph isomorphisms）未直接支持，但应可通过使用 line_graph 来执行检查。对于非诱导的子图，更倾向于使用术语“单态同态”（monomorphism）而不是“同构”。

设 G = (N, E) 是一个图，其中节点集为 N，边集为 E。

如果 G' = (N', E') 是一个子图，则: N' 是 N 的子集，E' 是 E 的子集。
如果 G' = (N', E') 是一个节点诱导子图，则: N' 是 N 的子集，E' 是 E 中连接 N' 中节点的边的子集。
如果 G' = (N', E') 是一个边缘诱导子图，则: N' 是 N 中由 E' 中的边连接的节点子集，E' 是 E 的子集。
如果 G' = (N', E') 是一个单态同态，则: N' 是 N 的子集，E' 是 E 中连接 N' 中节点的边的集合的子集。

请注意，如果 G' 是 G 的节点诱导子图，那么它始终是 G 的子图单态同态，但反之不总是成立，因为单态同态可以具有更少的边。

参考文献#

[1] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento,: “大型图匹配的（子）图同构算法”，IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-1372, Oct., 2004. http://ieeexplore.ieee.org/iel5/34/29305/01323804.pdf
[2] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, “一种改进的: 大型图匹配算法”，第三届 IAPR-TC15 模式识别中基于图的表示研讨会，Cuen, pp. 149-159, 2001. https://www.researchgate.net/publication/200034365_An_Improved_Algorithm_for_Matching_Large_Graphs

另请参阅#

semantic_feasibility syntactic_feasibility

注意#

该实现支持有向图、无向图以及多重图。

通常，子图同构问题是 NP-完全的，而图同构问题很可能不是 NP-完全的（尽管尚不存在已知的多项式时间算法）。

图匹配器#

`GraphMatcher.__init__`(G1, G2[, node_match, ...])	初始化图匹配器。
`GraphMatcher.initialize`()	重新初始化算法的状态。
`GraphMatcher.is_isomorphic`()	如果 G1 和 G2 是同构图，则返回 True。
`GraphMatcher.subgraph_is_isomorphic`()	如果 `G1` 的子图与 `G2` 同构，则返回 `True`。
`GraphMatcher.subgraph_is_monomorphic`()	如果 `G1` 的子图与 `G2` 单态同态，则返回 `True`。
`GraphMatcher.isomorphisms_iter`()	生成 G1 和 G2 之间同构的生成器。
`GraphMatcher.subgraph_isomorphisms_iter`()	生成 `G1` 子图与 `G2` 之间同构的生成器。
`GraphMatcher.subgraph_monomorphisms_iter`()	生成 `G1` 子图与 `G2` 之间单态同态的生成器。
`GraphMatcher.candidate_pairs_iter`()	迭代器，用于遍历 G1 和 G2 中候选的节点对。
`GraphMatcher.match`()	扩展同构映射。
`GraphMatcher.semantic_feasibility`(G1_node, ...)	如果将 G1_node 映射到 G2_node 在语义上可行，则返回 True。
`GraphMatcher.syntactic_feasibility`(G1_node, ...)	如果添加 (G1_node, G2_node) 在语法上可行，则返回 True。

有向图匹配器#

`DiGraphMatcher.__init__`(G1, G2[, ...])	初始化图匹配器。
`DiGraphMatcher.initialize`()	重新初始化算法的状态。
`DiGraphMatcher.is_isomorphic`()	如果 G1 和 G2 是同构图，则返回 True。
`DiGraphMatcher.subgraph_is_isomorphic`()	如果 `G1` 的子图与 `G2` 同构，则返回 `True`。
`DiGraphMatcher.subgraph_is_monomorphic`()	如果 `G1` 的子图与 `G2` 单态同态，则返回 `True`。
`DiGraphMatcher.isomorphisms_iter`()	生成 G1 和 G2 之间同构的生成器。
`DiGraphMatcher.subgraph_isomorphisms_iter`()	生成 `G1` 子图与 `G2` 之间同构的生成器。
`DiGraphMatcher.subgraph_monomorphisms_iter`()	生成 `G1` 子图与 `G2` 之间单态同态的生成器。
`DiGraphMatcher.candidate_pairs_iter`()	迭代器，用于遍历 G1 和 G2 中候选的节点对。
`DiGraphMatcher.match`()	扩展同构映射。
`DiGraphMatcher.semantic_feasibility`(G1_node, ...)	如果将 G1_node 映射到 G2_node 在语义上可行，则返回 True。
`DiGraphMatcher.syntactic_feasibility`(...)	如果添加 (G1_node, G2_node) 在语法上可行，则返回 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)	返回一个用于通用属性的比较函数。