NHKの笑わない数学の第一弾は「確率論」，第二弾は「非ユークリッド幾何」でどちらもFBの数学グループで話題沸騰中だ．わたしも巻き込まれてだいぶ時間を消費してしまったが，本線に戻ろう．グラフの隣接行列から距離行列を生成する「ワーシャル・フロイド法」というアルゴリズムがあり，これをハミルトン閉路問題に応用するという課題がにわかに浮上してきた．ロバート・フロイドがこのアルゴリズムを最初に発表したのは1962年（それ以前にバーナード・ロイとステファン・ワーシャルが独立に発見している）で，現在の三重ループの形に整理されたのはピーター・インガーマン(1962)による．
このアルゴリズムは元々はオートマトンや正規表現の世界から渡ってきたようで，重み付き最短経路を多項式時間で計算することができ，さらに重みの和が負であるようなサイクルを含まないグラフのサイクル検出にも適用できる．また，推移的閉包の検出にも適用可能であるようだ．FBのコメントではこのアルゴリズムが「フロイド・ライブネッツアルゴリズム」という名称で紹介されていた．
しかし，どこを探してもそのようなものは出てこない．そもそも，Leibnizの名前をライブネッツとなまっている時点でおかしいのだが，上の記事では何度もこの名前で出てくるので執筆者はそれが正しいと確信しているようだ．この記事はHatena BlogのPyDocumentというシリーズものの一部で，『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』米田優峻著からの抜粋のように見えるが，ひょっとすると本当の著者はChatGPTなのではないだろうか？いかにもChatGPTのやりそうな間違いだ．
「GPU上での高速なブロック化フロイド・ワーシャル法」などというのもあり，かなり実用的に使われているアルゴリズムではあるようだ．
この記事では改良によって頂点数256～1024の場合は従来手法より高速化し，それ以上の場合は遅くなったと報告しているが，アリアドネの既存コードでは100点までしか計算できない．行列同型でもN=520を超えるサンプルではスタックオーバーフローが起きていたはずなので，500点を超えるサンプルを扱えるようにするのは難しそうだ．我々の目的からすれば，そこまで大きなサンプルは必要ないので，まぁ，500点が限界だとしてもとりあえず問題はないが…
アリアドネはFドライブのBACK2006-05-05/BABA_LABORATORYにある．このフォルダにはsamplesというフォルダがあるが，この中にはファイルが9452本も入っている．フォルダだけで13個もある．Narcissus，ないしNarkissosというフォルダが気になる．ハミルトン閉路問題ではないかという気がするのだが… 2002～2004年頃のものだ．どちらが最終版なのか？EXEのタイムスタンプはまったく同じなので時期は完全に一致している．前者はフォルダ数293, ファイル数19に対し，後者のフォルダ数は30．ファイル数は3566なので，おそらく，Narcissusを保存版としてくくり出したのだろう．
Narcissusのpublishというフォルダには，Narcissus.exeと一緒にELSIE.exeも入っている．このフォルダではELSIEとNAICISUSを並行して開発していたのだろうか？このフォルダのSOURCEにはELSIEのソースファイルしか入っていない．⇒走らせてみれば分かるだろう．
NarcissusというのはELSIEの一部だ．つまり，ELSIEはNarcissusを含んでいる．NarcissusはELSIEの機能のうち，グラフ同型検定に特化したものと言ってよい．ただし，この機能に関してはELSIEより少し詳細な設定ができる可能性がある．たとえば，表示モードを切り替えたり，ファイル形式の変換ツールが入っていたりする．まぁ，とりあえずはELSIEに含まれているものだけで十分だ．アリアドネのソースはVBだと思っていたが，C++だった．AriadneはELSIEとほぼ同等だから，準同型検定CSに組み組むのは難しくないと思われる．ただし，Ariadneを組み込むとこのプロジェクト全体の性格が大きく変化することになるので，フォルダ名を変えておくのが順当だろう．
もし，今後ハミルトン閉路問題が主題になるとすれば，日本語で「アリアドネ」ということでよいのではないだろうか？Ariadneの中にはAriadne100の他に，Asha, CounterStas, Hcp2Sat01というフォルダがある．Hcp2Satはハミルトン閉路問題をSAT（論理式の充足可能性問題）に変換するためのツールだ．CounterStasというのはよく分からないが，Stanislav Busyginとのやり取りに関係したものだろう．Ashaの中にはBlkblu.exeというのが入っているが実行できない．あとはBlkblu.cとテキストファイルが２本入っているだけだ．
Ashaというのは多分人名だと思う．確かにそうだ．Cソースの中に
printf(“\n%s v. %d, by Asha Goldberg\n\n”, progname, versionno );
という一行があるので，Asha Goldbergという人物が書いたコードだということが分かる．この頃はネット上にソースが転がっているという時代ではないので，多分本人から送ってもらったものではないかと思う．ただし，メールの現物は残っていない．このコードはハミルトン閉路の解法アルゴリズムだ．いや，ハミルトン閉路を含むグラフを生成するためのコードかも知れない．ブラックとかブルーなどの色を頂点に割り当てるようなことをしている．おもしろそうだが，読み切るにはちょっと時間が必要なのでパスしておこう．データファイルのフォーマットはアリアドネと完全に同じ，各行が#で始まる隣接行列だ．
ELSIEを組み込んだときの手順を忘れてしまった．既存のプロジェクトを組み込むというのが最速だが，新規プロジェクトとして登録してからファイルを追加していったような気もする．その辺り，ログに残っているだろうか？ELSIEのときは，boostというライブラリの組み込みで立ち往生していた．ELSIEのプロジェクトファイルはElsieComeBackフォルダに入っているので多分既存プロジェクトを組み込んだだけだと思う．その後，ソースファイルの入れ替えをやったような記憶もあるが… それよりも，Ariadneに入っている本体以外のフォルダを削除してディレクトリを１段上げておいた方がよい．つまり，アリアドネの直下にAriadne100が来るという構成だ．
準同型検定CSというソリューション名も変える必要がある．名前の変更は調整できたが，ビルド→実行でエラーが出てしまった．
アプリケーションのシングルスタートアッププロジェクトがElsieComeBackになっていた．準同型検定に変えて動作するようになった．⇒既存プロジェクトの追加で以下のメッセージが出た．
OKでビルドできたが，「D8016 コマンド ライン オプション ‘/ZI’ と ‘/Gy-‘ は同時に指定できません」のようなエラーになった．/Gy-というのは，関数レベルでリンクしないという意味のようだ．ZIはエディットコンティニュの意味だ．/Gy 関数レベルでリンクするに統一した．
▲i, j, k が定義されていない，ないし，未使用という警告⇒対処した．
▲warning D9035: オプション ‘Gm’ の使用は現在推奨されていません。今後のバージョンからは削除されます。⇒最小リビルドを有効にするという意味だ．⇒オフにしておこう．
▲This function or variable may be unsafeがかなりの件数ある．fopen, scanf, getch, strcpy, sprintf, ctime, strcpy,.. などだ．