Elsieを起動して,6.Random matrices を選択→matrix size→iteration countを入力したところで,例外が発生する.
freopen_s(&logfile, EXPERIMENTLOG, “a+”, logfile)で失敗している.EXPERIMENTLOGには “Experiment.log”という文字列が入っている.ソースコードにはログファイルを開いている箇所は存在しない.logfileはまったく使われている形跡がない.とりあえず,止めておくことにしよう.EXPERIMENTLOGで止めるようにした.
一応動作するようになったが,何をやっているのか?さっぱりわからない.こんな出力が出ている.
p0:EchoingMethod: ._NORMAL_ (12,12,12)
orbits=FIXED POINTS
p1:EchoingMethod: ._NORMAL_ (12,12,12)
orbits=FIXED POINTS
O0: 3 2 8 12 9 7 6 10 11 1 5 4
O1: 12 2 9 11 10 1 7 4 6 5 8 3
Matrices are isomorphic: Required time=722466:55:08, N=12, M=50, axes=0, crack=0
Psi0=(2.6136868720357000E+13:26136868720357)
Psi1=(2.6136868720357000E+13:26136868720357)
#001 The experiment complete! expo=2, X=4, Y=4, type=NORMAL
——————————————————————————
FIXED POINTSというのは,TRANSITIVEの対語のようだ.PrintOrbitsの中で使われている.ISOMORPHというクラスにはarrayが3つ,matrixが3つ,Vectが7つ入っていて,OrbitsというのはそのうちのOというVectを指しているようだ.グローバル変数としてorbits0[256], orbits1[256]というのもある.これは解析もかなり難しそうだ…
PsiNumberというのが出てくるのだが,これは何だろう?PsiNumberというのはどうもグラフに関係しているようなのだが… GraphPsiNumberと並立してMatrixOmegaNumberというのも出てくる.Psi numberにはHorizontalとVerticalがある.マトリックスはpsiHとpsiVという2つの一次配列を持っている.これが一致する必要があるらしい.CompMatrixという関数では単純に2つのマトリックスのセルを比較している.マトリックスのタイプには以下がある.
- NORMAL:
- IRREDUCIBLE:
- SUBSYMMETRIC:
- CRYSTAL:
- SYMMETRIC:
- PARASYMMETRIC:
- COMPLETE:
- TRIFLE:
同型判定の方式として,①Mirroringと②Echoingの二種がある.MATRIXINVARIANTがオンのときは,マトリックスの不変量を求める方法が採用される.GetMatrixInvariantではデルタマトリックスというのを生成して,プサイ数とオメガ数を計算しているようだ.これらが一致すれば同型と判定されるのだろう.見通しが悪いので,使われていない関数はすべて廃棄してしまおう.
- ReverseCycle
- PartitionDeltaMatrix
- CanonicalLabeling
- StandardDeltaMatrix
- RemoveVertex
- RetrieveOne
- RetrieveVector
- Decending
- CheckComponentSize
- printCleavage
- Stocktaking
- loadWeightArray
- MakeWeightArray
- SubMatrixInventory
- subMatrixInventory
- ChainConnection
- CheckBrokenBlock
- CheckOmegaMatrix
- CheckBC
- MakeInventory
- TakeInventory
- BuildOmegaMatrix
- ExchangeBlocks
- FixPermutation
- GetOmegaValue
- InventoryPartition
- Homomorphism
- ShadowEchoing
- BreakInnocent
- CheckLeftRightDelta
- CheckPolymetrie
- DestructiveExperiment
- BlockInspection
- HomomorphismExperiment
- IsTriviallyHomomorphic
- IsTriviallyIsomorphic
- MatrixHomomorphism
- TestMatching
- TransposeMatrix
- printPolygram
- PrintPolygram
- DecompPolygram
- round
- checkpartition
- testpolygram
- checkblock
- CheckNullBlock
- checkzeroline
- checkvect
- checklinear
- CheckMatrixSize
- checkNullmatrix
- CompPItree
- checkoverrun
- dumpvector
- dumplarge
- complarge
- PsiNumberMethod
- InitializeExponent
- CompressPSIs
- CompressPsi
- swapstr
- PrintPartition
- Euclids
- MakeS4sample
- printVector
- printArray
- PrintArray
- InitializeMap
- compmat
- VeryfyMapping
- IsValidPermutation
- printhugenum
- printarray
- PrintResult
75本の関数ないし関数名を除去した.使われていないもので一部残したものもある.Euclidsはユークリッド互除法の実装だが,どこで使うつもりだったのだろう?homomorphism(準同型)に関する関数がいくつかあったが,結局実装しないことになったようだ.行列同型では演算を前提としていないので,準同型の出る幕はなかったのだろう.MakeS4sampleというのがある.S4と言えば4次の対称群ということになるのだが,その辺りも少しからんでいたのだろうか?KUEXPERIMENTというフェーズ名がある.KUexperimentというのが入っていた.KellyUlamという関数まであった.興味あるところだが,とりあえず消してしまった.⇒いや,残っている.
サンプルファイルが見つかった.こんな感じのデータだ.Graph Isomorphism : Counter Example Fri Sep 01 21:43:34 2023という表題が付いているので,「反例」ということになるが,多分,これは正規のデータだと思う.
2 1 2 0 2 2 0 0 1 0 2 2
0 1 2 1 0 1 0 2 2 1 2 2
2 0 0 2 1 0 1 1 0 0 2 1
1 1 1 1 1 2 0 1 1 1 2 1
2 2 0 0 2 2 1 1 1 0 1 0
0 1 0 2 1 1 0 0 2 2 0 0
2 1 0 0 1 1 2 1 2 2 1 1
0 0 2 0 0 2 2 1 1 2 2 0
0 1 1 2 0 1 2 2 2 2 1 0
2 2 1 0 2 1 1 0 1 1 1 2
0 1 1 0 0 1 1 0 0 0 2 1
0 0 0 0 0 1 2 0 1 1 2 0
これで見ると,行ヘッダや列ヘッダを持たない行列の中身だけが格納されたファイルになっている.行列の中身は数字だが,これはコードとして読んでもよいと思う.従って,現時点で考えている「同型な行列」のイメージとかけ離れたものではない.もう一つのサンプルは:
1 0 1 1 1 2 1 1 2 1 1 1
0 2 0 1 2 1 2 1 1 2 1 1
2 1 0 1 0 2 2 1 0 0 0 1
0 2 2 1 2 2 0 0 2 1 0 0
0 1 1 0 1 1 2 2 1 1 2 2
0 1 1 0 0 2 0 1 1 0 1 0
0 0 2 0 0 2 2 2 2 1 1 2
0 2 0 0 1 2 0 0 1 1 0 0
2 0 0 0 2 0 0 0 1 2 1 1
2 2 1 2 2 1 0 0 1 2 1 0
1 0 2 2 1 2 0 2 1 2 1 0
0 1 0 1 0 1 2 0 2 1 2 2
この2つを比較すると同型だという答えが返ってくる.多分,以下がその全単射になっているはずだ.
O0: 6 8 1 9 3 12 5 2 4 10 11 7
O1: 11 12 4 6 3 5 10 7 8 9 2 1
ただし,これが同型写像であるとすると,行と列には同じラベルが振られているということになる.実際にこの順序で並び替えて,同一であることが確認できるとよいのだが… これを一瞬で計算できるとすれば,かなりのものだ.拾い上げる価値はあるような気がする.たとえ,完全なものではなかったとしても実用的な有用性は十分あると思う.ただし,限界があるのではないか?この行列の中身である数字は2つの行列で共通でないと動作しないのではないだろうか?一つの群から派生した部分群の比較などならそれでも十分間に合うとは思うが,完全に文字コードに依存しない同型判定にはなっていないのではないだろうか?それができれば完璧なのだが,そもそもそんなことは可能なのだろうか?
いずれにしてもn!個の全単射をしらみつぶしに調べる方法に比べれば格段に有利な方法であることは間違いないと思う.