Isomorphism#

`is_isomorphic`(G1, G2[, node_match, edge_match])	如果图 G1 和 G2 是同构的，则返回 True，否则返回 False。
`could_be_isomorphic`(G1, G2)	如果图绝对不是同构的，则返回 False。 True 并不保证同构。
`fast_could_be_isomorphic`(G1, G2)	如果图绝对不是同构的，则返回 False。
`faster_could_be_isomorphic`(G1, G2)	如果图绝对不是同构的，则返回 False。

VF2++#

VF2++ 算法#

VF2++ 算法 [1] 的实现，用于图同构测试。

使用此模块的最简单接口是调用：

vf2pp_is_isomorphic ：检查两个图是否同构。 vf2pp_isomorphism ：获取两个图之间的节点映射（如果它们是同构的）。 vf2pp_all_isomorphisms ：生成两个图之间的所有可能映射（如果它们是同构的）。

Introduction#

VF2++ 算法遵循与 VF2 类似的逻辑，同时引入了新的易于检查的剪枝规则，并确定了节点的最佳访问顺序。它还以非递归方式实现，与之前的版本相比，节省了时间和空间。

最佳节点排序是通过同时考虑节点的度数和标签稀有性来获得的。这样，我们将更有可能匹配的节点放在顺序的前面，从而从一开始就检查最有希望的分支。这些规则还考虑节点标签，使得在过程早期更容易修剪无果的分支。

Examples#

假设 G1 和 G2 是同构图。验证如下：

无节点标签：

>>> import networkx as nx
>>> G1 = nx.path_graph(4)
>>> G2 = nx.path_graph(4)
>>> nx.vf2pp_is_isomorphic(G1, G2, node_label=None)
True
>>> nx.vf2pp_isomorphism(G1, G2, node_label=None)
{1: 1, 2: 2, 0: 0, 3: 3}

有节点标签：

>>> G1 = nx.path_graph(4)
>>> G2 = nx.path_graph(4)
>>> mapped = {1: 1, 2: 2, 3: 3, 0: 0}
>>> nx.set_node_attributes(
...     G1, dict(zip(G1, ["blue", "red", "green", "yellow"])), "label"
... )
>>> nx.set_node_attributes(
...     G2,
...     dict(zip([mapped[u] for u in G1], ["blue", "red", "green", "yellow"])),
...     "label",
... )
>>> nx.vf2pp_is_isomorphic(G1, G2, node_label="label")
True
>>> nx.vf2pp_isomorphism(G1, G2, node_label="label")
{1: 1, 2: 2, 0: 0, 3: 3}

References#

[1]

Jüttner, Alpár & Madarasi, Péter. (2018). “VF2++—An improved subgraph isomorphism algorithm”. Discrete Applied Mathematics. 242. https://doi.org/10.1016/j.dam.2018.02.018

`vf2pp_is_isomorphic`(G1, G2[, node_label, ...])	检查G1和G2是否同构。
`vf2pp_all_isomorphisms`(G1, G2[, node_label, ...])	生成所有可能的G1和G2之间的映射。
`vf2pp_isomorphism`(G1, G2[, node_label, ...])	返回 `G1` 和 `G2` 之间的同构映射（如果存在）。

Tree Isomorphism#

一种用于判断两棵无向树是否同构的算法，如果同构则返回两组节点之间的同构映射。

该算法使用了一个判断两棵有根树（指定根节点的树）是否同构的例程，该例程可能具有独立的使用价值。

该算法实现来自：《计算机算法的设

`rooted_tree_isomorphism`(t1, root1, t2, root2)	给定两棵有根树 `t1` 和 `t2` ，分别以 `root1` 和 `root2` 为根，此程序将判断它们是否同构。
`tree_isomorphism`(t1, t2)	给定两个无向（或自由）树 `t1` 和 `t2` ，此程序将确定它们是否同构。它返回一个同构映射，即将 `t1` 的节点映射到 `t2` 的节点上，使得两棵树完全相同。