C# 实现 VF 图同构算法
VF 图同构算法的 C# 实现。
引言
附加的代码是 VF 图同构算法的实现。该算法可以在 VF Graph Comparing library 中找到，并且还有其他程序可以作为包装器，例如从 Python 调用此库。当然，对于 C# 也可以这样做，但这里的代码完全用 C# 实现该算法，完全绕过了 C++ 库。这样做有几个原因。首先，它在完全托管的环境中提供了该算法。其次，我认为原始的 C++ 代码效率不高，写得也不太好。第三，VF 库实际上是为了比较各种算法而编写的，所以当你使用该库时，也会附带这些算法，最后，这听起来很有趣。
背景
图同构问题接受一对有向图作为输入，如果一个图是另一个图的“重新标记”版本，则返回 true。VF 算法还将执行子图同构，即第一个图的子图与第二个图同构。它还允许在匹配完成后检索映射。它允许进行上下文检查，其中节点可以携带属性，并且可以根据这些属性与同构节点的相应属性进行测试，然后根据测试结果拒绝匹配。最简单的情况是，它允许用户“着色”节点，并且只允许相同颜色的节点进行匹配。
VF 算法基本上是一次建立一个匹配项来构建同构，并对匹配项进行有根据的回溯搜索。在确定添加匹配项是否可接受时，有各种标准。其中一些仅仅是为了提高性能，但最重要的标准是新添加的匹配项维护了迄今为止收集的组的同构性。通过这种方式，当你处理完第二个图中的所有节点时，你就实现了你所寻求的同构，这似乎是显而易见的。
有关所有这些细节，可以在论文中找到：A (sub)graph isomorphism algorithm for matching large graphs。我的实现基本上遵循了这篇论文。唯一的主要区别是我使用排序列表来存储一些内部节点集，这意味着我更有可能尽早找到一个可行的匹配项。这也意味着我可以比原始算法更早地停止搜索。
使用代码
代码实现为一个类库。有两个主要类需要与代码进行接口。第一个是 Graph 类，用于创建/操作你的图。Graph 只有一个默认构造函数，不接受任何参数。一旦有了图，你可以使用 InsertNode() 插入节点，使用 InsertEdge() 插入边。通常，InsertNode 在不带参数的情况下调用，在这种情况下，它会返回插入节点的整数 ID。然后可以使用这些整数 ID 来调用 InsertEdge(int node1, int node2) 来在节点之间插入边。InsertNode 的另一种形式接受一个 object 参数，该参数代表插入节点的属性。属性可以是任意的，也可以是实现了 IContextCheck 接口。IContextCheck 非常简单，如下所示：
interface IContextCheck
{
bool FCompatible(IContextCheck icc);
}
如下所示，匹配可以设置为使用这些上下文检查属性，在这种情况下，任何被检查为可能匹配的两个节点都会调用上下文检查。如果上下文检查返回 false，则不允许匹配。在这种情况下，图中的所有属性都必须实现 IContextCheck。没有属性的节点将与任何其他节点匹配。属性也可以通过 InsertEdge(iNode1, iNode2, object attr) 附加到边上，但它们（目前）不能像节点属性那样用来影响匹配。
Graph graph = Graph();
// The first nodes is always ID 0 and the rest
// follow so we have nodes 0, 1, 2 and 3
graph.InsertNodes(4)
graph.InsertEdge(0,1);
graph.InsertEdge(1,2);
graph.InsertEdge(2,3);
graph.InsertEdge(3,0);
还有删除节点（DeleteNode(int ID)）和边（DeleteEdge(int idFrom, int idTo)）的方法。请注意，我们输入的是有向边，因此 InsertEdge(1,0) 与 InsertEdge(0,1) 是不同的边。
一旦你创建了一对你想检查同构性的图，你就可以使用构造函数 VfState(Graph graph1, Graph graph2) 创建一个 VfState 对象。然后可以使用 VfState 来执行实际的检查，如下所示：
...
VfState vfs = new VfState(graph1, graph2);
bool fIsomorphic = vfs.FMatch();
if (fIsomorphic)
{
// mapping[i] is the node in graph2 which corresponds to
// node i in graph1...
int[] mapping = vfs.Mapping1To2;
...
还有一个 Mapping2To1，它将 graph2 映射到 graph1。在子图同构（默认使用）中，算法寻找 graph1 的一个子图，该子图与 graph2 同构。VfState 可以接受两个 boolean 参数，或者 VfState(graph gr1, graph gr2, boolean fIso)，或者 VfState(graph gr1, graph gr2, boolean fIso, boolean fContextCheck)。如果 fIso 为 true，则算法寻找严格同构。这比搜索子图同构更有效。如果 fContextCheck 为 true，则所有节点属性都会根据映射中的对应项进行上下文检查，如上所述。
更新：除了上述两个 VfState 构造函数签名外，还有一个接受第三个 boolean 的构造函数：VfState(graph gr1, graph gr2, boolean fIso, boolean fContextCheck, boolean fFindAll)。默认情况下，fFindAll 为 false。如果为 true，则在匹配后，你可以获取所有同构的映射列表。每个同构在列表中由一个 FullMapping 结构表示，该结构仅包含两个 int[] 数组中的 1 到 2 和 2 到 1 映射，如下例所示。
...
VfState vfs = new VfState(graph1, graph2, false, false, true);
bool fIsomorphic = vfs.FMatch();
if (fIsomorphic)
{
// mapping[i] is the node in graph2 which corresponds to
// node i in graph1...
foreach(FullMapping fm in vfs.Mappings)
{
int[] mapping1to2 = fm.arinodMap1To2;
int[] mapping2to1 = fm.arinodMap2To1;
...
算法概述
如上所述，该算法基本上是在匹配空间中搜索 graph2 与 graph1 的某个子图之间的同构。我所说的“匹配”是指将 graph1 的单个节点映射到 graph2 的单个节点。搜索算法的每一步都提议将一个新的匹配项添加到迄今为止建立的同构中。如果我们能够将这些匹配项扩展到包含 graph2 的所有节点，我们就完成了。如果不能，我们就必须回溯并尝试不同的匹配项。此搜索的顶层算法如下所示（自 4/29 更新以来，这实际上是伪代码，其中删除了处理多个同构的部分以求清晰，但基本思想仍然保留）：
bool FMatchRecursive()
{
Match mchCur;
CandidateFinder cf;
if (FCompleteMatch())
{
return true;
}
cf = new CandidateFinder(this);
while ((mchCur = cf.NextCandidateMatch()) != null)
{
if (FFeasible(mchCur))
{
BacktrackRecord btr = new BacktrackRecord();
AddMatchToSolution(mchCur, btr);
if (FMatchRecursive())
{
_fSuccessfulMatch = true;
return true;
}
btr.Backtrack(this);
}
}
return false;
}
我应该指出，这是一个递归版本，更容易理解，但在实际代码中被 ifdef 掉了，转而使用非递归版本。你可以 ifdef 它重新启用，并通过 NUnit 代码验证其有效性，但对于足够大的图，它可能会导致堆栈溢出，并且效率较低。该方法使用 CandidateFinder 来定位潜在匹配项，遍历它们，并使用可行方法进行更仔细的检查。此检查包括确保匹配项不会破坏我们迄今为止建立的同构。BacktrackRecord 允许我们在匹配失败时撤消 AddMatchToSolution 调用产生的影响。我们暂时将匹配添加到当前同构中，将每个图的范围扩展一个节点，然后递归检查我们是否可以将这种新的同构扩展到 graph2 的完整映射。如果可以，我们就完成了并返回 true。如果不能，我们回到添加匹配项之前的状态，并在主循环中查找其他潜在匹配项。
这里的关键函数是 NextCandidateMatch 和 FFeasible。这两个函数非常依赖于将节点分为每个图的四个集合。第一个集合，我们将其称为图 1/图 2 上的 I1/I2，是参与算法每个阶段产生的同构的节点。第二个集合，T1/T2（图 1/图 2），是至少有一个边指向 I1/I2 中节点的节点集。第三个集合，F1/F2（图 1/图 2），是至少有一个边从 I1/I2 中的节点指向它们的节点集。请注意，如果一个节点在 I1/I2 中既有前驱节点又有后继节点，那么它既属于 F1/F2 也属于 T1/T2。最后，与同构中任何节点都不相连的节点属于 D1/D2 集。
这些组是通过使用枚举来维护的
[Flags]
enum Groups
{
ContainedInMapping = 1, // Contained in the mapping
FromMapping = 2, // Outside the mapping but pointed to from the mapping
ToMapping = 4, // Outside the mapping but points to a node in the mapping
Disconnected = 8 // Outside the mapping with no links to mapped nodes
}
每个节点都维护一个包含此枚举的字段，说明它属于哪个组。此外，VfState 类会保留这些组的列表，按节点的度排序。
显然，如果我们想通过在 graph1 的节点 N1 和 graph2 的节点 N2 之间添加一个匹配来维护同构，那么必须满足某些结构规则，这就是我们的搜索能够将候选对象缩小到少数几个并相对快速地剔除错误匹配项的方式。例如，CandidateFinder 确保节点要么都来自 T 集，要么都来自 F 集，要么都来自 D 集。T 集的情况源于这样一个观察：如果 N1 指向当前同构，那么 N2 也必须如此。F 集和 D 集也同理。如果 T1 或 T2 中没有节点，则候选查找器会查找 F 集，然后是 D 集。当 CandidateFinder 搜索特定组以进行匹配时，它会按度数递减进行搜索，因为列表就是这样排序的。这有几个含义。首先，它使我们能够更早而不是更晚地匹配正确节点的几率更高。其次，由于 N1 必须拥有的边数至少与 N2 一样多（请记住，graph2 可以映射到 graph1 的子图），因此一旦我们发现 T1 列表中的某个节点度数小于 N2，我们就可以放弃，因为之后的所有节点度数都会更低。实际上，如果正在寻找严格同构，那么我们可以在 T1 的第一个节点的度数与 T2 的第一个节点的度数不同时停止。在严格同构的情况下，存在许多等于失败条件的情况，而在子图同构的情况下，存在大于等于失败条件的情况。因此，我们在 VfState 类中有一个委托 fnComp，它执行上述两种测试之一，我们在 VfState 构造时设置一次，然后在此后代码中使用 fnComp 进行这些测试。
一旦 CandidateFinder 选择了一个可行的匹配项，我们就使用 FFeasible() 进行进一步检查。一个匹配项本质上必须通过四项测试才能通过 FFeasible()。第一个也是最重要的测试，只需验证将匹配项添加到当前同构不会破坏该同构。准确地说，同构中与 N1 连接的每个节点必须映射到一个同样与 N2 连接的节点。此外，如果正在进行上下文检查，它也在此可行性测试中进行，并且如果属性冲突，匹配项可能会被拒绝。这确实是唯一绝对的要求。只要这一点成立，随着我们添加节点，我们将始终维护 I 集节点的一个有效同构，这样当 graph2 的所有节点都在 I2 中时，我们就会得到一个完整的同构。但是，仅使用此标准会允许许多必须最终手动回溯的匹配项，因此我们希望在此处剪裁选择，这就是 FFeasible 的其他三个要求。
其他三个要求基本上是针对 T、F 和 D 组的同一规则的不同版本，因此我将只讨论 T 组，但同样的逻辑也适用于其他两个组。我仍然假设我们正在添加 graph1 的节点 N1 和 graph2 的节点 N2 之间的匹配。我们要求来自 T1 中节点到 N1 的入边数超过来自 T2 中节点到 N2 的入边数。出边也同理。这是我们使用 fnComp（如上所述）进行严格同构的相等性测试或子图同构的不等性测试的另一种情况。同样的测试也适用于 F 集和 D 集。执行上述第一个测试（T1 节点到 N1 的入边数与 T2 节点到 N2 的入边数比较）的代码如下所示：
if (!fnCmp(
GetGroupCountInList(lstIn1, _vfgr1, Groups.FromMapping),
GetGroupCountInList(lstIn2, _vfgr2, Groups.FromMapping)))
{
return false;
}
这里，GetGroupCountInList() 只是计算第一个参数列表中属于 _vfgr1（graph1）或 _vfgr2（graph2）给定图的正确组的节点数。lstIn1 只是指向 N1 的边的节点列表，lstIn2 也是如此。
当我们添加匹配到同构时，这可能会将其他几个节点移动到其他组。AddMatchToSolution() 方法在回溯记录中跟踪所有这些移动，以便在匹配失败时可以将其全部移回。回溯记录只是 BacktrackAction 的链表，每个 BacktrackAction 要么是移动到同构中，要么是移动到另一个组。
这完成了算法的概述。我没有包括 Graph 和 VfGraph 之间的转换。主要区别在于以度数递增的顺序对 VfGraph 中的节点进行排序，并设置各种节点列表以准备 VF 算法。所有节点最初都放在 D 组，I 组为空。我们还保留原始 Graph 结构中的未排序节点与 VfGraph 结构中的节点之间的映射，以便我们最终可以整理所有内容，并通过 Mapping2To1 和 Mapping1To2 返回映射，这些映射引用原始 Graph 对象中的节点 ID，而不是 VfGraph 中使用的 ID。这在很大程度上是记账问题，而不是算法本身的一部分。
性能
当我开始研究代码时，我想了解有多少匹配项通过了候选查找器，有多少通过了可行性检查器，以及有多少通过了两者但最终被回溯。我让我的随机图生成器创建了一个包含 1000 个节点的随机图，并令人惊讶地发现没有节点被回溯——候选查找器和可行性检查器的组合就像一个完美的预言机，能够预测最终进入同构的内容。这似乎是不可能的，我怀疑是有一个 bug。为了测试这一点，我注释掉了回溯的调用，并运行了所有的 NUnit 代码。两个测试失败了，这让我感觉好多了——我的回溯代码实际上是有用的。在我开始思考这个问题之后，一切都变得更有意义了。对于随机图，具有最大度的节点可能很少。对于具有相同最大度的节点，为了通过可行性测试，它们必须拥有相同数量的出边和入边。更有可能的是，这唯一地确定了第一个要进入同构的匹配项。从那里开始，随着同构的建立，同构本身出错的可能性迅速降至几乎为零，因为假设与此相反，就是假设随机图中存在两个同构相同的区域。添加新匹配项也是如此，因为它们必须附加到当前同构上，而且很有可能只能匹配到同构的一个位置。所以，我们很有可能正确地获得第一个匹配项，并且在此之后，成功的几率会增加而不是减少。因此，我开始意识到该算法在随机图上会工作得非常好。事实上，如果我们假设没有回溯并且平均度数恒定，我相信该算法的复杂度是 O(n^2)，这非常棒。
当然，此时，我想尝试找到更糟糕的情况。似乎很明显，如果图“高度自同构”，即图的大部分区域与其他区域同构，那么回溯会更多。对我来说，一个非常糟糕的情况是网格——节点位于网格线的交叉点，并且沿着网格线连接它们。当我尝试这个时，果然，有很多很多的回溯。我意识到当没有同构时情况会更糟，所以我用一条边将网格的两个相对“角”连接起来，而第二个图没有这条边。我不得不取消运行，因为等待时间很长，因为我认为它非常接近最坏情况。由于角点的度数低于中心节点，因此在所有中心节点都经过同构检查之后才会检查它们，并且由于它们是唯一非同构的部分，因此它会尝试无数次备份。为了验证这一点，我没有在这两个节点之间插入一条边，而是插入了多条边，使它们的度数更高，从而使算法首先检查它们。这使得运行时间几乎是即时的。当然，我尝试的是一个 30x30 的网格，对于较小的版本，它可能运行得相当好。一个可以消除这个特定问题的方法是只比较节点度数。由于我已经按度数对节点进行了排序，因此这应该很容易。对于子图，这也将起作用，我必须在第二个图的节点和第一个图中度数更大的节点之间建立一对一映射。
另一个潜在的问题区域可能是比较具有更高度数的图与具有更低度数的图。这可能会消除排序节点的优势，而排序节点倾向于将同构节点聚集在候选查找器中。我认为这不会是一个太糟糕的问题，因为本文开头链接中描述的原始算法根本没有利用图的排序。当然，如果度数足够高，实际上可能会更容易，因为节点更容易匹配到其他节点。在极端情况下，如果第一个图是完全图，任何一对一映射都可以。
所以，教训是，最坏情况可能非常糟糕，但较小的图或更随机的图可以安全地预期 O(n^2) 的性能。
我还进行了一些非常不严谨的计时（例如，我没有尝试消除任何后台处理），并在我的随机图测试中得到了以下结果：
请注意，每节点的平均时间已乘以 4000，以便在图上进行良好的缩放。1000 节点图的边负载因子为 0.1，因此每个节点平均大约有 100 个入边和 100 个出边。我想保持所有图的度数相同，因此对于其他大小的图，边负载因子与节点数成反比。因此，2000 节点图的负载因子为 0.05。
关注点
应该指出几个注意事项。首先，当我们谈论子图同构时，这里的子图定义是通过移除节点及其关联边得到的图。这意味着你不能直接移除边，除非它们附加到被移除的节点上。我不认为这是一个大问题，但尚未纳入。
代码包含了 NUnit 测试。我喜欢 NUnit，并推荐你获取它以及优秀的 TestDriven.NET Visual Studio 插件。它们都是免费且非常有价值的，我认为你最终会很高兴拥有它们。但是，如果你实在不愿意迈出这些简单的步骤，那么你只需删除项目中的 NUnit.FrameWork 引用，并将 NUNIT 定义从调试配置中删除。即使在这种情况下，通过查看 NUnit 代码，你可能也能更好地理解代码。代码中没有测试或演示程序，因为它完全通过 NUnit 进行测试。
最后一点——我假设基础代码在 Mono 上运行得很好，但我没有进行设置来测试。我不确定 NUnit 是否在那里运行，所以可能也需要将其删除。
历史
- 08-1-23 - 第一个版本。
- 08-1-24 - 添加了算法概述，以及（糟糕！）最初忘记将
FMatch public。添加了一个被ifdef掉的递归调用，并进行了一些名称更改。 - 08-1-30 - 修正了第一个链接，添加了性能部分，并添加了一个快速的一次性图度数兼容性检查。
- 08-4-29 - 添加了获取所有同构列表的功能，而不是只获取找到的第一个。