次のタスクを実行するアルゴリズムのPython実装を探しています。
サイクルを含む可能性のある2つの有向グラフとそのルートが与えられると、2つのグラフの類似性に対するスコアが生成されます。
（Pythondifflibが2つのシーケンスに対して実行できる方法）
うまくいけば、そのような実装が存在します。それ以外の場合は、自分でアルゴリズムを実装してみます。その場合、（単純さに関して）実装するのに好ましいアルゴリズムは何ですか。
アルゴリズムの動作方法は私には重要ではありませんが、その複雑さは重要です。また、私が説明したようなグラフがこのDSで表現できる限り、異なるデータ構造で動作するアルゴリズムも受け入れられます。
強調しておきますが、実装の方がはるかに優れています。
編集：
同型写像アルゴリズムは関係ないようです。グラフ編集距離はよりポイントに近いことが示唆されました。これにより、グラフ編集距離を実行するか、グラフをツリーに縮小してからツリー編集距離を実行するソリューションに検索が絞り込まれます。
それらのノードは、それぞれ数行のアセンブリコードで構成されています。
別の方法は、固有ベクトル類似性と呼ばれるものを使用することです。基本的に、各グラフの隣接行列のラプラシアン固有値を計算します。各グラフについて、 k個の最大固有値の合計がすべての固有値の合計の少なくとも90％を構成するように、最小のkを見つけます。kの値が2つのグラフ間で異なる場合は、小さい方を使用してください。類似性メトリックは、グラフ間の最大のk固有値間の差の2乗の合計です。これにより、[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)
最終的に行ったことは、 「化合物マッチングのヒューリスティック」で説明されているアルゴリズムを実装することです。
グラフを表現し、最大クリークを見つけるためにNetworkXを使用しています。
編集：
基本的に、新しいグラフを作成します。各ノード（v）は、グラフA（a）のノードとグラフB（b）のノードの可能なペアを表します。
アプリケーションで2つのノード（a、b）が類似しているかどうかにかかわらず、異なるペアリング（a、b）に対応するノード（v）を新しいグラフから削除します。2つのノードが互いに矛盾しない場合は、それらをエッジで接続します。たとえば、ペアリング（a、b）と（a、c）は互いに矛盾しています（正式な定義については記事を参照してください）。次に、ノードの数が最大であるクリークを新しいグラフで見つけます。
アプリケーションで2つのノードの類似性がバイナリでない場合は、新しいノードに範囲内の重みを指定します（たとえば、（0,1））。ヒューリスティックに、事前定義されたしきい値よりも低い類似度を持つ新しいノードを削除できます。次に、最大の重み（ノードに割り当てられた重みの合計）を持つクリークを新しいグラフで見つけます。
いずれにせよ、類似性グレードを生成することで終了します。クリークのサイズ/総重量を元のグラフの属性の関数で割ったものです（AとBのサイズ/重量の最大/最小/平均）。
優れた機能は、見つけたクリークから類似性の「ソース」、つまり「より強力な」ペアリングを推測できることです。
さらに明確にする： 制約はアプリケーションに依存します。このアプローチを使用して、関数制御フローグラフのペアを比較しました。一般に、このアプローチでは、最初のグラフの一部のノードと2番目のグラフの一部のノード（サブグラフからサブグラフ）の一致が検出されます。アソシエーショングラフの各ノードは、最初のグラフの単一ノードから2番目のグラフの単一ノードへの一致の可能性を表しています。最終的にクリーク（ノードのサブセット）が選択されるため、エッジは2つのマッチングが互いに矛盾しないことを意味します。別のアプリケーションに申し込むには、可能なペアリングの基準（または作成するノード）と、あるペアリングの選択が別のペアリングの選択にどのように影響するか（またはノードをエッジに接続する方法）を尋ねる必要があります。
これは古い質問ですが、私のアプローチを共有したいと思います。CVRP（Capacitated Vehicle Routing Problem）タスクがありました。私のヒューリスティックアルゴリズムは、解決策を見つけるためにいくつかの異なるグラフを作成しました。局所最適にとらわれないように、私はリラックスと修復の手順を使用しました。
この時点で、類似しすぎたソリューションを除外する必要がありました。ほとんどのヒューリスティックアプローチは、ローカル検索手順内の近隣の体系的な変更を使用してソリューションを提供するため、Edit距離（Levenshtein distance）は私にとって完璧でした。Levenshteinアルゴリズムの複雑さはO(n*m)、nとmが2つの文字列の長さであるという複雑さです。したがって、グラフノードとルートの文字列表現を使用して、類似性を把握することができました。は、（解空間距離ではなく）探索空間距離と見なすことができるようにedit operations考えることができます。neighborhood operations
Needleman-Wunsch速度をいくらか犠牲にするより良い/一般化されたアプローチはアルゴリズムでしょう。Needleman-Wunschは、レーベンシュタイン距離を一般化し、2つの文字列間のグローバルアラインメントを考慮するハイブリッド類似度です。具体的には、2つの入力文字列間の各配置にスコアを割り当て、最適な配置のスコア、つまり最大スコアを選択することによって計算されます。2つの文字列間の配置は、それらの文字間の一連の対応であり、ギャップを考慮に入れています。
例えば：
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'))
この例では、カスタムレーベンシュタインアルゴリズムを使用できます。
レーベンシュタインの高速実装はGitに存在します（Cython、Numpyなどを使用）。
優れたライブラリはpy_stringmatchingであり、類似性アルゴリズムの次のリストが含まれています。
類似性を定義する方法はあまり標準的ではないと思うので、同型チェック、グラフ編集距離、最大共通サブグラフの実装を見つけて、それらを自分で組み合わせる方がおそらく簡単です。
ただし、このような類似度の計算にはコストがかかる可能性があることを理解する必要があります。そのため、グラフが多数ある場合は、最初に何らかのスクリーニングを実行することをお勧めします。
たとえば、 igraphは同型をチェックできます。
編集：上で指摘したように、MCSの存在は通常は無関係であり、編集距離が0の場合、2つのグラフはとにかく同型になるため、実際には編集距離のみが必要です。