スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
【--/--/-- --:-- 】
| スポンサー広告 | コメント(-) | トラックバック(-) |
最短路問題,グラフ描画,家系図

追加キーワード: グラフ理論,ネットワーク最適化,展開形ゲーム,ゲームツリー,可視化,ヴィジュアル,グラフィックス.

前回記事にある「油分け問題」に続き,今回は最短路問題を解くダイクストラ法 (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,つまり子供がひとりだけということになっていた.すなわちこの家系図はある個人の直系尊属のみを記録したものであり,兄弟や傍系の存在に起因する複雑さを回避したものだった.

リマーク 1.

読者は「そもそも親子間の枝をつねに交差なしの直線で描くことは無理では」と思うかもしれない.だが,できるのだ.一組の夫婦とその子だけからなるグラフに関する限りできる.そのグラフが平面グラフであることは描いてみればすぐ確かめられる.そして,たぶん驚くべきことにファーリの定理によれば,すべての平面グラフはどの辺もまっすぐになるように描けるのだ!……いや,そんな定理を持ち出すまでもなく,子を横一列にならべて,親をその列の上下に配置すればできる.よき教育者は,イメージを喚起しやすいように教育的配慮をするものだ.これはどうか? 時間軸の両側に男女がいて,ある時点 t におけるセックスでできた子供を,時間軸上の点 t に配置する感じだ.(ちなみに一組の夫婦とその n 人の子からなる親子関係グラフは完全2部グラフ K2,n という.)

なお,夫婦 1 組子供 5人を表現する dot ファイルを作って Graphviz の 4 つのレイアウトをちょっと試したところ,いずれの描画も枝が交差するものだった.「平面グラフを辺が交差しないように描いてくれるんだろうか?」という疑問には,いまのところポジティブな答を得ていない.

というわけで,Graphviz で家系図を作るとすれば,親子間の枝が複雑に交差するのは許す一方で,階層構造の表現を優先するのがよさそうだ.ここまでできるのだから,一組の夫婦にかんする親子関係の枝をまとめる方法 (つまり完全2部グラフ K2,n のすっきりした描き方) を提供してくれてもいい気はするけどね.[追記 2 参照]

追記 1 (1/26/2008).

リマーク 1 などに若干手を入れた.

「お前は「父・母・子」の3項関係にこだわり過ぎている.家系図を描く上で重要なのはだれとだれが子供の親であるかであって,そのどちらが父親でどちらが母親かということではない.あくまでも親子関係という2項関係が基本だ.数学でも,2項関係の理論を多項関係のそれに拡張して本質的なちがいがあったか? よき振る舞いをする多項関係は,2項関係に一定の条件を加えたものにすぎないのではないか? お前の専門とする社会選択でも,《選好》という2項関係をもとにした理論と,多数からなにかを選ぶ選択関数という多項関係をもとにした理論とで大きなちがいがあったか?」とのお告げがあった.

アダムとイブの関係を基本にして「生めよ,ふえよ,地に満ちよ」と祝福した神のお告げにしては意外だが,そこは問わないことにする.なるほど,《親子関係》を基本と考えて,それぞれのノードが親をふたつ持つ (入次数が2である) ことだけ要求すれば,たしかにどちらが父でどちらが母かは系図作成上重要ではないかもしれない.親の一方に「男」と,もう一方に「女」とラベルをつけることで満足ならば,3項関係を持ち出すまでもない.このばあい,親子関係のグラフは《グラフ》の定義を逸脱してはいない.

同様のことは「2部グラフ」と呼ばれるグラフでも起こる.2部グラフとはたとえば互いにセックスをしたことのある男女に枝を引くようなグラフであり,もちろん《グラフ》の定義を逸脱していない.ホモセクシャルを考慮外にすれば,男同士あるいは女同士のあいだには枝がない.つまりそれぞれの点に「男」あるいは「女」とラベルをつけられるようなグラフだ.その際,男性である太朗に「女」のラベルをつけたならば,太朗とセックスしたことのある花子には「男」のラベルをつけることになる.グラフへの追加的な構造として「男集合」「女集合」といたラベルのついた集合を導入しないかぎり,性別の逆転はありうる.

追記 2 (2/7/2008).

「Graphviz で家系図を作るとすれば,親子間の枝が複雑に交差するのは許す一方で」と書いたが,もちろん下図のように婚姻関係などを表す点をダミーとして入れれば枝の交差はなくせる.人間を表さない点が導入されるとか,入力ファイルの可読性が下がる (上がる?) といった問題を除けば,現実的な描き方かもしれない.


【2008/01/25 17:39 】
| プログラミング | コメント(0) | トラックバック(1) |
<<経済学,経営学,見えざる手 | ホーム | Ruby との悪戦苦闘で明けた新年>>
コメント
コメントの投稿











管理者にだけ表示を許可する

トラックバック
トラックバックURL
http://theorist.blog6.fc2.com/tb.php/146-b29b0601
非循環性なしの社会選択理論が出現!
「それってすごいことなの?」って? 経済理論を教える大学教授にでも聞いてくれ. ここでは最初に「社会選択のコアにかんするクイズ」の... ある平凡助教授の,なんということもない日々【2008/11/25 16:00】
| ホーム |
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。