プロジェクトでは、networkx と連携して NAUTY スタイルの同形性チェック プログラムを作成する python プログラムを作成しています。私のプログラムは、ここにある Nauty の紹介に基づいており、次のように機能します。
2 つのグラフ G と H を取り、次数に応じてノードに色を付けます。色クラスの各ノードの近傍に基づいてグラフの色を調整する色調整アルゴリズムを実行します。このペア (G', H') は、検索ツリーの「ルート」になり、DFS アルゴリズムを使用します。次に、複数の要素を持つ最小の色クラスに属する G' のノードを個別化し、分岐法を使用して、新しい木のペア (G'', H''), (G'' , H'''), ... (G'', H^(k)) (k は色クラスのサイズに依存します。たとえば、色クラス red の g の場合: [1,2,3]は G の赤いノードであり、[5,6,7] は H の赤いノードです。次に、ペア 1:5、1:6、1:7 の検索ツリーの分岐を作成し、開く必要があります。後で検索ツリーにアクセスする新しいブランチ)。そして、摩擦があります！私のツリーは大きくなりすぎ、速すぎます。これは、上記のリンクの「ノードの不変条件とプルーニング」の部分で説明されているノードの不変条件を使用していないためです。
誰かが私が使用できるノード不変条件のいくつかの例を説明できますか? StackExchange では、ここではあまり役に立ちませんでした。ノードの色がノードの不変条件であるという事実を想定して使用していますが、強力な通常のグラフの場合、それは常に多くのことをもたらすとは限りません。何か案は？