▲ZTシステム構成図7.ZELの直系血族図 #1 couplingを軸線図法=1で開いて,NAMEBOX::MakeZeroTYWで停止する.MakeExtractBoxが空を返している.障害が起きているのはNAMEBOX #1272 UNDONODE(1)で,このノードもその人名リンクも軸線のマークを持っていない.⇒抽出の対象となっているのはこのノードではなく,このノードの右手枝にある結婚枠の中にある子どもノードonlysonだ.この子どもノードはMARGBOX::OnlyOneVisibleSonで取り出されている.⇒onlysonとその人名リンクが軸線である場合にはゼロ復帰するようにした.
これで基準ノード=#1 couplingの軸線図を出力することはできたが,明らかにこの軸線は短過ぎる.本来ならnodule→NODULEが図面の一番下に表示されなくてはならないところだが,noduleを多重表示することで「ごまかし」ている.現行の軸線決定アルゴリズムが誤っていることは明らかだ.軸線というのは,基準ノードの先祖ノードとその末裔ノードを結ぶ最長経路と定義される.親子関係(養親子関係を含む)は半順序関係であり,血統軸線図の中に埋め込まれた直系血族図という半順序集合上の「最長鎖」を求める問題として定式化できる.
これを一般化すれば,非循環的有向グラフの特定の2点を結ぶ最長経路を求める問題と言い換えることができる.これをさらに一般化すれば,有向グラフ上の任意の2点を結ぶ最長経路を求める問題となり,もし,この問題を解くことができればNP完全問題が解かれたことになると解される.あるグラフGの任意の2点間を結ぶ最長経路がグラフGのすべての点を含むものであれば,それはハミルトンパスであり,その2点を結ぶ有向枝があればハミルトン閉路になる.任意の2点間の最長距離を計算する多項式時間アルゴリズムが存在するとすれば,ハミルトン閉路問題はグラフGの節点数をNとして,高々そのO(N^2)倍で解けることになる.つまりNP=Pであることが証明されたということになる.
従って,「軸線ノード決定問題」,つまり,「半順序集合上の最長鎖を求める問題」がそんなに簡単に解ける訳がないと考えるのが順当だろう.現行アルゴリズムがどんなことをしているのか?どこで失敗しているのかを見ておくことにしよう.FindJikusenAncestorという関数だ.
- 基準ノードの自己ループ枝を登録する
- 直系血族図から親子関係を枝とするグラフを生成する
- 基準ノードに連結しているすべてのノードをマークする
- 基準ノードからのパスがない(端点にマークのない)枝を削除する
- 最長軸線の終端ノード(先祖ノードと末裔ノード)を決定する
- 最長軸線の終端ノード(先祖ノードと末裔ノード)をロックする
- 行き止まりノードの枝をグラフから削除する
- 枝が削除されている場合にはステップ3に戻る
- 余分な経路(重複パス)をカットして線形グラフに変形する
- 父系/母系優先を枝グラフに反映する
- 任意の重複枝を削除する
- 行き止まりノードの枝を削除してステップ11に戻る
- 基準ノードに連結する最長軸線を切り出す
- 行き止まりノードの枝をグラフから削除する
- 先祖ノードと末裔ノードを返す
ステップ8まではおそらく問題はないと思われる.おそらく一番クリティカルなステップは9の「重複パスをカットして線形グラフに変形」というところだろう.線形グラフというのが具体的にどのようなものを指しているのかはよく分からないが,イメージとしてはグラフを先祖ノードから末裔ノードまでをつなぐチェーンの集合のようなものに変えようとしているものと推定される.ステップ11でも「重複枝を削除」しているが,「重複枝」と呼んでいるのは必ずしも「多重枝」ではなく,単に「分岐」を意味しているようだ.
既存プログラムにはdumpgraphというグラフをテキスト形式でダンプするルーチンが整備され,デバッグ時には各ステップでそれを実行していたはずだが,現行のような描画システムを使って直接グラフを目で確認するという方法に勝るものではない.ステップ9の入口でインポートしたグラフを出力すると,孤立ノードを除いて,カードが30点残っている.
とりあえず,ここまでは問題ないと言えそうだ.しかし,ステップ8のループ出口でグラフを出力すると,ここではすでに軸線はpagesetupを通るパスで確定してしまっている.
上記では単に「マーク」と記しているが,実際に格納されるのは基準ノードからの距離Dであり,上りならばー,下りならば+が与えられる.一つのノードに到達するパスは複数あるので,下りならばより大きい値,上りならばより小さい値が設定される.ステップ9ではこの距離を基準に分岐を決めているのだが,成功していない.ステップ9の入口の軸線グラフにこの値を表示してみよう.
couplingは先祖ノードであると同時に基準ノードでもあるので,0,familytreeとpagesetupは1,topology, undosys, namesort, linktableは2という値を持っている.末裔ノードのNODULEは11, noduleは10で,確かに最長パスを経由した値が入っている.pagesetupとcouplingの距離は1だが,pagesetup→treeviewでは3の距離がある.つまり,treeviewが最長パス上にあるかないかは分からないが,少なくともpagesetup→treeviewの枝が最長パス上にないことは明らかだ.
現行アルゴリズムでは枝の両端点の距離Dを比較しているだけで,その絶対値が1より大きいかどうかということには無関心であるようだ.これは重要なポイントなのでまず,この論理を追加してみよう.枝の端点の距離Dの差が1より大きい枝を推移枝と呼んでおくことにしよう.推移枝は最長パス上にない枝と考えられるのでグラフから除去するという方策を立てて実装した.以下の枝が削除されている.
- #1:coupling(0) → #4:treeview(4)
- #5:pagesetup(1) → #4:treeview(4)
- #5:pagesetup(1) → #4:treeview(4)
- #7:topology(2) → #33:baselist基本世代枠(4)
- #130:EDGELIST(5) → #61:NLIST< LISTNODE, CID>(7)
- #33:baselist基本世代枠(4) → #61:NLIST< LISTNODE, CID>(7)
- #229:nlist(6) → #62:LIST(8)
- #118:UNDONODE(5) → #201:nodule(10)
- #156:配列要素(5) → #201:nodule(10)
- #235:Bobject(5) → #201:nodule(10)
この結果,軸線は下図のように変化した.
明らかにどこか切り過ぎている.pairlist→NLIST< LISTNODE, CID>という枝があるはずなのだが,どこかに消えてしまっている.上のカット枝のリストの中には入っていない.推移枝をカットした後の軸線グラフは下図のような状態になっている.
一番大きな原因はNLISTが親を失ってしまったという点だが,不審なのはNLISTの距離Dに61という大きな数字が表示されている点だ.その下の7という数字がむしろそれに該当するように思われるのだが… もしこの数字が7であれば,pairlistは6という数字を持っているので,pairlist→NLISTは存続できたのではないか?
いや,これはどうもインポートしている一覧表データの読み込み時の問題ではないかと思う.NLISTはNLIST< LISTNODE, CID>という名前を持っているが,「,」は区切り記号として使われているので,名前の中には使えない.⇒「,」を日本語文字の「,」に変えたら直った.直っただけでなく,チェーンが繋がった.
後は目を瞑っていても料理できる.処理後の軸線図を出してみよう.
!完璧だ!この図面「ZTシステム構成図7.ZEL」には,これ以外の軸線はあり得ない.…残念ながらその後が悪い.重婚クラスタ循環が存在しない図面で多重が3件も発生してしまっている.
クラスタ図(重婚クラスタグラフ)を出してみよう.
これは重婚クラスタグラフを軸線図で表示したものだが,軸線なしでも多分変わらないと思う.⇒実際,その通りだ.11世代ある.絶対世代番号はこの図面に従って出力しているはずだから,それに従って展開すれば,軸線を描画することは不可能ではないはずだ.
おそらく,クラスタ図作成の次段階である「ハッセ図の生成」というところでやり損なっているのだろう.実際のところ,クラスタ図がここまで出来ているのなら,「ハッセ図の生成」と呼ばれるプロセスはほとんど不要とさえ言える.ハッセ図の生成ステージは2段階の処理になっている.①TestInevitableMultiZeroと②VerticallyTightenHasseDiagramだ.もう一度洗い直しするしかないだろう.