is_isomorphic

is_isomorphic(G1, G2, node_match=None, edge_match=None)

如果图 G1 和 G2 同构，则返回 True，否则返回 False。

参数:

G1, G2: 图

两个图 G1 和 G2 必须是同一类型。

node_match可调用对象

一个函数，用于判断图 G1 中的节点 n1 和图 G2 中的节点 n2 在同构测试期间是否应被视为相等。如果未指定 node_match，则不考虑节点属性。

该函数将被调用，形式如下：

node_match(G1.nodes[n1], G2.nodes[n2]).

也就是说，该函数将接收 n1 和 n2 的节点属性字典作为输入。

edge_match可调用对象

一个函数，用于判断图 G1 中节点对 (u1, v1) 的边属性字典和图 G2 中节点对 (u2, v2) 的边属性字典在同构测试期间是否应被视为相等。如果未指定 edge_match，则不考虑边属性。

该函数将被调用，形式如下：

edge_match(G1[u1][v1], G2[u2][v2]).

也就是说，该函数将接收正在考虑的边的边属性字典。

另请参阅

numerical_node_match, numerical_edge_match, numerical_multiedge_match

categorical_node_match, categorical_edge_match, categorical_multiedge_match

注意

使用 vf2 算法 [1]。

参考文献

[1]

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

示例

>>> import networkx.algorithms.isomorphism as iso

对于有向图 G1 和 G2，使用‘weight’边属性（默认值：1）

>>> G1 = nx.DiGraph()
>>> G2 = nx.DiGraph()
>>> nx.add_path(G1, [1, 2, 3, 4], weight=1)
>>> nx.add_path(G2, [10, 20, 30, 40], weight=2)
>>> em = iso.numerical_edge_match("weight", 1)
>>> nx.is_isomorphic(G1, G2)  # no weights considered
True
>>> nx.is_isomorphic(G1, G2, edge_match=em)  # match weights
False

对于多重有向图 G1 和 G2，使用‘fill’节点属性（默认值：‘’）

>>> G1 = nx.MultiDiGraph()
>>> G2 = nx.MultiDiGraph()
>>> G1.add_nodes_from([1, 2, 3], fill="red")
>>> G2.add_nodes_from([10, 20, 30, 40], fill="red")
>>> nx.add_path(G1, [1, 2, 3, 4], weight=3, linewidth=2.5)
>>> nx.add_path(G2, [10, 20, 30, 40], weight=3)
>>> nm = iso.categorical_node_match("fill", "red")
>>> nx.is_isomorphic(G1, G2, node_match=nm)
True

对于多重有向图 G1 和 G2，使用‘weight’边属性（默认值：7）

>>> G1.add_edge(1, 2, weight=7)
1
>>> G2.add_edge(10, 20)
1
>>> em = iso.numerical_multiedge_match("weight", 7, rtol=1e-6)
>>> nx.is_isomorphic(G1, G2, edge_match=em)
True

对于多重图 G1 和 G2，使用默认值分别为 7 和 2.5 的‘weight’和‘linewidth’边属性。同时使用默认值为‘red’的‘fill’节点属性。

>>> em = iso.numerical_multiedge_match(["weight", "linewidth"], [7, 2.5])
>>> nm = iso.categorical_node_match("fill", "red")
>>> nx.is_isomorphic(G1, G2, edge_match=em, node_match=nm)
True