特定のグラフのセットから同形グラフのクラスを識別するヒューリスティック ソリューションを実装しようとしています。現在、各ノードに隣接ノードの次数のマルチセット (WL アルゴリズム) をラベル付けしています。
これは、次数規則グラフなどの場合、明らかに誤検知を引き起こします。私は、WL アルゴリズムのコーナー ケースを横断できる、安価に実装できる (時間とスペースの制約がある) 別のヒューリスティックを見つけたいと考えていました。基本的に、私は、それらの間でわずかな誤検知を与える、簡単に実装できるヒューリスティックのペアを探しています。
WL アルゴリズム以外のどのヒューリスティックを調べる必要がありますか?
ありがとう！
VF2 アルゴリズムをチェックしてください。
VF2 を実装する C++ ライブラリがあります: http://mivia.unisa.it/datasets/graph-database/vflib/
VF2 と他のいくつかのアルゴリズムの比較: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.2640&rep=rep1&type=pdf
おそらく、この論文で説明されている最小色の最短経路不変式を考えてみてください: http://www.academia.edu/5111652/A_new_refinement_procedure_for_graph_isomorphism_algorithms ?
比較的安価に計算できるもう 1 つの不変条件は、頂点が含まれるサイクルのリストです。もちろん、それにはグラフ内のサイクルを見つける必要がありますが、それを行うアルゴリズムはたくさんあります。