ELSIEのグラフ同型判定機能

ELSIEの6番目のオプションである Random matrices を実行して例外が発生している.⇒CriticalStateで例外をthrowしている. この関数では例外なく例外をスローしてトラップから出るようになっている.暫定的に平常時の脱出口を設けた.コンソールで0を入力すると処理を中断するようになっているが,エラーが発生する.USERABORT –1023 だ.⇒ゼロ復帰するように修正した.

昨日のログでは「Mirroring Methodというのは,MATRIXINVARIANTが定義されていないときに実行されるアルゴリズムと見られる」としているが,その反対ではないか?いや,間違ってはいない.現行ソースではMATRIXINVARIANTはオフになっている.動作チェックするために,暫定的にオンにしてみたのではなかったろうか?

NARCISSUSというマクロもある.多分,グラフ同型判定用と思われる.このリテラルがオンになっているとCallNautyという関数が呼ばれるようになっている.この関数の実装は含まれていないが,多分Nautyを呼び出しているのだろう.Nautyというのは確か,オーストラリアの先生が書いた最速のグラフ同型判定プログラムだ.

グラフのサンプルファイルは以下のような書式になっている.

===================================================================================
Graph Isomorphism : Counter Example  Sun Sep 10 15:47:11 2023
===================================================================================
#1 > 1 3 4 5 6 7 8 9 10 11 12
#2 > 2 4 5 6 7 8 9 10 11 12
#3 > 1 2 4 6 7 8 12
#4 > 2 3 4 5 6 9 10
#5 > 2 3 5 6 7 8 9 10 11 12
#6 > 2 3 6 8 9 11
#7 > 3 6 7 8 9 10 11 12
#8 > 2 5 6 9 10
#9 > 1 5 9 10 11 12
#10 > 1 2 3 4 5 6 9 10 11
#11 > 1 3 4 5 6 8 9 10 11
#12 > 2 4 6 7 9 10 11 12

これはおそらく,隣接行列というより,隣接リストと呼ばれるべきものだろう.実際,このリストは変換されて以下のような隣接行列として出力される.

    1  2  3  4  5  6  7  8  9  0  1  2
  1:  1  0  1  1  1  1  1  1  1  1  1  1
  2:  0  1  0  1  1  1  1  1  1  1  1  1
  3:  1  1  0  1  0  1  1  1  0  0  0  1
  4:  0  1  1  1  1  1  0  0  1  1  0  0
  5:  0  1  1  0  1  1  1  1  1  1  1  1
  6:  0  1  1  0  0  1  0  1  1  0  1  0
  7:  0  0  1  0  0  1  1  1  1  1  1  1
  8:  0  1  0  0  1  1  0  0  1  1  0  0
  9:  1  0  0  0  1  0  0  0  1  1  1  1
10:  1  1  1  1  1  1  0  0  1  1  1  0
11:  1  0  1  1  1  1  0  1  1  1  1  0
12:  0  1  0  1  0  1  1  0  1  1  1  1

グラフ同型判定でサンプルを自動生成しているが,まったく同型なサンプルが作れていない.⇒元のグラフの隣接行列をシャッフルしているが,行の入れ替えしかやっていないため,ノーマルなグラフの形が崩れてしまっている.グラフの場合は,行と列は完全に対応していなくてはならない.つまり,行ヘッダと列ヘッダは完全に一致する必要がある.(実際には行ヘッダ/列ヘッダのようなものは持っていないが)⇒Shuffleを書き換えて,行と列を完全に同期するようにした.

グラフが有向か無向かのチェックを行っているが,そのあと,有向グラフを弾いている.⇒有向グラフも検定の対象となるように修正した.また,有向枝のダンプも止めた.

コンソールで0を入力すると処理を打ち切って,メニューに戻れるようにした.これでグラフ同型検定はある程度使い物になるようになった.

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA