hishiさんから問い合わせが入っているので返信した．
|
duke.hishi さま お問い合わせありがとうございます． ライセンスコード：ARKGWQN お試しください．（ライセンスキーをコピペしてください） 馬場研究所 PS: hishiさんから最初のお問い合わせを頂いたのは，2004年1月頃のことと思われますが，それからあっと言う間に17年もの年月が経過してしまいました．現在，「正式版」の年内リリースに向けて鋭意開発を進めているところですが，これまでどうしても突破できなかった壁を次々と打ち破る怒涛の進撃が続いています．ゼルコバの木ユーザ会のアルファ会員，ベータ会員の皆様には正式版初版を無償提供することをお約束していますが，hishiさんは加入年度から見てアルファ会員であることは間違いありませんので当然その資格をお持ちでいらっしゃいます．これからも末永くご支援賜りますようお願い申し上げます． |
閉路（循環）を持たない無向グラフを木というように，有向閉路を持たない有向グラフはADG（Acyclic Directed Graph, 非循環的有向グラフ）と呼ばれる．ADGのグラフ表現の中で特に矢線の向きが定方向（通常は上向き）であるようなものをハッセ図という．ZTでは系図図面上に配置されるカードの絶対世代番号を決めるために作成される重婚クラスタグラフをハッセ図と呼んでいるが，クラスタ図（重婚クラスタグラフ）は定義上ハッセ図そのものであるので，今後とも適宜使い分けることにしよう．クラスタ図を描画するための方法は色々考えられるが，もっとも確実な方法は，まずADGの最長鎖を求め，それを基準として各ノードの「世代」を決定することであると考えられる．最長鎖に関しては以下の定理が知られている．
| 定理：(P, ≦)を半順序集合，Pに含まれる最長鎖の長さをnとするとき，Pの要素はn個の互いに素な反鎖に分割される |
ここで反鎖(antichain)とは半順序集合Pの部分集合でそのどの要素も互いに関係を持たないようなものを言う．ゼルコバの木の用語で言うと，この「反鎖」の実体は「世代」に他ならない．平たく言えば，同一世代のノード同士には親子関係は存在しないという意味であり，別に難しいことを言っている訳ではない．反鎖への分割の仕方は必ずしも一意ではないが，その個数はつねにnになるというのが定理の趣旨だ．
「最長鎖」という概念は「軸線」を構成するために持ち込まれたものだが，最長鎖（軸線）が得られると軸線の長さをnとして系図上のすべてのノードはn世代に分割されると言うことができる．つまり，最長鎖を求めることは「クラスタ図」を得るためにも必須である．従って，最長鎖を求めるアルゴリズムを確立することが最重要な課題となってくるが，我々はすでにそれを得ているのではないか？そのことをまず，確認しておきたい．現行では下記のような手順で軸線を決定している．
- 基準ノードAの直系血族図に属するノードを節点とし，ノード間の親子関係を枝とする有向グラフGを生成する
- 基準ノードAの距離A(d)=0とし，Aに接続するノードでAより上にあるもの（Aの親）に-1，Aより下にあるもの（Aの子）に+1を与える
- 距離dの値を持っているすべての節点Nにつき，Nが負値を持っている場合には，Nと接続するNの親PにN(d)-1を与える，Nの親Pの距離P(d)≦N(d)-1のときには上書きしない．また，Nが正値を持っている場合にはNと接続するNの子KにN(d)+1の値を与える ただし，Nの子Kの距離K(d)≧N(d)+1の場合は上書きしない
- これをグラフGのすべての枝の始点と終点の距離dが確定するまで反復する （始点の距離dが更新された場合には終点の値を更新する，値が負値の場合はその逆）
- グラフGの節点のうち，入次数0でかつ最小のd値を持つものを先祖ノードとする（同じ値のd値を持つものが複数ある場合は任意選択する）
- グラフGの節点のうち，出次数0でかつ最大のd値を持つものを末裔ノードとする（同じ値のd値を持つものが複数ある場合は任意選択する）
- 先祖ノードと末裔ノードには自己ループ枝を追加する
- グラフGのすべての枝を点検して端点の距離dとd’の差の絶対値が1より大きいものがあればこれをグラフから取り除く
- 枝の除去によって入次数ないし出次数0となった節点はグラフから取り除く（先祖ノードと末裔ノードにはループ枝が追加されているので入次数ないし出次数0にはならない）
- 節点の除去によって始点ないし終点を失った枝はグラフから取り除く
- ステップ9に戻って静定するまで反復する
- 入次数ないし出次数が2以上の節点に接続する枝をグラフから取り除く
- ステップ9に戻って静定するまで反復する
- グラフに残った節点は（先祖ノードと末裔ノードを除き）すべて入次数および出次数1で先祖ノードから末裔ノードに至るチェーンを構成する
この手順によってつねに基準ノードを通る最長鎖を得られることが証明できるだろうか？基準ノードを必ず通る路が得られるということに関しては問題ないだろう．スタート地点が基準ノードでそれから上下に分かれているので，基準ノードは明らかに「関節点」になっており，このノードが削除されることはあり得ない．ステップ3, 4の距離数の割当てから，基準ノードの上の枝も下の枝もつねに，
始点の距離数＜終点の距離数
が成立することは明らかである．つまり，「番号」の逆転はあり得ない．ステップ8で除去される「端点の距離dとd’の差の絶対値が1より大きい」ような枝を推移枝と呼ぶ．下図では推移枝の始点の距離dは1，終点の距離dは3なのでその差は2となり，除去の対象となる
明らかにこのような推移枝がすべて除去された後のグラフGの枝はすべて始点と終点の距離数の差は1のものだけになるから，パス上の節点はすべて通し番号が振られたような状態になっていることは確実である．また，①→②，②→③のような枝は（ステップ8までは）除去されることはないので，このグラフが非連結にならないことも確認できる．ステップ9, 10を実行するとグラフには先祖ノード(source)から出て末裔ノード(sink)に入る枝しか残らないことになるから，source→sinkの複数のパスだけが残った状態になる．これらのパスはすべて通し番号でどの一つを取っても最長鎖になっていることは明らかであるから，任意のパスをカットして単線化すれば求めるチェーンが得られる．
これで証明になっているだろうか？ただし，一般の場合には，最長鎖が基準ノードを通るという保証はない．軸線図の場合には最長鎖つまり「軸線」が基準ノードを通っていることは必須だが，クラスタ図の場合，最長鎖が基準ノードを通っていないという場合もあり得ると考えられる．従って，クラスタ図で最長鎖を求める場合には上記手順をそのまま適用することはできない（対象も基準ノードの直系血族図ではなく系図全体が対象となる）．この場合は，系図上の先祖ノードの各々について，上記手順（基準ノードを先祖ノードと読み替える）で最長鎖を求め，その中で最長のものを系図全体の最長鎖とするしかないような気がする．これよりもっと効率的な方法はあるだろうか？既存の「ハッセ図検定」でどんなことをやっているのか見てみることにしよう．
先に進む前に最近の修正をフィックスしておくことにする．仕掛りのオプションとしては以下がある．
- adjustGenerationRangeを停止する＠20210117 1箇所 → 廃止
- 無向グラフでは並行枝を登録しない＠20210128 2箇所
- 直系血族配偶者は切り離す＠20210129 → 廃止
- FindJikusenAncestorで基準ノードの自己ループ枝を登録しない＠20210201 2箇所 → 廃止
- FindJikusenAncestorで軸線ノードを決定する＠20210201 8箇所
- 軸線ノードの抽出・TYW・ZTYWを禁止する＠20210202 2箇所
▲ZTシステム構成図7.ZELの直系血族図 基準ノード=#1 couplingを開いて，MARGBOX::setGoodSonで停止した．(GetHeadSibling() != this)という理由だ．この関数は血統軸線図の軸線GoodSonを設定するためのもので，GetHeadSiblingは拡張子ども枠の代表枠を返す関数だ．代表子ども枠は通常先頭枠であり，必ずしもgoodsonを保持するとは限らないような気がするのだが… この関数はTOPOLOGY：BuildShaftLineの中から呼び出されている．
MARGBOX::setgoodsonではgoodsonはgetmyplaceに格納されるので，単体結婚枠がgoodsonを持つというのでよいのではないかと思うのだが… GoodSonは代表枠が保持することになっていたのだろうか？「＠2016-09-29 GoodSonを上位枠が持っている場合がある」というコメントもあるので，代表枠が持つことになっている可能性はあるが… setgoodsonと矛盾するような気がするのだが… 確かにそのように取れるところもあるが，あまりよい仕様ではないような気がする．
障害が起きているのはMARGBOX #668：#776 tribelist(0)＋→#1279 baselist基本世代枠(1)で，その前にMARGBOX #731：#776 tribelist(0)＋→#1278 treeview(3)がある．⇒軸線枠はjikusenというプロパティを持っているのだから，あえてGoodSonという変数を使わなくてもよいような気がする．NAMEBOXにはGoodBoxという変数もある．これらは軸線の構成に手こずってやむを得ず導入されたものではないか？おそらくどちらも廃止できるのではないかと思われるが，ここでは停止しないでプリント文を出すだけとしておこう．
MARGBOX::CheckMarchainでもエラーが出た．「非代表枠のgoodson」というメッセージが出ている．確かに拡張枠の場合はgoodsonを代表枠に格納するという決まりになっているのだろう．あまりよいアイディアとは思われないが，これに合わせるしかないのではないか？⇒BuildShaftLineでsetGoodSonするときに代表枠があればそちらに設定するようにした．⇒エラーが2つとも解消したのでまぁ，これでよいことにしておこう．