图匹配算法

Question

我一直在寻找用Python编写的图形匹配算法，但是我没有找到多少。

我目前正在尝试匹配两个不同的图形，它们是从两组不同的字符序列派生而来的。我知道这两个图之间有一种潜在的联系，更确切地说，是节点之间的一对一映射。但是图没有相同的标签，因此，我需要通过比较拓扑和/或属性来返回节点映射的图形匹配算法。通过测试，我希望能最大限度地得到正确的匹配。

我一直在使用graphsim包中的Blondel和Heyman，并且打算在同一个包中使用Tacsim。我想测试其他选项，可能更标准，比如最大子图同构，或者找到两个图之间很好匹配的子图。如果图形编辑距离能够给出匹配，它也可能会有所帮助。

问题是，即使在我正在使用的Networkx中，我也找不到实现的任何东西。有人知道Python的实现吗？如果这些选项使用Networkx，那将是一种好处。

Answer 1

我发现了这个图形编辑距离算法的实现，它在Python中使用了NetworkX。

https://github.com/Jacobe2169/GMatch4py

GMatch4py是一个专门用于图形匹配的库。图形结构存储在NetworkX图形对象中。GMatch4py算法是用Cython实现的，以提高性能。