0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

プロデルAdvent Calendar 2019

Day 10

日本語プログラミング言語「プロデル」でグラフを描く

Last updated at Posted at 2019-12-09

はじめに

グラフ理論のグラフです。チャートではありません。

実装

今回は,隣接行列を内部に持つグラフ構造種類を定義して,その上でサクッとグラフを描いてくれるようにしたいと思います。
図形描画は面倒なので,今回はグラフ描画老舗最大手のgraphvizを使います。

コンストラクタ

日本語プログラミング言語なので,日本語をラベルに持ったノードも使うことがあるかもしれません。その際に問題になるのがフォントです。そこで,フォントを指定できるようにしておきます。

グラフ構造.rdr
グラフ構造とは
	+隣接行列:行列
	+ラベル:配列
	-フォント名:文字列
	-大きさ:整数
	はじめ(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にエッジを引く。

路線図を無向グラフとして描画する。
待機。

image.png

きちんと動きました。

有向グラフも描いてみます。

「行列.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にエッジを引く。

進路を有向グラフとして描画する。
待機。

image.png

きちんと動きました。

なお,グラフ構造.rdrでは,

路線図で「荻窪」から「中野」にエッジを引く。

などと書いても動きます。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?