投稿者: babalabo

投稿日:

C#からC++の関数を呼び出すサンプル

以下の記事を参考にして，C#からC++の関数を呼び出すサンプルを作ってみた．　C#から、C++の関数の実行（関数）

とりあえず，説明通り動いた．この記事ではネィティブコードのDLLを生成し，それを呼び出すラッパクラスを別プロジェクトでビルドしている．DLLのヘッダでは以下を宣言して使っている．

#ifdef NATIVEFUNC_EXPORTS
#define NATIVEFUNC_API __declspec(dllexport)
#else
#define NATIVEFUNC_API __declspec(dllimport)
#endif

namespace Native
{
     // num個のint配列srcから、最大値とそのインデックスを探す関数です
     NATIVEFUNC_API void Max(int* src, int num, int* mx, int* mxIndex);
}

ラッパクラスの関数の中では以下のように生ポインタをピン止めするという操作を行っている．

void Wrapper::WrapperClass::Max(array<int>^ src, int num, int% mx, int% mxIndex)
{
     // ★ここがポイント
     // 実行中、ガベージコレクションされないように、pin_ptrを使って固定する
     pin_ptr<int> psrc = &src[0];
     pin_ptr<int> pmx = &mx;
     pin_ptr<int> pMxIndex = &mxIndex;

    // 自作関数実行
     Native::Max(psrc, num, pmx, pMxIndex);

    // ★ここがポイント
     // 固定解除
     psrc = nullptr;
     pmx = nullptr;
     pMxIndex = nullptr;
}

C++プロジェクトでは「シンボルのエクスポートにチェック」となっているが，VS2019の画面ではこのようなオプションは表示されない．また，C++では出力ファイルをDLLとしているのに，ラッパクラスのプロパティ → リンカー → 入力 →追加の依存ファイルではLIBが設定されているというのもよく分からないところだ．

投稿日:

自己同型検定を一晩走らせてA4同型写像24個を出力した

A4の自己同型検定を一晩走らせて，恒等写像を含めて２４個の同型写像が出力されたが，完了までにはほど遠い．停止させてチェックしたところ「i」までは進んでいたので，半分くらいこなしたというところだろうか？少なくともS5くらいまでは計算できるようにしたいのだがほど遠い話だ．ELSIEは一般の行列の同型判定プログラムだが，準同型検定CSは本来群の検定を目的としたものであるから，単位元の存在は仮定してよいはずだ．従って，全置換のうち，先頭がaであるものだけを検査するというのでよいのではないだろうか？これならほどほどの時間で完了できる．A4なら10分も掛からないのではないだろうか？S5となるとそれでもほぼ不可能だが，S4なら何とかなるかもしれない．

どう改造すればよいか？ArrayList Createで渡す配列を最初から短くしておくのが一番手っ取り早い．Permutation.Printでリストを生成するときに書き戻せばよいのではないか？いや，それより確実なのは，全単射の生成で置換リストを生成するときに付け加える方が分かり易い．⇒しかし，この場合は全置換リストを生成する必要があるのではないか？対称群を生成するときなどは完全な置換リストが必要になる．

▲「置換リストを使う」設定で，自己同型検定→群同型判定で例外が発生する．⇒全単射の生成で落ちる．置換リスト = new string[m, n];で墜ちている．m=479001600, n=12だ．sizeof(string)は取れないので，sizeof(long)で代用すると，18,446,744,072,449,064,960で到底カバーできる数字ではない．

「置換リストを使う」設定のときの論理は現行のママとし，使わないときには Permutation.Creatの引数で調整することにする．⇒実装した．A4でテストしてみる．⇒最初の３つまではすぐに出たが，その後が続かない．相当な時間が掛かりそうだ．13:10開始ということにして時間を測ってみることにする．⇒完了した．所要時間は１時間半．まぁまぁの成績と言ってよいだろう．

#1 Permute 自己同型：b,c,d,e,f,g,h,i,j,k,l,
#2 Permute 自己同型：b,c,i,h,g,k,j,l,e,f,d,
#3 Permute 自己同型：b,c,l,j,k,f,e,d,h,g,i,
#4 Permute 自己同型：c,b,d,f,e,j,k,l,g,h,i,
#5 Permute 自己同型：c,b,i,g,h,e,f,d,k,j,l,
#6 Permute 自己同型：c,b,l,k,j,h,g,i,f,e,d,
#7 Permute 自己同型：e,g,d,k,c,h,f,l,b,j,i,
#8 Permute 自己同型：e,g,i,b,j,c,k,d,f,h,l,
#9 Permute 自己同型：e,g,l,f,h,j,b,i,k,c,d,
#10 Permute 自己同型：f,j,d,h,b,k,e,i,c,g,l,
#11 Permute 自己同型：f,j,i,e,k,g,c,l,h,b,d,
#12 Permute 自己同型：f,j,l,c,g,b,h,d,e,k,i,
#13 Permute 自己同型：g,e,d,c,k,b,j,i,h,f,l,
#14 Permute 自己同型：g,e,i,j,b,f,h,l,c,k,d,
#15 Permute 自己同型：g,e,l,h,f,k,c,d,j,b,i,
#16 Permute 自己同型：h,k,d,g,j,e,b,l,f,c,i,
#17 Permute 自己同型：h,k,i,f,c,j,g,d,b,e,l,
#18 Permute 自己同型：h,k,l,b,e,c,f,i,g,j,d,
#19 Permute 自己同型：j,f,d,b,h,c,g,l,k,e,i,
#20 Permute 自己同型：j,f,i,k,e,h,b,d,g,c,l,
#21 Permute 自己同型：j,f,l,g,c,e,k,i,b,h,d,
#22 Permute 自己同型：k,h,d,j,g,f,c,i,e,b,l,
#23 Permute 自己同型：k,h,i,c,f,b,e,l,j,g,d,
#24 Permute 自己同型：k,h,l,e,b,g,j,d,c,f,i,

いよいよ，ELSIEの登場ではないだろうか？ELSIEはプロジェクトとしてはすでに組み込まれているのだが，C#からどう呼び出せばよいのだろうか？マネージドからアンマネージドなので何かラッパーのようなものが必要になるのではないかと思うのだが… ⇒そもそも，#include プリプロセッサディレクティブがない．⇒少なくとも，下記のような仕掛けが必要なようだ．

extern “C”             //No name mangling
__declspec(dllexport)  //Tells the compiler to export the function
int                    //Function return type    
__cdecl                //Specifies calling convention, cdelc is default,
                        //so this can be omitted
test(int number){
     return number + 1;
}

ゼルコバの木ではどんなことをやっていたのか見てみよう．ExporoClasses.hというヘッダファイルがある．冒頭で，

#if defined(ZELKOVA_EXPORTS)
#define _EXPORTCLASS __declspec(dllexport)
#else
#define _EXPORTCLASS __declspec(dllimport)
#endif /* ZELKOVA_EXPORTS */

でEXPORTCLASS を定義している．ZELKOVA_EXPORTSを使って，dllexportとdllimportを切り分けている．どういう使い方をするのかは，いまいち分からない．ZELKOVA_EXPORTSは comdebug.h で定義されている．コメントに「COMDEBUG: _EXPORTCLASSの出入りの方向を決める：この行はExportClasses.hの前に置かなくてはならない！」とある．ExporoClasses.hには外部インタフェース用のクラスが各種定義されている．すべて，class _EXPORTCLASS PERSONAL のようにEXPORTCLASS として立てられている．

もうひとつ，ZelkovaExports.hというヘッダファイルがある．ここでも同種のマクロが定義されている．

#if defined(ZELKOVA_EXPORTS)
#define _EXPORT extern “C” __declspec(dllexport)
#else
#define _EXPORT extern “C” __declspec(dllimport)
#endif // ZELKOVA_EXPORTS

このヘッダファイルには，

_EXPORT long __stdcall GetViewRect(CRect *viewrect);

のような形式でDLLインタフェース関数が列挙されている．この関数の実装は，KeizuDLL.cppにあり，

long __stdcall GetViewRect(CRect *viewrect)
{
     AFX_MANAGE_STATE(AfxGetStaticModuleState());
     probe(GetViewRect)
     ASSERT_NEVER (!TreeView)
     *viewrect = TreeView->ViewRect();
     return 0;
}

のようなややこしいことをしている．なぜか，AFX_MANAGE_STATE(AfxGetStaticModuleState());のようなお呪いが必要とされている．このような宣言はextern “C” {}というブロックの中で行われているという点もポイントだ．

ZelkovaGC.hでは，namespace ZelkovaBetaというのが定義されている．このヘッダファイルにはExportClasses.hとZelkovaExports.hが#include されていて，参照できるようになっている．namespace ZelkovaBetaの中にはVBから参照されるクラスが定義されている．VBとC#はほぼ同等なので，ここまでやらなくてはならないのではないか？DLL内の関数名などをどう参照すればよいのか？DLLをリンクするだけで参照できるようになるのだろうか？namespace はC++で宣言できる．これだけで済むのなら好都合なのだが…

もう一つ問題がある．matrixはhugenumの行列になっている．これをcpp_intに切り替えるか，ないしC#に持ち出してBigIntegerが使えるようにしなくてはならない．ELSIEは４つのC++ファイルからなっている．これをまるごとC#に移すというのはちょっと二の足を踏んでしまう．まず，最初にこれをcpp_intに置き換えるところから始めた方がよいのではないか？仮に最終的にC#に持ち出すことになったとしても，そこまでやってあれば，かなり対応し易くなるはずだ．しかし，そもそもmatrixをhugenumにする必要が本当にあるのだろうか？PSI数などが大きくなるのは当然であるとしても，行列本体に巨大数を格納するというのは必要なのだろうか？

matrixとarrayはhugenumだが，それと別にMatとVectというのがある．これらはintの配列だ．ISOMORPHというクラスにはarrayが３つ，matrixが３つも含まれている．ISOMORPHのinitializeでは最初に引数で渡されたMatを内部のMatメンバーにコピーしている．つまり，検体となる行列は本来 int 配列なのだろう．従って，外部とのインターフェースはこの行列を渡せばよいということになるのではないか？⇒とりあえず，外部から２つのMatデータを与えられればMatrixComparisonと同等の検査を実行できそうだ．とりあえず，ELSIEの持っている６つの処理をC#から実行できるようにすればよいのではないか？

投稿日:

置換リストを使う/使わない

「A4は自己同型群ではない」という表示が出るのは，群同型判定で真を返していないためだ．「置換リストを使わない」は真になっているので，実行されているのはPermutation.Createだけだ．この関数はArrayListを返しているだけなので，同型判定の結果についてはここでは何も言えない．対象となっている準同型にはアクセスできるので，ここに結果を格納できるようにしておこう．⇒結果は同じだ．A4は恒等写像以外に自己同型となるような置換（全単射）を持っていないように思われる．⇒V4で試してみたが結果は同じだ．

おかしい．どこか壊してしまったのだろうか？「置換リストを使わない」オフで置換数不一致が発生してしまった．⇒肝心なところが止めてあった．これを復活させて，V4は自己同型群であるということになった．V4は群同型写像を５つ持っている．

#1. 群同型写像：map1=1,2,4,3, map2=1,2,3,4,　(3 4)
#2. 群同型写像：map1=1,3,2,4, map2=1,2,3,4,　(2 3)
#3. 群同型写像：map1=1,3,4,2, map2=1,2,3,4,　(2 3 4)
#4. 群同型写像：map1=1,4,2,3, map2=1,2,3,4,　(2 4 3)
#5. 群同型写像：map1=1,4,3,2, map2=1,2,3,4,　(2 4)

これは正しいのではないかと思う．従って，「A4は自己同型群ではない」という言い方は，少なくともこの場では通用する．⇒従来論理，つまり「置換リストを使う」の答えが正しいとすれば，「置換リストを使わない」では間違えていることになる．見直しが必要だ．その都度テストするのとまとめてテストするので結果が異なるというのはおかしい．パラメータの渡し方が悪いのだろうか？⇒どこかで群Aの台集合を書き換えている！⇒群Aの台集合と一致するか否かの検査をパスするようにして同型判定に入れるようになったが，今度は２４個の全単射のすべてが同型ということになってしまった．

従来論理では５個のみということになっているので，これは明らかにおかしい．準同型検定でAとBのmapが同一になっている．これもかなりおかしい．この動作は「置換リストを使わない」場合に限られている．どこかで余分なことをしているようだ．どうも，この論理には何かかなりひどい欠陥があるように思われる．おそらく，配列の参照に関わる事象と思われるが，使いまわししているアドレスが参照になっていて，書き込まれているような感じだ．⇒map1とmap2が繋がってしまっている．map1にはA.台集合，map2にはB.台集合が入っている．

おそらく，最初からA=Bになっているのだろう．準同型や写像のコンストラクタで＝ではなく，コピーしなくてはダメなのではないか？⇒確かにそのようだ．かなり面倒な話になってきた．すべてのクラスを作り直さなくてはならない．一度終了して出直すことにしよう．

▲群の検査でスタックオーバーフローが発生した．⇒群の検査の中で自己同型検定を実施しなければスタックオーバーフローは起きない．

ようやくノーマルな動作になった．V4では恒等写像を含め６個の同型写像が確認された．自己同型検定では写像と準同型をnewで生成しているが，準同型のコンストラクタでは群１，群２，写像をそれぞれ生成している．これは参照でもよいのでは？⇒問題なさそうだ．これでよいのではないかと思う．共役変換検定も復活できた．A4をテストして恒等写像を含め３つの同型写像が検出されたが，その後無応答の状態に陥った．

#1 Permute 準同型：a,b,c,d,e,f,g,h,i,j,k,l,
#2 Permute 準同型：a,b,c,i,h,g,k,j,l,e,f,d,
#3 Permute 準同型：a,b,c,l,j,k,f,e,d,h,g,i,

この後どのくらい掛かるのか見当も付かない．⇒一昼夜放置して，#24まで進んだ．

#1 Permute 自己同型：a,b,c,d,e,f,g,h,i,j,k,l,
#2 Permute 自己同型：a,b,c,i,h,g,k,j,l,e,f,d,
#3 Permute 自己同型：a,b,c,l,j,k,f,e,d,h,g,i,
#4 Permute 自己同型：a,c,b,d,f,e,j,k,l,g,h,i,
#5 Permute 自己同型：a,c,b,i,g,h,e,f,d,k,j,l,
#6 Permute 自己同型：a,c,b,l,k,j,h,g,i,f,e,d,
#7 Permute 自己同型：a,e,g,d,k,c,h,f,l,b,j,i,
#8 Permute 自己同型：a,e,g,i,b,j,c,k,d,f,h,l,
#9 Permute 自己同型：a,e,g,l,f,h,j,b,i,k,c,d,
#10 Permute 自己同型：a,f,j,d,h,b,k,e,i,c,g,l,
#11 Permute 自己同型：a,f,j,i,e,k,g,c,l,h,b,d,
#12 Permute 自己同型：a,f,j,l,c,g,b,h,d,e,k,i,
#13 Permute 自己同型：a,g,e,d,c,k,b,j,i,h,f,l,
#14 Permute 自己同型：a,g,e,i,j,b,f,h,l,c,k,d,
#15 Permute 自己同型：a,g,e,l,h,f,k,c,d,j,b,i,
#16 Permute 自己同型：a,h,k,d,g,j,e,b,l,f,c,i,
#17 Permute 自己同型：a,h,k,i,f,c,j,g,d,b,e,l,
#18 Permute 自己同型：a,h,k,l,b,e,c,f,i,g,j,d,
#19 Permute 自己同型：a,j,f,d,b,h,c,g,l,k,e,i,
#20 Permute 自己同型：a,j,f,i,k,e,h,b,d,g,c,l,
#21 Permute 自己同型：a,j,f,l,g,c,e,k,i,b,h,d,
#22 Permute 自己同型：a,k,h,d,j,g,f,c,i,e,b,l,
#23 Permute 自己同型：a,k,h,i,c,f,b,e,l,j,g,d,
#24 Permute 自己同型：a,k,h,l,e,b,g,j,d,c,f,i,

まだ，初期画面は出ていない．

投稿日:

置換リストを用いずに同型検定を実施する

A4の置換リストを保持しようとすると，479001600ｘ12ｘStringのサイズを持つ配列を用意しなくてはならない．これはS4の場合などに比較すると十分実現できる範囲であるように思われるが，OutOfMemory例外が起きてしまう．もしかすると対処策もあるのかも知れないが，ここではあきらめて，先に進むことにする．つまり，置換リストを用いずに，個別に置換（全単射）を生成して，その都度同型検定を実施するという方法だ．もし，同型写像が見つかればほどほどの時間で判定が完了する．同型でない場合には全置換を検査しなくてはならないので，相応の時間が掛かることは避けられないが，それでも実行終了することはできるだろう．⇒一応．準備は整った．一応動いている模様だ．

A4は自己同型群ではないということになったが，正しいだろうか？wikiによれば，「一般の n > 3 (n ≠ 6) に対する An の自己同型群は対称群 Sn で、内部自己同型群として An を外部自己同型群として Z/2Z を持つ。このとき外部自己同型群は奇置換による共軛変換から得られる。」となっている．どうもまだよく分かっていないことが多過ぎる…

投稿日:

さて，Permutationクラスでは

さて，Permutationクラスでは長さが13位上の置換を生成できないというのはやむを得ないとして，ELSIEをその代用とすることが果たして可能なのか？ELSIEの論理では行列のセルの値は整数であり，その絶対値が意味を持っていると考えられるから，値の範囲が異なる行列を比較することはそもそも不可能なのではないか？文字列を数値に置き換えることはできたとしても，２つの行列でまったく異なるコード系が使われている場合には対処できないと思われる．たとえば，S4の２つの部分群は位相同型であったとしても，数値の範囲はまったく異なるはずだ．

サンプルを修正してテストしてみた．example0.maxの１をすべて３に書き直したサンプルはexample0.maxと同型と認定された．これと同型のexample1.maxでも同じ結果になった．別の数字を入れたもの，同じ数字でも値を変えたものは見破られた．これはもしかすると使えるかも知れない．int MatrixIsomorphism(int N, ISOMORPH *p0, Mat& d0, ISOMORPH *p1, Mat& d1)の動作をチェックしてみよう．

この関数は与えられた２つのマトリックスd0, d1からISOMORPHを生成/検定している．ELSIEが使えそうな見込みが出てきたので，準同型検定にプロジェクトとして組み込むことにする．⇒ElsieComeBackプロジェクトを準同型検定CSに組み込み，DLLを生成するような構成とした．これで，C#からELSIEの関数が呼び出せるようになればよいのだが…

S4ではエラーが出てしまうので，A4を生成するようにしてみたが，かなり時間が掛かる．時間が掛かるだけでなく，例外が発生した．OutOfMemoryだ．

image

ヒープを大きくするなどなにか対策はあるのかも知れないが，やむを得ない．⇒A4の群検査が失敗したあと，もう一度ボタンを押してA4を再検査しようとしたら，「群A4は結合法則を満たさない：A=b B=b C=f (AB)C=f A(BC)=a」で抜けてしまった．これはなぜか？⇒多分乗積表が作り切れなかったのだろう．A4を群として構築したことはこれまでなかったのだろうか？もう少し小さいサンプルで試してみよう．

▲V4を初期生成して群の検査でエラーになった．「インデックスが配列の範囲外です」

image

自己同型検定→群同型判定で例外が発生している．置換のダンプで失敗しているようだ．⇒VBのUBoundでは最大インデックスを返していたので，その値で配列にアクセスできたが，GetLengthでは長さを返しているので，一つ小さくする必要がある．⇒UBoundが使われていた箇所を点検する必要がある．⇒片付けた．

メモリ不足はPermutationで起きている．プロセスメモリの４GBをほぼ使い切っているが，全メモリ１６GBのうち，まだ５．６GBは残っている．⇒Permuteの入口でダンプしたり，DoEventsを実行したりすると，このメモリ不足は発生しなくなる．ダンプを実行した場合には，メモリ使用量はほとんど増加しないが，処理は相当遅くなるものと推定される．DoEventsを実行した場合には，メモリ使用量は増加の傾向が見られるが，その傾きはきわめて緩やかで，おそらくA4の置換をすべて列挙するまで停止することなく走り続けることができそうだ．

これはどういうことかというと，４GBのメモリを食っているのは一重にOSのメモリ管理の非力の所為であると言って過言ではない．つまり，GCにはそれなりの時間が掛かるため，完全なガベージコレクションができていないということを意味する．これは前々から分かっていたことだが，64ビットになって２GBの制約から解放されたにも掛かわらず，ほとんど進歩していないと断じても間違いではない．我々の参照管理を適用すれば，100％の完全なガベージコレクションを実現可能であることを考えると，これは現行のOSの大きな欠陥とみなしても差し支えないと思う．この意味では我々がやってきたことは間違っていなかったと断言できる．⇒いや，そこまで言うのは言い過ぎかもしれない．

メモリ使用量の増加の傾きが小さいのは，単純に時間が掛かっているというだけだろう．いずれにしてもメモリを実消費していることは間違いないのだから，いつかはメモリ不足の状態になるに違いない．24!というのはとてつもなく大きな数である．620448401733239439360000ｘ１行分のメモリということになれば，GBでは到底追いつけないことは確かだ．置換を生成するだけでよいのなら，必ずしもメモリは必要ない．その都度消費してしまえばよいというだけの話だ．

つまり，Permuteの中で実質的な検査を行うことができれば，メモリの浪費は防ぐことができる．もし，「自己同型」というのが，「恒等写像以外の同型写像を一つでも持つ」ということでよいのなら，おそらく検査にそれほどの時間を費やす必要もなくなるのではないだろうか？もちろん，同型でない場合には最後までやらなくてはならないことになってしまうが，それもある程度までは事前検査で弾くことは可能であると思われる．A4の場合は，m=479001600なので，メモリへの書き込みを実施しなければそこそこの時間で完了する．

ただし，さすがに479001600ｘ12のマトリックスは生成できない．

投稿日:

VB.NETのコードをC++に移植する

C++にboostを組み込んで，cpp_int（巨大整数）を扱うことができるようになった．さて，ここからどちらの方向に進めばよいのだろう？ELSIEは行列同型判定アプリなので，現在VBで開発している準同型検定とリンクさせることが目標ではあるが，どこをプラットフォームとすればよいのかが問題だ．ELSIEをVBから呼び出さるように作り込むという方向と，準同型検定をC++に移植するという２つの方向が考えられる．究極の目標が，NODULEを基底クラスとする統合的な処理系を作り上げることにあるとすれば，そのもっとも現実的な方向はVBを捨ててC++に乗り換えることではないか？

boostにはグラフ理論周りの関数もかなり整備されているので，うまくゆけばこれらをそっくり利用することも考えられる．準同型検定のソースは現在1200行くらいなので，移植するというプランの現実性は十分ある．VB,BETとC#の相互変換ツールというのがある．VS 2008には実装されていたようだが，すでに廃止されているが，それに替わるものがオンラインで使える可能性がある．

Telerik Code Converter
http://converter.telerik.com/

SharpDevelopというツールもある．ただし，これも新しい版では廃止されてしまっているようだ．また，対象となるプロジェクトもVS 2015までのようだ．Language Convertプラグインというのもある．これはVSのプラグインだろうか？dnSpyというツールは双方向の変換ができるようだ．IL Spyというのもあるらしい．先頭のTelerik Code Converterというのをオンラインで試してみた．ファイル１本分を黙って変換してくれた．ただし，一部に変換に失敗したところもあるようだが…　十分間に合うのではないだろうか？

C#のプロジェクトには大別して３種ある．①Windows フォームアプリケーション，②Windows フォームアプリ，③WPFアプリケーション．①ｔ②の相違点は.NET Frameworkを使うか？.NET Core を使うかという違いだ．.NET Frameworkは4.8で終了ということになっているので，将来的な問題がある．②の場合には，.NET CoreがWindowsに標準装備されていないという問題がある．③のWPFというのは最新のテクノロジーでGUIとロジックが完全に分離したものになる．

ただし，これまでのようにツールボックスからコントロールからドラッグ＆ペーストなどのことができなくなり，すべてXAMLで記述しなくてはならない．③ではGDIではなくDirect 3Dが使われているので，描画はより強力なものになることが期待できる．将来的にはWindows App SDKを使うという方向性が出されており，今後どうなるかは今のところ未定である．とりあえず，①のWindows フォームアプリケーションでゆくしなかいのではないだろうか？⇒初めてのC#プロジェクトを立ち上げてみた．何とかなりそうな気配ではある．

▲ArrayListというクラスが未定義になった．⇒C#にもArrayListというクラスはある．⇒using System.Collections;で解消した．

▲private var S4の置換 = new 置換(“S4の置換”, 4);で「キーワード ‘var’ は、ローカル変数宣言内またはスクリプト コード内でのみ有効です」⇒var→置換で解消した．

▲「’共役変換検定’ は ‘メソッド グループ’ であるため、これに割り当てることはできません」⇒VBではファンクション名に値を代入して返すようになっているが，この方法は通用しない．C#では明示的に戻り値を返す必要がある．⇒対処した．

▲public static string KeyIndex(ref string[] map, string key)の戻り値がstringになっている．⇒KeyIndexには２つある．写像クラスと群クラスのものだ．Public Function KeyIndex(key As String) As Integerは群で，Shared Function KeyIndex(ByRef map() As String, key As String) As Stringは写像クラスだ．共役変換検定の中では写像クラスの関数を呼び出している．明らかにこれは誤りだ．というか，多分戻り値をintで取り出しているのが誤りなのだろう．VBのソースコードを修正しておこう．⇒いや，違う．関数定義の方が間違っている．実際のコードでは整数を返している．⇒対処した．

▲public static void Fact(object n)　この関数はbigIntegerを返すものであるはずだ．⇒この関数はどこかから拾ってきたものではなかったろうか？引数も戻り値も型なしだ．とりあえず，intを引数としてintを返すものとしておく．ただし，これは巨大数になる可能性があるので，BigIntegerとした方が無難かもしれない．60!で10進81桁になる．しかし，この値は置換クラスの変数mに格納されるものなので，そこまで大きくなることを想定していないのではないか？⇒これは後で見直すことにして，ここでは保留としておく．

▲string[] listtop = list(0);でエラーになる．⇒list[0]なのではないか？⇒そのようだ．修正して解消した．

▲public void リストに登録あり(string[] list, string key)⇒戻り値の型指定なし⇒ブール値を返すように修正．

▲配列の初期化でエラーが出ている．string の２次元配列だ．「配列初期化子は変数かフィールド初期化子の中でのみ使用できます。new 式を使用してください。」以下のような式が通らない．

private 群 S2 = new 群(“S2”, 2, new[] { “1”, “-1” }, new[] { { “1”, “-1” }, { “-1”, “1” } });⇒new[] →new[,]として解消した．

▲型 ‘int’ を ‘bool’ に暗黙的に変換できません→対処した．

▲ int rows = Information.UBound(table, 1); のような変な構文が出てきた．C#にはUBoundという関数はないのだろうか？⇒GetLength
で代用する．⇒UBoundの次元は１発進だが，GetLengthでは０発進．

▲「現在のコンテキストに ‘Strings’ という名前は存在しません」⇒Strings.Format→String.Format

▲C#ではMsgBoxがMessageBoxになる．⇒MessageBox.Showを使う．⇒エラーメッセージはe.Messageで取り出す．

エラー処理を除いてすべてのコンパイルエラーが消えた．⇒とりあえず，画面を整備して動かし始めた．

▲Permutation::Createで例外が発生する．⇒配列サイズが制限を超えている．array.Length=24となっているが，制限は１３までだ．S4の乗積表を生成しようとしているのだが，S4の元は24個あるので，24!=620,448,401,733,239,439,360,000にもなり，到底カバーできない．しかし，群S4はこれまでにも生成したことはあったのではないだろうか？⇒いや，おそらくやっていないと思う．A4の群検査でハング状態になっている．A4くらいまではこなしていたような気もするのだが…

準同型検定ではほとんどログを取っていないので，進行状況がほとんど分からない．多少のところはFBに投稿していたかもしれないが… コストが掛かっているのは自己同型検定なので，もしかすると，これまでは止めてあったのかもしれない．いや，おそらくそういうことだったのではないか？ELSIEを引っ張りだしてきたのは，到底カバーできないというのが発端だったはずだ．従って，この問題を解決するには，ELSIEを整備して実用化するしかないと思う．

これで目標が定まったと言えるのではないか？

投稿日:

ELSIEのグラフ同型判定機能

ELSIEの６番目のオプションである 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を入力すると処理を打ち切って，メニューに戻れるようにした．これでグラフ同型検定はある程度使い物になるようになった．

投稿日:

boost のインストールに成功した！

boostをインストールしてみたのだが，どうしても include path が通らないので，vcpkg というツールを使ってみた．これは，多分マイクロソフトの製品ではないかと思われるが，サードパーティ製の規模の大きいパッケージをインストールするためのツールで，これを使えば整合的なインストールができるというのが謳い文句だ．vcpkg を使うためにはまず，git にアクセスできる必要があるので，git をダウンロードしてインストールした．https://git-scm.com/ この後，git を起動してコマンドラインから以下を実行して，vcpkg をインストールする．

＞git clone https://github.com/Microsoft/vcpkg.git

ついで，以下を実行してvcpkgをビルドする．

＞.\vcpkg\bootstrap-vcpkg.bat

これで vcpkg がインストールできたので，以下を実行して boost をインストールした．

＞vcpkg install boost

これだけで boost のインストールが始まったので，おそらく git ないし vcpkg は boost のパッケージがどこに置いてあるかを知っているのだろう．というか，多分 boost は git のプロジェクトの一部なのだろう．インストールには1.1時間掛かっているので，かなりのボリュームだ．ただし，boost がどこにインストールされているのか分からないので，探し回ったところ，以下のフォルダに格納されていた．

C:\Users\babalabo\vcpkg\installed\x86-windows\include

多分ここを指定すればよいのではないかと思う．このフォルダの下にある boost にはすべての hpp ファイルが入っている．（boostのヘッダファイルは*.hではなく，*.hppという拡張子が付いている）DLL は vcpkg\installed\x86-windows\bin に，LIB はvcpkg\installed\x86-windows\lib にある．⇒expample というプロジェクトで試してみたが，ダメだ．どういうことだろう？もしかすると，もうひとつ実行する必要があるのかもしれない．これをやってみよう．

＞.\vcpkg\vcpkg integrate install　

これを実行して，以下が表示された．

C:\Users\babalabo>.\vcpkg\vcpkg integrate install
Applied user-wide integration for this vcpkg root.
CMake projects should use: “-DCMAKE_TOOLCHAIN_FILE=C:/Users/babalabo/vcpkg/scripts/buildsystems/vcpkg.cmake”

All MSBuild C++ projects can now #include any installed libraries. Linking will be handled automatically. Installing new libraries will make them instantly available.

多分，この効果は新しく作ったプロジェクトにしか効かないのではないかと思う．VS2017のC++によるデスクトップ開発というパッケージには，Boost.Testのテストアダプターというのが含まれている．つまり，Boost はVS2017にすでに含まれている可能性がある．

https://learn.microsoft.com/ja-jp/visualstudio/test/how-to-use-boost-test-for-cpp?view=vs-2022

Boost.Testというのは，テストのための特製のプロジェクトを立てるということのようで，ここではとりあえずは関係ないようだ．

プロジェクトを作り直した．今回は何も設定することなく完璧に動いた．さて，問題はBigIntが使えるかどうかだ．boostではこれをcpp_intと呼んでいるようだが… ⇒簡単に動いた．

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
namespace mp = boost::multiprecision;

int main()
{
     mp::cpp_int x = 1；
    for (unsigned int i = 1; i <= 100; ++i)
         x *= i;
        std::cout << x << std::endl;
}

これで準備は整った．いよいよELSIEの再生だ！

投稿日:

Boost C++ Libraries をインストールした

どうもいまいち，ELSIEの動作が分からない．オプション４のRead a matrix data fileでサンプルを読み込ませた場合でも，

p0:EchoingMethod: ._NORMAL_ (12,12,12)
orbits=FIXED POINTS

p1:EchoingMethod: ._NORMAL_ (12,12,12)
orbits=FIXED POINTS

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

Matrices are isomorphic: Required time=722449:06:01, N=12, M=48, axes=0, crack=0
Psi0=(4.3189128850862000E+13:43189128850862)
Psi1=(4.3189128850862000E+13:43189128850862)
#001 The experiment complete! expo=2, X=4, Y=4, type=NORMAL

のようなダンプが出る．２つの行列を扱っているようだが，p0, p1はどう違うのだろう？⇒２つ目の行列はShuffleで生成されたものだ．おそらく，これは行と列をランダムに入れ替えることに相当する操作と思われる．従って，２つの行列は当然同型と判定されなくてはならない．

方式はよく分からないが，ともかく与えられた行列からある種の不変量を計算し，それを比較することによって同型か否かを判定しているものと見られる．この不変量は巨大数となるので，hugenumというデータ型を自作して対応しているというのが現状のようだ．hugenumというのは倍倍精度実数と長長整数を組み合わせたもので，誤差が発生するのは避けられない．FIXED POINTS（固定小数点数）というのはおそらく，誤差が発生していないということを意味するのだろう．

この実装では「Echoing Method」というアルゴリズムが実装され，A1という記号が振られているが，A2は存在しない．Mirroring Methodというのは，MATRIXINVARIANTが定義されていないときに実行されるアルゴリズムと見られるので，不変量の計算を行わない別法と考えられるが，現状ではEchoing Methodに固定されているものと見られる．

ただし，Mirroring Methodの実装は残っていて，切り替えは可能な状態になっている．MATRIXINVARIANTをオフにすると，上記のプサイ数の計算は実行されないが結果は同じになるので，一応動いているものと見られる．⇒いや，プサイ数の計算は実行されているようだ．ダンプに含まれないだけではないか？２つの手法の相違点はよくわからないが，それほど大きく異なるものではないような気がする．

フェーズは以下の５段階に区分されている．{ INITIALIZE, KUEXPERIMENT, NUTSCRACKER, WUPINNOCENT, FASTREACTOR } 確かにこの辺りの用語には聞き覚えがある．どんな意味だったのかはよく覚えていないが… いずれにせよ，それなりに動作していると評価してよいのではないだろうか？このアプリのオプション６つのうち，３つはグラフに関するものだ．グラフは隣接行列として過不足なく表現できるから，グラフ同型問題を行列同型問題として解くというのは当然のアイディアだろう．我々は群論の問題に行列同型を適用しようと思っているのだが，群の乗積表は（多少特殊な）正則行列にほかならないのだから，解けて当然と言えるはずだ．

このアルゴリズムは十分な有用性を持っていると考えられるのでなんとか復活させたいものだ．どうすればよいか？自前のhugnumを使っている限り，限界に直面することは間違いないので，これをBigIntegerと置き換える必要がある．BigIntegerが使えるのは今のところVBとPythonだけだ．Pythonはどちらかというとあまり使いたくないので，そうなると，VBに移植するか，C++にBigIntを導入するかの２択ということになる．どちらが使い勝手がよいか？拡張性はどうか？BigIntはネット上に公開されているソースもあり，GitHubには複数のプロジェクトがあるので，導入はいつでも可能と言えるのだが…

現時点ではソースコードは111KBある．行数で3500行くらいだ．これをそっくりVBで書き直すというのは現実的に可能だろうか？不可能ではないとしても，相当なコストは覚悟しなくてはならない．それより，C++にBigIntを導入する方がましであるような気がするのだが… 現時点でのhugenumの廃止は不可避であり，不可欠であると思われる．

C#に移行するという選択肢はあるだろうか？C#はBigIntegerを持っていたはずだ．C#はVB.NETとも互換性があったのではないだろうか？C#でC++のネイティブコードが走るかどうか？が問題だ．それができるのであればC#に移行するというのはベストチョイスになる可能性はある．

もう一つの選択肢として，多倍長整数のライブラリをC++に組み込むという路がある．この種のライブラリは各種あり，一長一短と思われるが，Boost Multi Precision Library というのを見つけた．これはドキュメントが整備されており，かなり信頼度は高そうに見える．日本発のプロジェクトで高橋晶という人物がリーダーだ．これは買いではないだろうか？最新版は1.83.0 2023/08/11 リリースなのでプロジェクトは現在も活性状態にある．ダウンロードしてみた．

zipファイルを解凍して中に入っている bootstrap.bat を実行すると b2.exe が作られる．これをダブルクリックで実行したところ，インストールは実行されたようだが，VSから認識される状態にはなっていない．改め> .\b2.exe install -j2 –prefix=C:\Program Files \boost \boost_1_82_0 を実行してみたが，途中で止まってしまった．

don’t know how to make <e>Files\boost\boost_1_82_0
…found 1 target…
…can’t find 1 target…

PowerShellを使ってみる．結果は同じだ．管理者モードで実行してみる．⇒やはり，ダメだ．開発用のDドライブにインストールしてみよう．⇒今度はうまく行った．前回はファイルコピー時に出ていたコードが処理できないというエラーも解消し，完全にクリーンなインストールができた．あとは，これを参照できるようにするだけだ．問題はこれまでのコードと相性が合うかどうか？このプログラムは多分64ビット環境で動くようにインストールされていると思われるが，我々のプログラムのプラットフォームは基本的に32ビットシステムだ．開発環境が64ビットであっても32ビットコードを生成できないということにはならないが…

サイトにあったサンプルコードで動作確認しようとしてみたが，include パスが通らない…$(VC_IncludePath);$(WindowsSDK_IncludePath); の後に追加できるはずなのだが，認識されない．

投稿日:

行列同型判定プログラム ELSIE を動かす

Elsieを起動して，６．Random matrices を選択→matrix size→iteration countを入力したところで，例外が発生する．

image

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が３つ，matrixが３つ，Vectが７つ入っていて，OrbitsというのはそのうちのOというVectを指しているようだ．グローバル変数としてorbits0[256], orbits1[256]というのもある．これは解析もかなり難しそうだ…

PsiNumberというのが出てくるのだが，これは何だろう？PsiNumberというのはどうもグラフに関係しているようなのだが…　GraphPsiNumberと並立してMatrixOmegaNumberというのも出てくる．Psi numberにはHorizontalとVerticalがある．マトリックスはpsiHとpsiVという２つの一次配列を持っている．これが一致する必要があるらしい．CompMatrixという関数では単純に２つのマトリックスのセルを比較している．マトリックスのタイプには以下がある．

  • NORMAL:
  • IRREDUCIBLE:
  • SUBSYMMETRIC: 
  • CRYSTAL:
  • SYMMETRIC:
  • PARASYMMETRIC:
  • COMPLETE:
  • TRIFLE:  

同型判定の方式として，①Mirroringと②Echoingの二種がある．MATRIXINVARIANTがオンのときは，マトリックスの不変量を求める方法が採用される．GetMatrixInvariantではデルタマトリックスというのを生成して，プサイ数とオメガ数を計算しているようだ．これらが一致すれば同型と判定されるのだろう．見通しが悪いので，使われていない関数はすべて廃棄してしまおう．

  1. ReverseCycle
  2. PartitionDeltaMatrix
  3. CanonicalLabeling
  4. StandardDeltaMatrix
  5. RemoveVertex
  6. RetrieveOne
  7. RetrieveVector
  8. Decending
  9. CheckComponentSize
  10. printCleavage
  11. Stocktaking
  12. loadWeightArray
  13. MakeWeightArray
  14. SubMatrixInventory
  15. subMatrixInventory
  16. ChainConnection
  17. CheckBrokenBlock
  18. CheckOmegaMatrix
  19. CheckBC
  20. MakeInventory
  21. TakeInventory
  22. BuildOmegaMatrix
  23. ExchangeBlocks
  24. FixPermutation
  25. GetOmegaValue
  26. InventoryPartition
  27. Homomorphism
  28. ShadowEchoing
  29. BreakInnocent
  30. CheckLeftRightDelta
  31. CheckPolymetrie
  32. DestructiveExperiment
  33. BlockInspection
  34. HomomorphismExperiment
  35. IsTriviallyHomomorphic
  36. IsTriviallyIsomorphic
  37. MatrixHomomorphism
  38. TestMatching
  39. TransposeMatrix
  40. printPolygram
  41. PrintPolygram
  42. DecompPolygram
  43. round
  44. checkpartition
  45. testpolygram
  46. checkblock
  47. CheckNullBlock
  48. checkzeroline
  49. checkvect
  50. checklinear
  51. CheckMatrixSize
  52. checkNullmatrix
  53. CompPItree
  54. checkoverrun
  55. dumpvector
  56. dumplarge
  57. complarge
  58. PsiNumberMethod
  59. InitializeExponent
  60. CompressPSIs
  61. CompressPsi
  62. swapstr
  63. PrintPartition
  64. Euclids
  65. MakeS4sample
  66. printVector
  67. printArray
  68. PrintArray
  69. InitializeMap
  70. compmat
  71. VeryfyMapping
  72. IsValidPermutation
  73. printhugenum
  74. printarray
  75. PrintResult

７５本の関数ないし関数名を除去した．使われていないもので一部残したものもある．Euclidsはユークリッド互除法の実装だが，どこで使うつもりだったのだろう？homomorphism（準同型）に関する関数がいくつかあったが，結局実装しないことになったようだ．行列同型では演算を前提としていないので，準同型の出る幕はなかったのだろう．MakeS4sampleというのがある．S4と言えば４次の対称群ということになるのだが，その辺りも少しからんでいたのだろうか？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   

この２つを比較すると同型だという答えが返ってくる．多分，以下がその全単射になっているはずだ．

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

ただし，これが同型写像であるとすると，行と列には同じラベルが振られているということになる．実際にこの順序で並び替えて，同一であることが確認できるとよいのだが… これを一瞬で計算できるとすれば，かなりのものだ．拾い上げる価値はあるような気がする．たとえ，完全なものではなかったとしても実用的な有用性は十分あると思う．ただし，限界があるのではないか？この行列の中身である数字は２つの行列で共通でないと動作しないのではないだろうか？一つの群から派生した部分群の比較などならそれでも十分間に合うとは思うが，完全に文字コードに依存しない同型判定にはなっていないのではないだろうか？それができれば完璧なのだが，そもそもそんなことは可能なのだろうか？

いずれにしてもｎ！個の全単射をしらみつぶしに調べる方法に比べれば格段に有利な方法であることは間違いないと思う．

Proudly powered by WordPress