我正在寻找一个Python实现的算法，它执行以下任务：
给定两个可能包含循环的有向图及其根节点，生成两个图相似度的分数。
（类似Python中difflib对两个序列所执行的方式）
希望这样的实现已经存在。否则，我将尝试自己实现算法。在这种情况下，哪种算法更简单易懂？
算法的工作方式对我来说并不重要，但它的复杂性很重要。 另外，只要可以用这个数据结构表示我描述的图形，使用不同数据结构的算法也是可以接受的。
我强调，有实现会更好。
编辑：
似乎同构算法与此无关。建议使用图编辑距离更加切合要求，这将缩小我的搜索范围，只需一个能够执行图编辑距离或将图缩减为树然后执行树编辑距离的解决方案。
节点本身由几行汇编代码组成。
另一种方法是使用称为特征向量相似度的方法。基本上，您需要计算每个图的邻接矩阵的拉普拉斯特征值。对于每个图，找到最小的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)
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'))
我认为你定义相似性的方式不是很标准，因此可能更容易找到同构检查、图编辑距离和最大公共子图的实现，然后自己组合。
然而，需要理解计算这样的相似度量可能是昂贵的，因此如果有很多图形，您可能需要先进行某种筛选。
igraph 例如可以检查同构。
编辑：实际上，您可能只需要编辑距离，因为MCS的存在通常是无关紧要的，正如我上面指出的那样，如果编辑距离为0，则两个图形将是同构的。