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を入力すると処理を打ち切って,メニューに戻れるようにした.これでグラフ同型検定はある程度使い物になるようになった.