VF2 Algorithm#

VF2算法#

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

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

Introduction#

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

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

要包含语义检查，应子类化(Di)GraphMatcher类，并重新定义 semantic_feasibility 函数。默认情况下，语义可行性函数始终 返回 True 。这样做的效果是，在匹配G1和G2时不会考虑语义。

Examples#

假设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}

Subgraph Isomorphism#

图论文献对于上述陈述的含义可能含糊不清，我们希望现在澄清它。

在VF2文献中，映射 M 被称为图-子图同构当且仅当 M 是 G2 和 G1 的子图之间的同构。 因此，说 G1 和 G2 是图-子图同构就是说 G1 的一个子图与 G2 同构。

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

最后，“子图”这个词可以有多种含义。在这个上下文中，“子图”总是指“节点诱导子图”。边诱导子图同构不直接支持，但应该能够通过使用 line_graph 来执行检查。对于非诱导子图，术语“单态”比“同构”更受青睐。

设 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 的子图单态，但反之则不一定，因为单态可以有更少的边。

References#

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

“A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs”, 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, “An Improved

Algorithm for Matching Large Graphs”, 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen, pp. 149-159, 2001. https://www.researchgate.net/publication/200034365_An_Improved_Algorithm_For_Matching_Large_Graphs

See Also#

semantic_feasibility syntactic_feasibility

Notes#

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

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

Graph Matcher#

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, ...)

返回 True 如果添加 (G1_node, G2_node) 在语法上是可行的。

DiGraph Matcher#

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(...)

返回 True 如果添加 (G1_node, G2_node) 在语法上是可行的。

Match helpers#

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)

返回一个用于通用属性的比较函数。
On this page