|
追加キーワード: グラフ理論，ネットワーク最適化，展開形ゲーム，ゲームツリー，可視化，ヴィジュアル，グラフィックス． 前回記事にある「油分け問題」に続き，今回は最短路問題を解くダイクストラ法 (Dijkstra 法) の Ruby プログラミングを担当科目の課題にした．こちらはアルゴリズム自体はその疑似コードとともに授業で学んだので，あとは Ruby で表現する問題だ (受講生によればそこがむずかしい)．たとえば Wikipedia にある疑似コードを下敷きにしていいと受講生には伝えた． 自分でもプログラムを書いてみた．路線探索プログラムの本質的な部分が初心者にも書けたということであり，なかなか素晴らしい．(ちなみに路線探索では2番目以降に表示する経路をどうするかがむずかしいらしい．←こちらのサイトにはダイクストラ法の図解もある．) だが，なにかもの足りない．いや，将来「もの足りない」と言う学生が出てきそうな気がする．そう，なにもかも文字として処理されるのだ！ つまり重み付き枝たち (たとえば距離あるいは重み 10 の枝 (s, 1) を [:s,1,10] と書く) を要素とする配列と出発点 (たとえば :s と書く) を持つインスタンス problem を作れば，あとは problem.shortest_path_to(v) とやることで任意の点 v への最短路とその距離が配列として返って来る．図がどこにも現れないのである． そういう学生には，「心配はいらない．こういうグラフをテキストデータから描いてくれるプログラムは存在するはずだ」と答えるつもりだった．グラフというのは点と点のむすびつきの情報だけで決まるものであり，画像としての表現はその本質ではないからだ．把握のしやすさや見栄えを別にすれば，データを画像としてではなくテキストデータとして保持するのが本質的なやり方と言える．たぶん Mathematica あたりもそんな描画機能を備えているだろう．そんなところにたまたま飛び込んで来たのが，こちらの解説記事「ITpro【特選フリーソフト】テキストをグラフに変換 Graphviz」だ．ふむふむ，Graphviz ってのがあるんだね．ということで，Mac OS X edition of Graphviz を試してみた． 読者は「平面グラフ (点の位置をうまく選べば，辺が交差しないように平面上に描けるグラフ) をじっさいに辺が交差しないように描いてくれるんだろうか？」などの興味を持つかもしれない．平面グラフかどうかは理論的にはクラトウスキーの定理で判定できるが，このソフトがその判定機能を備えているかどうかは知らない．デモンストレーションを一見したところ，交差する枝が少ない気はするので，それに近い機能を利用しているんじゃないかとは思うが． 個人的には，これが家系図に使えるかどうかに関心がある．(ちょっと試したところ，残念ながら日本語が文字化けしたけど．) じっさい，同じ疑問をもったひとはいたようで，その返答として Graphviz で家系図を描いた例はあった．ポイントは親子関係を有向枝で表し，男性のノードを長方形で女性のノードを楕円で表すことにより区別することだろう．ノードを形で区別することは (ノードにノード名と異なるラベルをつける，あるいはノード名の付け方に規則を導入するという意味で多少)《グラフ》の定義を逸脱しているが (追記参照)，こうすることで「父・母・子」の3項関係を表すことはできる．ただし，このままでは兄弟の順番は (ラベルなしでは) 表現できないし，父母と兄弟の間の枝を交差させず直線で描こうとすれば (リマーク 1)，たぶん (先祖を子孫より位置的に上に描くといった) 階層構造は崩れる．じっさい，さっきの例のコードを描画してみたところ，根っこ以外のどのノードも出次数が 1，つまり子供がひとりだけということになっていた．すなわちこの家系図はある個人の直系尊属のみを記録したものであり，兄弟や傍系の存在に起因する複雑さを回避したものだった．
というわけで，Graphviz で家系図を作るとすれば，親子間の枝が複雑に交差するのは許す一方で，階層構造の表現を優先するのがよさそうだ．ここまでできるのだから，一組の夫婦にかんする親子関係の枝をまとめる方法 (つまり完全2部グラフ K2,n のすっきりした描き方) を提供してくれてもいい気はするけどね．[追記 2 参照] 追記 1 (1/26/2008). リマーク 1 などに若干手を入れた． 「お前は「父・母・子」の3項関係にこだわり過ぎている．家系図を描く上で重要なのはだれとだれが子供の親であるかであって，そのどちらが父親でどちらが母親かということではない．あくまでも親子関係という2項関係が基本だ．数学でも，2項関係の理論を多項関係のそれに拡張して本質的なちがいがあったか？ よき振る舞いをする多項関係は，2項関係に一定の条件を加えたものにすぎないのではないか？ お前の専門とする社会選択でも，《選好》という2項関係をもとにした理論と，多数からなにかを選ぶ選択関数という多項関係をもとにした理論とで大きなちがいがあったか？」とのお告げがあった． アダムとイブの関係を基本にして「生めよ，ふえよ，地に満ちよ」と祝福した神のお告げにしては意外だが，そこは問わないことにする．なるほど，《親子関係》を基本と考えて，それぞれのノードが親をふたつ持つ (入次数が2である) ことだけ要求すれば，たしかにどちらが父でどちらが母かは系図作成上重要ではないかもしれない．親の一方に「男」と，もう一方に「女」とラベルをつけることで満足ならば，3項関係を持ち出すまでもない．このばあい，親子関係のグラフは《グラフ》の定義を逸脱してはいない． 同様のことは「2部グラフ」と呼ばれるグラフでも起こる．2部グラフとはたとえば互いにセックスをしたことのある男女に枝を引くようなグラフであり，もちろん《グラフ》の定義を逸脱していない．ホモセクシャルを考慮外にすれば，男同士あるいは女同士のあいだには枝がない．つまりそれぞれの点に「男」あるいは「女」とラベルをつけられるようなグラフだ．その際，男性である太朗に「女」のラベルをつけたならば，太朗とセックスしたことのある花子には「男」のラベルをつけることになる．グラフへの追加的な構造として「男集合」「女集合」といたラベルのついた集合を導入しないかぎり，性別の逆転はありうる． 追記 2 (2/7/2008). 「Graphviz で家系図を作るとすれば，親子間の枝が複雑に交差するのは許す一方で」と書いたが，もちろん下図のように婚姻関係などを表す点をダミーとして入れれば枝の交差はなくせる．人間を表さない点が導入されるとか，入力ファイルの可読性が下がる (上がる?) といった問題を除けば，現実的な描き方かもしれない．
 |
 |
|
|
|
|
|
|
|
| ホーム |
|