抽象グラフ検証系を汎用化する – さあ，もう一度ゼロから始めよう

大失敗！Shirley（ミニノート）にインストールしたVisual Studio が不調なので，一旦アンインストールした後，再インストールを一晩掛けて実施したが，無料版のVisual Studio Communityをインストールしたつもりで，Enterprise版をインストールしてしまった．Enterprise版は30万円もする上，既存プロジェクトが「利用不可」になってしまう．これをアンインストールするだけで1時間くらい掛かりそうだ．

親子連結線の途切れを自動検出するためグラフ理論を応用したツールを作成することを意図しているが，すでに実装済の抽象グラフ検証系の仕様を調べておこう．ゼルコバの木では以下のような検定グラフをグラフ検証系の応用として実装している．

逆転循環検出枝グラフ
血統軸線図用枝グラフ
系列木グラフ枝グラフ
重婚同類グラフ1
重婚同類グラフ2
重婚同類グラフ3

これらはすべてSIMPLEGRAPH（検定用枝グラフ）として実装されている．SIMPLEGRAPHは①NODELIST，②EDGELIST，③COMPLISTを管理している．NODELISTはグラフの頂点集合，EDGELISTは辺集合，③COMPLISTは連結成分集合を意味するものと思われる．SIMPLEGRAPHの特徴はグラフの頂点としてシステム上の任意のオブジェクト（NODULE）を参照できるという点だ．NODELISTはSIMPLENODEのリストでSIMPLENODEはnoduleを参照している．EDGELISTはSIMPLEEDGEのリストでSIMPLEEDGEは辺の端点を示す2つのSIMPLENODEを参照している．

構想しているグラフを親子関係グラフと呼ぶことにしよう．親子関係グラフの節点は線分の端点であり，枝は線分そのものと考えられる．線分を描画する関数には用途によって各種ある．これらの描画仮数を呼び出すタイミングでグラフが生成されなくてはならないが，これはかなり難しい．描画関数は単純にディスプレイに描画を実行するための外部関数であり，システム内のオブジェクトとはまったく無関係だ．現行ではSIMPLENODE::linkにはnoduleポインタを格納することになっているが，これをvoidポインタに変更可能かどうか調べてみよう．

検定用枝グラフは基本的に対象システムを上から俯瞰するようになっていて，対象システムにはいかなる副作用も与えないことになっているのだから，参照先オブジェクトは必ずしもNODULEでなくても動作しなくてはならないはずだ．⇒この修正は比較的簡単に行えるが一つ問題が出てきた．連結成分の検査に用いているCOMPLISTは対象オブジェクトを直接参照するリストになっている．リスト操作は一般にノードのSLOTZEROを用いて構成されているが，SIMPLENODEはそれ自体リストを構成しているので，SLOTZEROが使えないようになっているためではないかと推定される．しかし，この構成はやや問題があると言わなくてはならない．グラフ検証系が一般的に活用される段階では対象オブジェクトがSLOTZEROを使っている可能性は十分あり得るからだ．

class NODELIST : public NLIST<SIMPLENODE, ‘V’>

どうすればよいか？SIMPLENODEに連結成分リスト用のスロットを設けることが考えられる．既存のリングないしリグという構成が使えるのではないか？デバッグ用増設スロットというものもある．

WASHING –4 UNDOシステムでオブジェクトの再生に用いる特殊枝番
SEIZEGROUND -3 アンカー接続：ポインタはメモリ上のセルに格納
XPAND_ANCHOR -2 デバッグ用増設スロットを示すスロット番号
EXTRA_ANCHOR -1 増設スロットを示すスロット番号

これらのスロット番号が負の値を取っているというところが不気味なところだ．実装者であるわたしでさえ想像つかない…親子関係グラフと夫婦関係グラフを合わせて結婚関係グラフと呼ぶことにしよう．系図木というのは究極のところ結婚木であり，婚姻関係図であると考えられる．結婚関係グラフがデバッグ時にのみ使われるものであるのなら，デバッグ用増設スロットを使うことも考えられるが，場合によっては拡張されたリリースバージョンでも使われるようになる可能性は十分考えられるので正規のスロットを定義しておいた方がよいように思われる．

リング参照リンクという構成が実装されている．これは「環状リスト用の汎用双方向参照」をサポートするためのもので，描画オブジェクトクラスでは2種のリングが使われている．一つは結婚枠衝突検定用結婚枠リング，もう一つは極大グラフ検定用セグメントリングだ．このクラスにはスロットを3つないし4つ使ったグループ参照リストも組み込まれているが，これらは汎用的な処理とはなっていない．現行のリスト処理はLISTクラスを基本クラスとするものでNLISTはその派生型だが，これを任意のスロットを用いる形式に仕様変更するのもかなり厄介だ．

COMPLISTはNLISTの派生型なのでここではキャストを用いて逃げておくことにしよう．クラスCOMPLISTの他にSIMPLEGRAPHでもlinkがnoduleであることを仮定している以下のような操作がある．MakeHasseDiagram，TightenHasseDiagram，DownStreamHasse，UpStreamHasse，RemoveRedundantEdge．これらはすべてNODULE::nodegene（絶対世代番号）を参照しているものだが，NODULEクラスの汎用性を考えるとこのパラメータをNODULEのメンバーとしておくことには問題がある．

しかし，その前にlinkを汎用ポインタでアクセスできるようにするためには，まずこのリンクを固有データ域に移す必要がある．実際，この状態で走らせるとGENEBOX::CheckInverseCycleでSIMPLEGRAPHを初期化しただけで落ちてしまう．

SIMPLENODEsLINKを廃止する必要がある．「SIMPLENODEsLINKを廃止＠20201019」を定義して切り分けるようにしておこう．TestSimpleGraphはコメントアウトした．「SIMPLENODEsLINKを廃止＠20201019」の両面で動作することを確認した．アプリ終了時に64バイトのメモリリークが出ているが，これは既存コードでも同じであり，以前から存在する事象と考えられる．

これで一応オブジェクトを含め「なんでも」グラフ検定の対象とすることができるようになった．たとえば，描画関数で線分を描画するとき，端点情報をどこかに保管できるようにしておけば，それだけで検証用の枝グラフを生成することが可能だ．ただし，その先は少々難しい．

◎COMPLISTは対象オブジェクトのSLOTZEROを使って連結成分リストを構成しているが，SIMPLEGRAPHを完全に抽象化するためにはオブジェクトから完全に分離する必要がある．SIMPLENODEにリスト構成用スロットを一つ設けるのがよいのではないか？任意のスロット番号を指定してリストを構成するようにLISTクラスを拡張するのは新たに組み込みで特殊リスト操作を付け加えるよりはるかに簡単なのではないか？現行ではSIMPLENODE::linkからオブジェクト以外の場所を参照することができるようになっているので，地雷を踏む危険性がある．

◎SIMPLEGRAPHで使っているnodegene（絶対世代番号）をNODULEのメンバ変数とすることには問題がある（一般性がない）．この値がハッセ図を生成するために不可欠であるというのなら，SIMPLENODEに持たせた方がよい．実際，SIMPLEEDGEはgenerationという値を持っている．枝を生成する時点でアプリからnodegeneを設定するSIMPLENODEの関数を呼び出すようにすればよいのではないか？

上記はSIMPLEGRAPHの抽象化レベルを高める上での必須項目である．

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル