はじめに
グラフ理論のグラフです。チャートではありません。
実装
今回は,隣接行列を内部に持つグラフ構造種類を定義して,その上でサクッとグラフを描いてくれるようにしたいと思います。
図形描画は面倒なので,今回はグラフ描画老舗最大手のgraphvizを使います。
コンストラクタ
日本語プログラミング言語なので,日本語をラベルに持ったノードも使うことがあるかもしれません。その際に問題になるのがフォントです。そこで,フォントを指定できるようにしておきます。
グラフ構造とは
+隣接行列:行列
+ラベル:配列
-フォント名:文字列
-大きさ:整数
はじめ(V)の手順
隣接行列は,行列(V,V)を作ったもの。
V回【あ】にカウントして繰り返す
ラベル(あ)は,あ。
繰り返し終わり。
大きさは,V。
フォント名は,「」。
終わり
はじめ(V,F)の手順
隣接行列は,行列(V,V)を作ったもの。
V回【あ】にカウントして繰り返す
ラベル(あ)は,あ。
繰り返し終わり。
大きさは,V。
フォント名は,「node [[]fontname = "[F]"[]];[改行]」。
終わり
終わり
エッジを引く
これは隣接行列に1を立てるだけです。
自分で【始点:整数】から【終点:整数】にエッジを引く手順
隣接行列の中身(始点,終点)は,1。
終わり
dotを作成する
有向グラフと無向グラフの場合で書き方が少し違うので,手順を2つ用意しました。
まず,有向グラフです。
自分を有向グラフとして描画する手順
【ドット:文字列】は,「」。
ドットは,ドット&「digraph{[改行][フォント名]」。
大きさ回,【行】にカウントして繰り返す
大きさ回,【列】にカウントして繰り返す
もし隣接行列の中身(行,列)が1なら
ドットは,ドット&「[タブ]"[ラベル(行)]" -> "[ラベル(列)]";[改行]」。
もし終わり
繰り返し終わり
繰り返し終わり
ドットは,ドット&「}」。
ドットをよしなにする。
終わり
まあそうだよね,という感じです。次に,無向グラフ。
自分を無向グラフとして描画する手順
【ドット:文字列】は,「」。
ドットは,ドット&「graph{[改行][フォント名]」。
大きさ回,【行】にカウントして繰り返す
大きさ回,【列】にカウントして繰り返す
もし隣接行列の中身(行,列)が1なら
もし(行<=列)または(隣接行列の中身(列,行)が0)なら
ドットは,ドット&「[タブ]"[ラベル(行)]" -- "[ラベル(列)]";[改行]」。
もし終わり
もし終わり
繰り返し終わり
繰り返し終わり
ドットは,ドット&「}」。
ドットをよしなにする。
終わり
無向グラフは,A→Bというエッジと,B→Aというエッジがあった場合に,2本エッジを引く意味が無いので,2回目の描画をしないようにしています。行<=列の場合に絞るという手もありますが,隣接行列にどのようにデータが入るか分からないので,採用しませんでした。
dotを起動して画像化し,表示する
【ドットデータ:文字列】をよしなにする手順
ドットデータを「_temp.dot」へ「UTF8」で保存する。
「dot.exe」を「-Tpng -O _temp.dot」として起動して待つ。
グラフ画像という画像(「_temp.dot.png」)を作る。
画像表示というウィンドウを作る。
その実質大きさは,グラフ画像の大きさ。
そのタイトルは,「グラフ」。
画像表示へ画像領域というピクチャーを作る。
その位置は,{0,0}。
その大きさは,画像表示の実質大きさ。
その画像は,グラフ画像。
画像表示を表示。
「_temp.dot」を削除する。
「_temp.dot.png」を削除する。
終わり
仮に_temp.dot
にdotファイルを出力し,dotを起動しています。dotはPATHが通っていることが前提です。出力されたPNG画像を読み込んで,ウィンドウに表示しています。
なんか描く
何か描いてみたいと思います。
「行列.rdr」を参照する。
「グラフ構造.rdr」を参照する。
路線図というグラフ構造(8,「Yu Gothic」)を作る。
路線図のラベルは,{「荻窪」,「中野」,「新宿」,「飯田橋」,「四ツ谷」,「東京」,「大手町」,「御茶ノ水」}。
’中央線
路線図で1から2にエッジを引く。
路線図で2から3にエッジを引く。
路線図で3から4にエッジを引く。
路線図で4から5にエッジを引く。
路線図で5から8にエッジを引く。
路線図で8から6にエッジを引く。
’東西線
路線図で2から4にエッジを引く。
路線図で4から7にエッジを引く。
’丸ノ内線
路線図で1から3にエッジを引く。
路線図で3から5にエッジを引く。
路線図で5から6にエッジを引く。
路線図で6から7にエッジを引く。
路線図で7から8にエッジを引く。
路線図を無向グラフとして描画する。
待機。
きちんと動きました。
有向グラフも描いてみます。
「行列.rdr」を参照する。
「グラフ構造.rdr」を参照する。
進路というグラフ構造(10,「Meiryo」)を作る。
進路のラベルは,{「幼稚園」,「小学校」,「中学校」,「中等教育学校」,「高等学校」,「高等専門学校」,「大学」,「大学院」,「大学病院」,「通商産業省工業技術院」}。
進路で1から2にエッジを引く。
進路で2から3にエッジを引く。
進路で2から4にエッジを引く。
進路で3から5にエッジを引く。
進路で3から6にエッジを引く。
進路で4から7にエッジを引く。
進路で5から7にエッジを引く。
進路で6から7にエッジを引く。
進路で6から8にエッジを引く。
進路で7から8にエッジを引く。
進路で7から9にエッジを引く。
進路で8から9にエッジを引く。
進路で9から8にエッジを引く。
進路で7から10にエッジを引く。
進路を有向グラフとして描画する。
待機。
きちんと動きました。
なお,グラフ構造.rdrでは,
路線図で「荻窪」から「中野」にエッジを引く。
などと書いても動きます。