ADGの最長鎖を求める汎用関数

Version 2.2.0.023 Release 2021-02-05を所内リリースした.これでSTOPで停止することもなくなるだろう.まず,ADGの最長鎖を求める汎用関数を作ってみることにする.これがあれば,軸線図でもクラスタ図でも使えるようになる.関数名はSIMPLEGRAPH::GetLongestChainとし,TOPOLOGY::FindJikusenAncestorから既存論理をコピーするところから始める.⇒実装した.SIMPLEGRAPH::GetLongestChainでは昨日書いた手順書のステップ9で一旦復帰することにした.復帰時のグラフは複数のsourceと複数のsinkを結ぶ複数の最長鎖が残った状態となっているはずだ.アプリでは,必要があれば,長子優先/父系・母系などのオプションによる選択をここで実施することができる.

GetLongestChainをFindJikusenAncestorに組み込んで動作を見てみよう.実装完了した.一応動くようになった.下図は,ZTシステム構成図7.ZEL 直系血族図 基準ノード=#30 MDBの軸線グラフをGetLongestChainで処理してエクスポートしたものだ.

image

先祖ノードはcouplingとCOUPLINGの2点,末裔ノードはownerからNODULEまでの13点が残っている.その他,多重パスが2個所に出現している.familytreeからtopology, namesort,linktableの3点に分岐,配列要素からmargbox, noduleの2点に分岐している.アプリ側ではこのグラフから適切な先祖ノードと末裔ノードを選択し,重複パスを解消して単線の軸線グラフを取り出すことができる.ただし,現行論理ではその辺りで失敗しているので,この系図の図面はまだ出力されていない.最長鎖の長さを知りたいだけなら,すでに結論は出ている.ノードMDBを通る最長鎖の長さはノード数をカウントして8だ.(距離というときはパス上の枝数を言うので7ということになる)

この分岐をどう始末するか?が問題だ.既存論理はできが悪いので全面破棄することとし,一から書き直すことにしよう.軸線グラフが単線になっているかどうかをチェックするのは簡単だ.枝数と節点数を比較し,枝数+1=節点数となっていれば,軸線を得られたことになる(グラフが連結で循環を持たないという前提の下で).ダブっている節点を任意に削除してこの状態に持ち込むことが可能だが,一つのノードを削除するとトポロジーが変化してしまうのでそれをコントロールする必要がある.まず,SIMPLEGRAPHが持っている連結成分リストを使って,反鎖リストを作るところから始めよう.反鎖リストというのは世代別にノードを集めたリストだ.⇒できた!

このサンプルでダブっているのは4箇所だから,4段階で処理できる.とりあえず,半鎖リストの先頭ノードを残すという論理を組んでみよう.⇒実装したが,枝数10,節点数8でループしている.なにか余分な枝が残ってしまっているようだ.自己ループが2つ残っている.GetLongestChainの出口で外しておくことにしよう.いや,ダメだ.このロックを外すと反鎖リストの始末も付けられない.自己ループは残しておかないと動作に支障をきたすので,最終的には枝数 – 1=節点数となるはずだ.⇒namesort→MDBという多重枝がある.なぜだろう?軸線グラフでは多重枝は認められていないはずなのだが… ノードの短絡や縮約を実行すると多重枝が発生する可能性はあるが…

どこで多重枝が発生しているのか?調べてみよう.GetLongestChainの入口ですでに多重枝が発生している.つまり,チェックがまるきり効いていない.⇒SIMPLEGRAPH::addではまったく検査していない.大文字のSIMPLEGRAPH::Addでは検査している.いや,addはAddを呼び出しているだけだ.使っている関数が間違っていた.findedgeではなく,FindEdgeだ.⇒ループを抜けてきたが,まだ悪い.

軸線は通ったが,孤立カードが13枚も残っている.しかも,そのうちの一つ#1は空白カードだ.⇒枝数 – 1=節点数でブレークしているためだ.節点数=20 枝数=21でブレークしてしまう.やはり,最長鎖の長さを見ないとダメだ(孤立カードが残っている,つまり連結していない).枝数 – 1=最長鎖の長さでブレークするようにしてほぼ片付いたが,空白カード1枚は残っている.なぜだろう?いや,これは残っているのではなく,ZTの多重カードのようだ.

image

いや,違う.白紙カードが別カードとして入っている.一覧表で見ても9枚になっている.しかし,グラフのダンプでは節点数=8 枝数=9となっているので,エクスポートでなにか余分なものを出力しているのではないか?⇒テキストエディタでCSVファイルを開いてチェックしてみたが,レコードは8件しか登録されていない.エクスポートする直前に自己ループ枝を除去しても変化しない.インポート側を見るしかない.インポートでも8枚しか処理していない.

LINKTABLE::ImportEndでMakeMarriagePageというのを実行している.ここで新規カードが発生している模様だ.いや,これは違う.結婚リンクを生成しているところだ.ImportTableFuncでは最初に新規ファイルを開いているが,このときすでに無名のカードが作られている.

コメントを残す

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

CAPTCHA