algorithm - 精确(纠错)图匹配算法

Question

我要在带有标记顶点和标记有向边的图上寻找一种不精确的图匹配算法。我的任务是检测两个图表的变化以将它们显示给开发人员(想想颠覆差异)。我已经实现了基于禁忌搜索 ( this ) 的优化算法，但我无法让该算法考虑我的边缘标签。我的图最多有 120 个顶点和 200 条边，因此我可能会使用更慢但更易于实现的算法。

为了您的观赏乐趣，这里有一个例子:

Answer 1

由于没有人提出现有算法，我将尝试发明一个...

对于每个顶点，您可以通过将其标签与所有相邻边的标签连接起来来计算其“签名”。为了保持一致性，请按字母顺序对标签进行排序。由于边是有向的，因此分别连接传入和传出边。

这些签名可用于检测顶点集的变化。首先，在第一张和第二张图中找到具有相同签名的对应顶点。剩余未配对的顶点是添加的顶点、移除的顶点、标签改变的顶点、边连接改变的顶点和边标签改变的顶点。您可以通过比较他们的签名并使用一些 string matching algorithm 选择最佳匹配来关联它们.显然，您将不得不引入一些关键的相似度来区分“它是具有许多更改属性的相同顶点”和“它是具有一些意外签名相似性的新顶点”。

以任意顺序排列数组中第一个图的所有顶点。创建另一个相同大小的数组。将第二个图的匹配顶点放入第二个数组中与第一个数组对应的位置；对所有完全匹配的顶点和所有修改的顶点执行此操作。对于在第二个图中没有匹配项的第一个图顶点(删除的顶点)，将数组单元格留空。然后，对于在第一个图中没有匹配的第二个图顶点(新顶点)，将这些顶点添加到第二个数组的末尾，并用相应数量的空单元格扩展第一个数组。

现在，当图的顶点列在数组中时，边可以表示为二维数组。如果一条边从第 i 个顶点到第 j 个顶点，则将其标签放入数组的 (i,j) 单元格中。

对两个图都这样做。由于你构造了两个相同大小的顶点数组，你得到两个相同大小的二维数组，具有一一对应关系。以直接的方式比较这两个数组可以让您检测添加的边缘、删除的边缘和更改标签的边缘。