非循環的有向グラフをハッセ図に転換する

軸線図グラフの動作はほぼ仕上がっているように思われるが,軸線が通らないサンプルが散見される.たとえば,STAGE6.ZELを#6 undosysで開くと下図が出力される.

image

これなどは,まだ最長鎖が取れていないようにも見えるのでチェックしてみよう.⇒どうも,やり損なっているようだ.カードに表示されている絶対世代番号で見ると,undosysは5,それと同世代のtopologyには2が割り当てられている.この番号は最長鎖検定ではなく,ハッセ図検定で付番しているものだが,こちらの方が正しい.いや,この図面は間違っていない.確かにtopology系の方が子孫系としては長いが,基準ノードのundosysから見ると傍系だ.現時点ではこのような図面になってしまうのは避け難いと思う.treeviewでソートした場合も同じだ.

image

この他,linktable, paegsetup, Bobjectでソートした場合にも同種の図面なる.つまり,血統軸線図の「軸線」とハッセ図の最長鎖は必ずしも一致しない.この2つをどのように調和させるか?あるいは,果たしてそれは可能か?ということを調べるためには,ハッセ図検定の中に踏み込むしかない.つまり,血統軸線図の場合には最長鎖検定を2度行う必要がある,ということだろう.既存ハッセ図検定と最長鎖検定をどうつなぐかというところはいまのところ不明だが,ともかく,一般のADGの最長鎖を求める検定の実装に入ることにしよう.その前に一つ最新のリリース版を起こしておくことにしよう.

現行のGetLongestChain(最長鎖の取得)を修正して一般のPDGを扱えるようにした.これまでは基準ノードの直系血族しか扱えなかったが,非連結な場合を含めてすべてのPDGを扱えるようになった.つまり,全系図を対象とする検定が行えるようになった.これをどこに使うかというと,重婚クラスタ検定で循環のないクラスタ図を生成したあと,このグラフから絶対世代番号を割り出すために使う.しかし,そこに組み込む前に本当に全系図のハッセ図を出力できるのかどうか試してみよう.それができれば,クラスタ図などはそれよりずっと小さいグラフなので容易に操作できることは確実だ.その前にまず,STAGE6.ZEL(30点)の枝グラフを生成し,それをエクスポートしたものを見てみよう.

image

オリジナルのZELファイルとまったく同じ系図が出力されている.全体図グラフには親子関係しか与えていないのだが,完全に同じものが生成されている.全体図グラフの枝は親子関係だが,父子関係,母子関係はそれぞれまったく独立に与えられているのに,一つの結婚としてまとめ上げられている.いや,このサンプルには単身婚しか含まれていないようなので別のサンプルを見ないと分からないが… まぁ,このまま続けよう.少なくとも兄弟は一つのボックスに入っている.最初にこのグラフをGetLongestChainに通してみよう.⇒GetLongestChainでエラーが出た.ノード数のカウントが合わないというエラーだ.

エラーはDeleteIsolatedNodeの中で起きている.いや,それよりずっと前,GetLongestChainの「基準ノードからのパスがない節点を削除する」で起きている.これはSIMPLEGRAPHの関数を使っていないためだ.⇒NODELIST::RemoveからSIMPLEGRAPH::Releaseに変えた.⇒これでエラーは解消したが,ファイルをインポートしようとして,「ファイルのオープンに失敗しました」のエラーになる.⇒最初のテーブルの列名の行しか入っていない.

「ループフリーグラフで自己ループ枝の登録は不可」というエラーが出ていた.今回はtempgraphという作業用グラフを使っているが,このグラフの属性は何も設定されていない.軸線グラフと同じ設定(SELFLOOPGRAPH | DIRECTEDGRAPH)にする必要がある.このグラフは普段は「系列枠リストのソート用」に使われている.しかし,実際に使われている形跡がない.最近の修正で大量廃棄されたコードの中で使われていたのかもしれない… ⇒インポートできるようになったが,カードが3枚しか残っていない.

image

これは先祖ノードと基準ノード(今回はundosys),末裔ノードだろう.⇒【2.3】基準ノードからのパスがない節点を削除するのところで4点削除されている.namesort,linktable,topology,NLISTだ.これらのノードを削除するのは間違いだが,それだけですべての枝が削除される結果になるだろうか?実際に枝が削除されるのは【4】距離が1以上の推移枝を削除するだ.ここで枝数30が一挙に3になってしまう.

「基準ノードからのパスがない(端点にマークのない)節点を削除する」とき,値が0ではNOMARKであることをチェックするようにして,上記4点の削除は止まった.推移枝の削除では枝数は40から27まで減少する.13枝削除されているが,まだ大多数は健在だ.次のRemoveDeadEndBranchで一挙にループ枝以外のすべての枝が切り落とされている.RemoveDeadEndBranchの論理が悪いのか,我々のアルゴリズムに根本的な誤りがあるかのいずれかだ.

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA