上一篇文章可以在这里找到，请务必查看它，以便您可以逐步跟踪流程。从那时起，该算法的另外两个非常重要的特性已经实现并测试：节点对候选者选择和可行性检查。

介绍#

如前所述，在 ISO 问题中，我们基本上试图创建一个映射，这样，第一个图中的每个节点都与第二个图中的一个节点匹配。这种寻找“可行对”的过程可以用一棵树来可视化，树中的每个节点都是我们应该检查的候选对。如果我们看看下图，这会变得更加清晰。

DFS VF2++ example$

为了检查图 $G_1$，$G_2$ 是否同构，我们检查每个候选节点对，如果它是可行的，我们扩展映射并深入到对的树中。如果不可行，我们向上攀爬并沿着另一条分支前进，直到 $G_1$ 中的每个节点都映射到 $G_2$ 中的一个节点。在我们的例子中，我们从检查 G1 中的节点 0 与 G2 中的节点 0 开始。经过一些检查（详细信息如下），我们确定节点 0 和 0 匹配，因此我们深入到映射剩余节点。下一对是 1-3，它不满足可行性检查，因此我们必须检查如图所示的不同分支。新的分支是 1-2，它是可行的，因此我们继续使用相同的逻辑，直到所有节点都被映射。

候选对选择#

虽然在我们的例子中我们使用随机的节点候选对，但在实际实现中，我们能够瞄准更有可能匹配的特定对，从而提高算法的性能。这个想法是，在算法的每一步，给定一个候选者

$$u\in V_1$$

我们计算候选者

$$v\in V_2$$

其中 $V_1$ 和 $V_2$ 分别是 $G_1$ 和 $G_2$ 的节点。现在这是一个不需要太多关于图或算法本身的特定知识的难题。跟我保持一致，你就会自己意识到。首先，令 $M$ 为迄今为止的映射，它包含了到目前为止所有“被覆盖的节点”。实际上，我们可能会遇到三种不同类型的 $u$ 节点。

情况 1#

节点 $u$ 没有邻居（$u$ 的度数等于零）。对于 $u$ 而言，测试 $G_2$ 中具有超过零个邻居的节点作为候选者是多余的。也就是说，我们消除了大多数可能的候选者，只保留了那些与 $u$ 具有相同度数（在这种情况下，为零）的节点。非常容易，对吧？

情况 2#

节点 $u$ 具有邻居，但它们都不属于映射。这种情况在下图中说明。

candidates

灰色线条表示 $G_1$（左 1,2）的节点映射到 $G_2$（右 1,2）的节点。它们基本上是映射。同样，给定 $u$，我们观察到 $u$ 的候选者 $v$ 也应该在映射中没有邻居，并且也应该与 $u$ 具有相同的度数（如图所示）。请注意，如果我们向 $v$ 添加一个邻居，或者如果我们将它的一个邻居放在映射中，那么检查 $u-v$ 是否匹配就没有意义。

情况 3#

节点 $u$ 具有邻居，其中一些属于映射。这种情况也在下图中描述。

candidates

在这种情况下，为了获得 $u$ 的候选者，我们必须查看映射回 $u$ 的被覆盖邻居的 $G_2$ 中的节点的邻域。在我们的例子中，$u$ 只有一个被覆盖的邻居（1），而 $G_1$ 中的 1 映射到 $G_2$ 中的 1，它具有 $v$ 作为邻居。此外，为了将 $v$ 视为候选者，它应该与 $u$ 具有相同的度数，显然。请注意，不在 1（在 $G_2$ 中）的邻域中的每个节点都不能与 $u$ 匹配，而不会破坏同构性。

ISO 可行性规则#

假设给定一个节点 $u$，我们按照上一节中描述的过程获得了它的候选者 $v$。在这一点上，可行性规则将决定是否应该通过 $u-v$ 对来扩展映射，或者我们应该尝试其他候选者。对 $u-v$ 的可行性通过一致性和剪枝检查进行检查。

一致性规则#

首先，我将介绍一致性检查的数学表达式。它可能一开始看起来很复杂，但使用可视化说明可以简化它。使用 $nbh_i(u)$ 表示 $u$ 在图 $G_i$ 中的邻域，一致性规则是

$$\forall\tilde{v}\in nbh_2(v)\cap M:(u, M^{-1}(\tilde{v}))\in E_1) \wedge \forall\tilde{u}\in nbh_1(u)\cap M:(u, M(\tilde{u}))\in E_2)$$

我们将使用以下简单图来解开上述方程的谜团。

consistency check scenario

映射被描绘为已经在映射的节点之间的灰色线条，这意味着 1 映射到 A，2 映射到 B。该方程隐含的是，对于两个节点 $u$ 和 $v$ 才能通过一致性检查，$u$ 的属于映射的邻居应该映射到 $v$ 的邻居（反之亦然）。这可以通过像下面这样的代码来检查

for neighbor in G1[u]:
    if neighbor in mapping:
        if mapping[neighbor] not in G2[v]:
            return False
        elif G1.number_of_edges(u, neighbor) != G2.number_of_edges(
            v, mapping[neighbor]
        ):
            return False

其中最后两行还检查节点 $u$ 与其邻居 $\tilde{u}$ 之间的边数，它应该与 $v$ 与 $\tilde{u}$ 映射到的邻居之间的边数相同。在非常高的层次上，我们可以将此检查描述为 1-look-ahead 检查。

剪枝规则#

我们之前已经讨论了 $T_i$ 和 $\tilde{T_i}$ 的含义（参见上一篇文章）。这些集合在剪枝检查中使用如下：$u$ 的属于 $T_1$ 的邻居数量应该等于 $v$ 的属于 $T_2$ 的邻居数量。花点时间观察下图。

cutting check scenario

同样，节点 1 映射到 A，2 映射到 B。红色节点（4,5,6）基本上是 $T_1$，黄色节点（C,D,E）是 $T_2$。请注意，为了使 $u-v$ 可行，$u$ 在 $T_1$ 中应该具有与 $v$ 在 $T_2$ 中相同的邻居数量。在其他任何情况下，这两个图都不同构，这可以通过视觉方式验证。对于这个例子，这两个节点在 $T_1$ 和 $T_2$ 中分别有 2 个邻居（4,6 和 C,E）。小心！如果我们删除 $V-E$ 边并将 $V$ 连接到 $D$，剪枝条件仍然满足。但是，可行性将通过上一节中的一致性检查失败。应用剪枝检查的简单代码将是

if len(T1.intersection(G1[u])) != len(T2.intersection(G2[v])) or len(
    T1out.intersection(G1[u])
) != len(T2out.intersection(G2[v])):
    return False

其中 T1out 和 T2out 分别对应于 $\tilde{T_1}$ 和 $\tilde{T_2}$。是的，我们必须检查这些，但是为了简单起见，我们在上面的解释中跳过了它们。

结论#

在这一点上，我们已经成功地实现并测试了算法 VF2++ 的所有主要组成部分，

  • 节点排序
  • $T_i/\tilde{T_i}$ 更新
  • 可行性规则
  • 候选者选择

这意味着，在下一篇文章中，希望我们能够讨论我们对 VF2++ 的第一个完整且功能齐全的实现。