TC3000という呪われたサンプル

TC3000という呪われたサンプルの呪縛をなんとかして解かなくてはならない.TC3000の内容をまるごと包含しているTC4000などのもっと大きいサンプルは容易に描画できているのに,このサンプルだけは収束しないという理由を是が非でも突き止めなくてはならない.さもなければこのソフトは永遠に陽の目を見ることはないだろう.いや,むしろ,このようなサンプルを与えられたことは法外な幸運であったと考えるべきかも知れない.⇒多少の進展はあった.

TC3000は4720点のカードを含むゼルコバの木的には巨大系図だ.三極検定では系図図面上のすべての描画要素の座標を調整して「最適配置」を実現しようとする処理だが,下流での調整は上流にも影響を与え,上流での調整は下流にも影響する.さらに,「計算上の誤差」という問題があるため,完全な厳密値を用いると収束できない場合がある.この問題は系図木の規模が大きくなればそれだけ累積的なものになる.

TC3000サンプルの出力するADLファイルをテキストエディタで直接編集して,5461という終端ノードを除去してやれば,有限時間内(loopcnt=67)に描画することができる.テスト回数3000という設定ではその2倍の5999までの奇数がテストされるから,5461という奇数はテスト対象に含まれる.このノードは子どもを持たないので,ルートノード1の直下の子ども枠の中で配置上の制約を持たないいわば,フロート状態にあると言える.ただし,このTC3000-1サンプルを読み出すためには,MAXIMALGRAPH::MergeUpperSegmentで同一セグメントと認定されるための条件を緩和する必要があった.

MergeUpperSegmentでは,対象結婚枠の「結婚点一致」という条件が成立すれば,結婚枠とその吊元である親ノードを同一セグメントと認定する.正確には,「誤差の範囲で結婚点が一致し,かつ吊り位置の子ノードの人名枠と親ノードの人名枠が水平座標でみて交差していること」という条件だ.現行では「誤差の範囲」として3という数が採用されている.これを12まで緩和することでようやく解に収束した.

image

このサンプルにもう一度5461を1の子ノードとして追加すると,再び収束不能状態に戻ってしまう.ただし,ゼルコバの木では子ノードは兄弟ノードの末尾にしか追加できないので,末弟の85の後ろに続くことになる.この図式はオリジナルのTC3000よりは容易に解けそうに見えるのだが,なぜか失敗している.どのような機序でこのような無限ループが発生しているのかを解析したいのだが,何せサンプルが大き過ぎて手も足もでない.というか,途方もなく時間コストばかり浪費するものになってしまう.「手に負えない問題 (intractable problem)」の典型だ.

このような場合には「事象を再現する最小サンプル」を作成するというのが定石だ.そこで,手始めにまず,TC3000-1上で末弟ノードの85とルート1の親子関係を切断してみた.この図式はloopcount=42で描画できる.この図式にノード1の子どもとして「5461」を追加する.これをTC3000-1+1とする.これで,この系図の登録カード数は4720点に戻った.末弟ノードの「85」は1との親子関係は切断されているが,系統としては残っているので,もう一度1の子どもとして復活させると事象が再現してしまうことは明らかなので,別のカードとして性別が女子のカード「85」を追加してみる.これで登録カード数は4721点になるが,問題なく描画できた.この図面をTC3000-4722としておこう.

▲アプリ終了しようとして,下記のエラーが出た.このエラーは前にも見たことがある… メニューバーの「名前検索」に関係するものだ.

image

TC3000-4722の女子カードの「85」に子ども「X」を追加したところ,事象が発生した.つまり,事象を再現するためには,かならずしも「85」の長い子孫系は不要ということになる.⇒試してみよう.TC3000-1+1を開いて,「85」の直系血族を全削除してみる.⇒ハングしてしまったようだ.「85」はこの図面では別系統(孤立した系列)になっているので,描画には影響ないはずなのだが…制御を失っている.⇒1点づつ削除ですべてのカードを削除することはできた.カード数は4618点.このファイルをTC3000-4618.ZELとして保全しておこう.

▲TC3000-1+1から「85」の系統を全削除しようとしてハングした.

ルート1の子ども枠にもう一度「85」を追加して4619点とする.これをTC3000-4619.ZELとして保全しておこう.

image

この図面では「5461」と「85」はともに子どもを持たないので,前方の「5」に隣接するところまで前方配置されている.

image

この状態で「85」に子どもを一人追加してやれば事象が発生することは明らかだ.「5461」と「85」が並んでいる必要はないと推定されるので,「5461」を削除し,その上で「85」に子ども「X」を追加してみる.⇒確かに事象が発生する.TC3000-4618.ZELの「5461」に子ども「X」を追加しても同じことが起こるはずだ.⇒再発する.元の図面の裾の方をカットしてみた.かなり大きい部分をカットしているが,今回は問題なく削除できた.3637点になったので,これも保全しておく.

image

▲全削除したあとの画面下部のステータスバーで表示カード数の値が変化していない.全カード数は変化している.⇒TC3000-3637.ZELを開いてみたら,カード数は3638/3638になっている.つまり,全カード数の表示も間違っている.

TC3000-3637.ZELは実際には3638点なので,TC3000-3638.ZELとリネームしておこう.このサンプルの「5461」に子ども「X」を追加しても,事象は発生しなかった.つまり,このサンプルの裾刈りは少し過剰だったようだ.もう一度,TC3000-4618.ZELに戻ってカットし直してみよう.今回は少し控え目にしてみたがどうだろう?点数は4382と出ている.⇒ダメだ.やはり描画できてしまう.

image

少なくとも結婚枠が接触しているポイントはすべて残す必要がある.

▲拡張選択でマウスをウィンドウ枠外までドラッグしてスクロールしているように見えるが,実際には同じ場所に留まっている.

!とんでもないことが起こってしまった!ノードを削除してより簡略なグラフを作っている途中で事象が発生してしまった.少なくとも4165点より小さな木だ.この作業の途中で孤立点が2点発生していたので,何か操作を誤っていた可能性はある.せめて,そのノード番号だけでも控えておけばよかったのだが… いずれにしても,この事象はグラフの大小にはよらないということだけは確実だ.だとすれば,もっとずっと小さい反例サンプルを作れる可能性もあるということだが…

!助かった!タイムアウトでブレークしてくれた.

image

いや,三極検定にはタイムアウトはない.ループカウントオーバーだ.デフォルトではかなり大きい数になっているが,放置しておいたので,最後に脱出できた.⇒これで少しだけ小さい反例サンプルを手に入れることができた.カード数は4154だ.CT 3000-4154.ZELとして保存した.このサンプルではルート1が孤立ノードになっている.

image

「5461」の子どもとして追加した「X」は入っていない.1の子どもは5人で末尾の子ども「5461」は子なしだ.このカードを削除してみよう.⇒カウントオーバーになった.つまり,このカードは障害の原因ではない.しかし,出てきた図面には1しか表示されていない.⇒もう一度試してみよう.⇒今度は1枚だけカード数が減った図面になった.一応これも保存しておこう.CT 3000-4153.ZELだ.それにしても,なぜ1しか表示されなかったのか?⇒親族図だった可能性がある.実際,親族図(直系血族図)としたらそういう図面が出てきた.

image

ただし,実際には1にはまだ4人子どもが残っているので,図面としては間違っている.ループカウントオーバーで強制ブレークしているためとも考えられるが…それでも,おかしい.⇒全選択すると一覧表上では全選択状態になる.⇒倍率が100%だったためだ.倍率100%では1の周辺には何もない状態になる.兄弟連結線が描画されていないのはおかしいが,それはバグということかもしれない.「画面に合わせてズーム」で全体が見えるようになる.1の水平線は消えているが,それ以外は表示されているので,配置上の問題かもしれない.

「5」と「1」を切断したら,ノーマルに描画できた.ただし,親族図から全体図に切り替えて,下記のエラーになった.

image

これは単なる偶然だ. (snum == 96423)で停止するというパッチが入っていた.しかし,「1」→「5」を切断するだけでここまで形状が変わるのはなぜだろう?

image

「5」の系統を全削除してみよう.⇒またレッドラインオーバーになった.どうもなんだか訳がわからないことになってきた.「5」の全系統を削除したつもりなのだが,まだ「5」の子どもたちが残っている.削除操作は系統並び替えに先行して実施されているはずだから,系統並び替えでエラーになる動作の影響を受けていないはずだが…しかも,「5」自体残って,遠いところで孤立点になっている.前にも「全削除」でハングしたことがあるので,「5」とその下流(の一部)が残っているのは,「全削除」のバグである可能性はある.

image

このグラフは4017点だ.これも保存しておこう.⇒何か操作を間違えたのだろうか?「5」の系統を削除したつもりだったが,「1」が消えてしまっている.この4017点のノードはすべて「5」の子孫だ.おそらく「全選択」の誤動作と思われるが,図面を縮小表示しているので,「誤操作」の可能性もある.いずれにしても,この図面の先祖ノードが「5」であることは間違いない.「5」には子どもが6人いる.{ 13, 213, 3, 3413, 53, 853 }だ.5→853の関係を切断してみよう.

▲全削除ではなく,1点づつ削除するようにしてみたが,どうも一部やり残しが出ている模様だ.

▲ステータスバーの基準カード,現参照カードの値が実際と一致していない.⇒上記,表示カード数の更新の問題と同根だ.

3997点まで縮小したが,まだレッドラインは止まらない.先祖ノードは「5」に変わっている.一旦これを保存しておこう.「5」にはまだ,子どもが5人いる.末弟の53の系統を削除してみよう.⇒「53」の系統には1931点のノードが含まれるが,その血統図自体壊れている.これ自体が反例サンプルなので,「画面上のカードを保存」で保全しておく.ファイル名は53直系血族図.ZELとする.

他の系統も調べてみることにする.その前に「53」の系統を削除してしまおう.⇒SeriaiizeHeaderエラーが起きた.

image

緊急退避ファイルに保存できないというメッセージが出ていたが.そのあと,SaveFamilyTreeのエラーが出始めて,止まらなくなった.

image

image

このエラーは切りなく出てくるので,やむを得ずアプリを強制終了した.デスクトップには反例サンプルファイルが生成されているので,多分最後の状態を復元できるだろう.⇒いや,反例サンプルは大量生産されているが,どれも3997点で55系統削除後のファイルになっていない.「53直系血族図.ZEL」を調理してみることにしよう.このサンプルは1931点だ.このサンプルには「5」が残っていて,その子どもが「53」だ.「53」には子どもが4人{ 141, 2261, 35, 565 } あるが,末子の「565」を切断してみる.⇒この系統はかなり小さく,4人しか入っていない.全削除してみよう.

53→35のリンクを切断して,MargTakeChildのエラーになった.

image

このエラーは繰り返し出てきたが,なんとか収まった.どうも「35」の兄弟2人を除いたカードはすべて「35」の血統のようだ.「2261」の系統というのも残っている.これも削除しておこう.⇒これで1908点になったが,まだ崩れたままだ.

image

このサンプルをCT 3000-1908.ZELとする.先祖ノードの「35」には,子どもが5人いる.末子の「93」系統を抹消してみる.このノードは3倍数だ.その上の「5973」も同様だ.第3子の「373」を抹消する.この系統の部分図を取ろうとして下記エラーになった.

image

部分図が動作していないので,全体図に戻って「373」の直系血族図を取ることにする.「373」の直系血族図は描画可能なようだ.一応これを保存しておこう.いや,「373」ではなくて,「35」の直系図になっていた.おかしい.いつの間にが描画可能になっている.「93」と「5973」を削除した時点で障害は解消していたのではないか?現在,1906点なので,確かに2点しか削除されていない.もう一度やり直してみよう.このサンプルも一応CT 3000-1906.ZELとして保存しておく.

2点削除してもレッドラインオーバーになる.⇒多分,35→373の切断で解けたのだろう.⇒確かにそのようだ.いまのところ,この1906点が最小反例サンプルということになる.これをBUG3000-1906.ZELとして確保しておこう.「23」の切断でも不良が起こる.ただし,これを復元して兄弟順位が1493→ 373→ 23のように変化すると,収まってしまう.子ども並び替えで元の順序に戻すと,再発するようになる.しかし,長子の1493の切断では不良は解消せず,むしろもっと甚だしいものになる.この系統はおそらく削除できるのでやってみよう.

これで先祖ノード「35」の子どもは「23」と「373」の2人だけになった.おそらく,そのどちらを切断しても収まるようになっていると思われるが,一応確かめてみよう.いや,その前にこのサンプルを保全しておいた方がよい.現在1900点なので,BUG3000-1900.ZELとして保存する.この図面は信じられないレベルでひどいものになっている.

image

予想通り,上記2点の切断では不良は解消する.また,兄弟順序を逆転した場合には,下図のような図面が出力される.それぞれの系統を比較するために,先祖ノードの「35」を抹消した図面を作ってみよう.

image

2つの系統を分離したときの図面も見ておこう.ただし,この図面には少し疑問がある.

image

左側の図面は系統並び替えを実施していないように見える.確かにそのようだ.左の系統の先祖ノード「373」で系統並び替えすると,下図のようになり,しぼんでいた風船に空気を入れたように急膨張する.

image

系統並び替えは始系列だけが対象となるのではなく,すべての系列を対象としているので,独立系統だから系統並び替えが掛からないということはあり得ないと思われるのだが… これについては別途調べなくてはならないが,いまのところは三極検定が収束しない問題に集中することにする.BUG3000-1900.ZELは横に広がった図面になっているので,縦書きで表示してみることにしよう.縦方向なら多少寸法を大きくすることができる.人名枠高も少し増加させてみた.

image

中吊りにしたらどう見えるのかも試してみよう.⇒大勢には影響しない.「23」と「373」の2系統は世代高さに大きな差がある.もし,この2系統の干渉による現象であるとすれば,下の方の世代をカットしても事象は再現できるのではないかとも思われるのだが,やってみたところそのようなことはなかった.⇒いや,中吊りの設定ではあるが,ある程度までカットはできる.ただし,それを過ぎるとやはり解けてしまう.

image

この図面は1303点だが,一応取っておこう.GOO3000-1303.ZELとしておいた.下図を見ても分かる通り,23と373の系統的な(水平的な)干渉などではないことは明らかだ.

image

かなりひどい図面が出たので保存しておこう.UNDOが機能しているかどうかを確認してみよう.⇒問題なさそうだ.ただし,一度以下のようなエラーが発生した.

image

反例サンプルは1353点まで圧縮したが,そろそろ限界に近い.BUG3000-1353.ZELを極小な反例サンプルとして保全した.

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA