精确(纠错)图匹配算法

Question

我正在寻找一个不精确的图匹配算法，在有标号点和有标记有向边的图上。我的任务是检测对两个图的更改，并将它们显示给开发人员(想想subversion diff)。我已经实现了一个基于禁忌搜索( tabu，这)的优化算法，但是我无法得到该算法来考虑我的边缘标签。我的图最多有120个顶点和200个边，所以我可以用一个更慢但更简单的实现算法。

以下是您观赏乐趣的一个例子：

​

Answer 1

既然没有人提出现有的算法，我会尝试发明一种.

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

这些签名可用于检测顶点集合中的更改。首先，在第一个图和第二个图中找到具有相同签名的对应顶点。剩余的未配对顶点是添加顶点、删除顶点、更改标签的顶点、改变边缘连接的顶点以及边缘标签被更改的顶点。您可以通过比较它们的签名并使用一些字符串匹配算法选择最佳匹配来关联它们。显然，你必须引入一些临界程度的相似性来区分“这是同一个有许多变化的属性的顶点”和“它是一个具有一些偶然特征相似性的新顶点”。

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

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

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