is_isomorphic

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

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

Parameters:

G1, G2: 图

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

node_match可调用对象

一个函数，如果图 G1 中的节点 n1 和图 G2 中的节点 n2 在同构测试中应被视为相等，则返回 True。 如果未指定 node_match，则不考虑节点属性。

该函数将被调用如下：

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

即，函数将接收 n1 和 n2 的节点属性字典作为输入。

edge_match可调用对象

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

该函数将被调用如下：

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

即，函数将接收正在考虑的边的边属性字典。

See also

numerical_node_match, numerical_edge_match, numerical_multiedge_match

categorical_node_match, categorical_edge_match, categorical_multiedge_match

Notes

使用 vf2 算法 [1]。

References

[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

Examples

>>> 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)  # 不考虑权重
True
>>> nx.is_isomorphic(G1, G2, edge_match=em)  # 匹配权重
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，使用 ‘weight’ 和 ‘linewidth’ 边属性，默认值分别为 7 和 2.5。同时使用 ‘fill’ 节点属性，默认值为 ‘red’。

>>> 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