我正在寻找执行以下任务的算法的 Python 实现：
给定两个可能包含循环和它们的根的有向图，对这两个图的相似性产生一个分数。
（Pythondifflib可以为两个序列执行的方式）
希望这样的实现存在。否则，我会尝试自己实现一个算法。在这种情况下，最好的算法是什么（就简单性而言）。
算法的工作方式对我来说并不重要，尽管它的复杂性很重要。此外，使用不同数据结构的算法也是可以接受的，只要可以用这个 DS 表示像我描述的那样的图形。
我会强调，实现会更好。
编辑：
似乎同构算法不相关。有人建议图形编辑距离更重要，这将我的搜索范围缩小到执行图形编辑距离或将图形减少到树然后执行树编辑距离的解决方案。
节点本身由几行汇编代码组成。
另一种方法是使用所谓的特征向量相似度。基本上，您计算每个图的邻接矩阵的拉普拉斯特征值。对于每个图，找到最小的k，使得k个最大特征值的总和构成所有特征值总和的至少 90%。如果两个图之间的k值不同，则使用较小的那个。然后，相似性度量是图之间最大k个特征值之间的平方差之和。这将在 [0, ∞) 范围内产生相似性度量，其中接近零的值更相似。
例如，如果使用networkx：
def select_k(spectrum, minimum_energy = 0.9):
running_total = 0.0
total = sum(spectrum)
if total == 0.0:
return len(spectrum)
for i in range(len(spectrum)):
running_total += spectrum[i]
if running_total / total >= minimum_energy:
return i + 1
return len(spectrum)
laplacian1 = nx.spectrum.laplacian_spectrum(graph1)
laplacian2 = nx.spectrum.laplacian_spectrum(graph2)
k1 = select_k(laplacian1)
k2 = select_k(laplacian2)
k = min(k1, k2)
similarity = sum((laplacian1[:k] - laplacian2[:k])**2)
我们最终做的是实现一个算法，描述在：“Heuristics for Chemical Compound Matching”。
我们使用 NetworkX 来表示抓地力和寻找最大集团。
编辑：
基本上，您创建一个新图，每个节点 (v) 表示图 A (a) 中的节点与图 B (b) 中的节点的可能配对。
如果在您的应用程序中两个节点 (a,b) 相似或不相似，则从新图中删除对应于不同配对 (a,b) 的节点 (v)。如果它们不相互矛盾，则将两个节点连接到一条边。例如，配对 (a,b) 和 (a,c) 相互矛盾（有关正式定义，请参阅文章）。然后，您会在新图中找到一个具有最大节点数的集团。
如果在您的应用程序中两个节点的相似性不是二元的，则您可以在一个范围内（例如 (0,1)）赋予新节点的权重。您可以启发式地删除相似度等级低于预定义阈值的新节点。然后，您会在新图中找到一个具有最大权重（节点分配权重的总和）的集团。
无论哪种方式，您都会生成相似度等级：集团的大小/总权重除以原始图的属性的函数（A 和 B 的大小/权重的最大/最小/平均值）。
一个不错的功能是，您可以从发现的集团中推断出相似性的“来源”——“更强”的配对。
进一步说明： 约束取决于应用程序。我们使用该方法来比较成对的功能控制流图。通常，该方法找到第一个图中的某些节点与第二个图中的某些节点的匹配（子图到子图）。关联图中的每个节点表示来自第一个图中的单个节点与第二个图中的单个节点的可能匹配。由于最终选择了一个团（节点的子集），因此一条边意味着两个匹配项不相互矛盾。要申请不同的应用程序，您应该询问可能配对的标准是什么（或者我要创建哪些节点），以及选择一个配对如何影响另一个配对的选择（或者我如何将节点与边连接）。
这是一个老问题，但我想分享我的方法。我有一个 CVRP（Capacitated Vehicle Routing Problem）任务。我的启发式算法生成了几个不同的图表以找到解决方案。为了不陷入局部最优，我使用了放松和修复程序。
在这一点上，我不得不过滤掉过于相似的解决方案。由于大多数启发式方法在本地搜索过程中使用系统的邻域变化来提供解决方案，因此Edit距离 ( Levenshtein distance) 对我来说是完美的。Levenshtein算法的复杂度为O(n*m)n 和 m 是两个字符串的长度。因此，通过图形节点和路线的字符串表示，我能够找出相似性。edit operations可以考虑，因此neighborhood operations可以将其视为搜索空间距离（而不是解决方案空间距离）。
牺牲一些速度的更好/通用方法是Needleman-Wunsch算法。Needleman-Wunsch是一种混合相似性度量，它概括了 Levenshtein 距离并考虑了两个字符串之间的全局对齐。具体来说，它是通过为两个输入字符串之间的每个对齐分配一个分数并选择最佳对齐的分数来计算的，即最大分数。两个字符串之间的对齐是它们字符之间的一组对应关系，允许有间隙。
例如：
import py_stringmatching as sm
nw = sm.NeedlemanWunsch(gap_cost=0.5, sim_func=lambda s1, s2: (0.0 if s1 == s2 else 1.0))
print('\nNeedleman-Wunsch: ', nw.get_raw_score('045601230', '062401530'))
在示例中，您可以使用自定义 Levenshtein 算法。
Git 中存在 Levenshtein 的快速实现（使用 Cython、Numpy 等）。
一个不错的库是py_stringmatching，其中包含以下相似性算法列表：
我认为您定义相似性的方式不是很标准，因此可能更容易找到同构检查、图形编辑距离和最大公共子图的实现，然后自己组合它们。
然而，人们应该明白，计算这样的相似性度量可能会很昂贵，所以如果有很多图表，您可能需要先进行某种筛选。
例如， igraph可以检查同构。
编辑：实际上你可能只需要编辑距离，因为 MCS 的存在通常是无关紧要的，正如我上面指出的那样，如果编辑距离为 0，两个图无论如何都是同构的。