Graphviz

ある記号列の列挙 #8

#2のen2.cや#3のen3.cでは多重エッジを含むグラフを生成しており、 #2ではこれを除去するためにtredを使ってフィルタリングした。 いちいちフィルタするのも面倒な場合、 DOTの方でこれに対処する方法がある。 たとえば、en3.cの場合なら、 en3strict.c #inc…

ある記号列の列挙 #3

enumerate(5, 4)では詳細に立ち入るにはちょっと大きい。 そこでスケールダウンしてenumerate(2, 1)について見てみる。 実はenumerate(2, 1)についてのグラフは既に出ている。 前回の記事の最後に出したグラフの中で、 ノードenumerate(2, 1)を根にして辿る…

ある記号列の列挙 #2

再帰関数enumerateの呼び出し関係をグラフで表してみる。 例えば、enumerate(5, 4)内では個数aを一つ減じて、 enumerate(4, 4)が呼ばれているので、これを、 と表現することにする。 ノードに関数の二つの引数の値、エッジにaとbのどちらの記号数を減じて呼…

gvprでの文字列の等価比較

前回のgvprプログラムには、 if (length(cs[i]) == length(c) && index(cs[i], c) == 0) {や if (length(list[i]) == length(action) && index(list[i], action) == 0) {のような条件式がif文中にあるが、この式は二つのstring型が等価かどうかを判断してい…

単純なマーク付けがなされた文字列の解析 #12

#10のプログラムから#11のプログラムへは手動で書き換えた。 試験データでは同様に動いているようだが、本当にちゃんと書き換えられているのだろうか。 というわけで、#10のプログラムから状態遷移表を作成してみて、 #11のアクション関数やtable等と突き合…

単純なマーク付けがなされた文字列の解析 #6

bisonはLR項の集合をノードとするGOTOグラフをDOT形式で出力するオプション-gを持っている。 例えば#3のparser.yからGOTOグラフを出力し、そのままdotコマンドで画像化すると結構大きいサイズになる。 GOTOグラフのノードの中にLR項の集合の全要素、つまり属…

ライフゲーム #30

ずいぶん長い間この話題を続けてきたのでこのあたりで一旦休む。さもないといつまでも続けられそうだ。 とりあえず便宜のため散らばっている関連するgvprプログラムをひとまとめにしておく。 以下のコードでは今までの記事のものから変更しているものもある…

ライフゲーム #29

set_gen0.gのはみ出し警告になにやらバグがある気がする。 はみ出さない配置なのに警告が出ることが起こるようだ。 設定動作そのものには影響していないようなのでとりあえずそのままに(え?*1気を取り直して、作成したトーラス面で滑空するGliderを見てみ…

ライフゲーム #28

gen_mesh.gが生成するグラフには端がある。そのため、前回のような現象も起きる。 とはいえ無限の広がりをもったグラフは難しいので、 グラフの上端と下端、右端と左端のノードを繋いでトーラス面にするプログラムを作ってみる。 gen_torus.g BEGIN { if (AR…

ライフゲーム #27

サイズを広めに取っておいて元々動かす気満々だったわけだが、Glider編隊を飛ばしてみよう。 レンダリングパラメータの設定にはvis_alive_2.gを使う。 $ gvpr -f gen_mesh.g -a 30,20 | > gvpr -cf set_gen0.g -a "glider.txt 26,16 glider.txt 21,16 glider…

ライフゲーム #26

せっかくだからもう少しだけset_gen0.gを便利にしてみよう。 座標リストと移動量の組み合わせを複数指定できるようにしてみる。 set_gen0.g BEGIN { if (ARGC < 1) { printf(2, 'usage: gvpr -cf set_gen0.g -a filename [[-a x0,y0 -a filename]...] [-a x0…

ライフゲーム #25

メッシュをはみ出してしまうような設定が行われた場合は警告を出すようにすべきか? 現状、はみ出してしまうような座標が指定されても無視するだけなので問題は少ないが。 set_gen0.g BEGIN { ...snip int fd = openF(filename, 'r'); string p[], s; int pn…

ライフゲーム #24

第0世代のalive属性付きノードを設定するgvprフィルタset_gen0.gで使い辛い点は、 設定座標リストファイルで指定できるメッシュ座標が絶対座標であることだ。 パターン全体を平行移動して設定したいことはよく起きるので、 座標リストは相対座標であることに…

無向グラフのDOTにgvprでrank付きサブグラフを加える #3

とりあえず前回のコードでうまくrankの設定がなされたサブグラフが加えられた。 しかし、insert_rank.gが出力するDOTを見ると、 graph { subgraph 3 { graph [rank=same]; "2,3"; "1,3"; "0,3"; } subgraph 2 { graph [rank=same]; ...snip のように、subgra…

無向グラフのDOTにgvprでrank付きサブグラフを加える #2

DOTにおけるサブグラフの定義の順序は、サブグラフが新規に作成されてグラフに追加される順序である。 それは前回のコードでは各ノードが走査される順序に依存していた。 前回は走査順が0,1,2,3になっていたが、順序は与えられるグラフ次第なので、しっかり…

無向グラフのDOTにgvprでrank付きサブグラフを加える #1

話題のメインがライフゲームと関係なさそうなのでタイトルを変えた。 ライフゲームの記事の#20ではdotコマンドを使ってレンダリングしようとした。 その時は手書きでDOTファイルを書いたのだが、あのサイズでもそれは面倒だった。 これをメッシュ生成プログ…

ライフゲーム #23

diehard.txtで設定されるパターンはDiehardという名前が付けられている。 第0世代でたった7個しかaliveでないのだが130世代ほど変化が続き、Methuselah*1と呼ばれるカテゴリに属する。 McClane警部補はまだ一般人な方で、Methuselahの中にはもっとずっと長く…

ライフゲーム #22

前日にdotで使用するために検討した際の見栄えがシンプルでいい感じだったので、 vis_alive.gをそういう感じに描画されるように変更してみた。 vis_alive_2.g BEGIN { if (ARGC != 1) { printf(2, 'usage: gvpr -f vis_alive_2.g -a size\n'); exit(0); } do…

ライフゲーム #21

グラフの見栄えに関するパラメータを調節してそれっぽくなるようにしてみる。 とりあえず、パラメータをtest.gvに直接挿入して調整してみる。 test.gv graph { graph [nodesep=0,ranksep=0]; { rank = same; "0,3"; "1,3"; "2,3"; } ...snip "1,3" -- "2,2";…

ライフゲーム #20

グラフのレンダリングにneatoを使ってきたがdotを使えないか考えてみた。 pos属性は便利だがneatoに特異的な属性なのでdotでは使えない。 代わりにノードの位置揃えにrank属性があり、これを使うことにする。 test.gv graph { { rank = same; "0,3"; "1,3"; …

ライフゲーム #19

Glider Gunの動きを100世代分ほどのanimated GIFにしてみる。 このサイズで100世代分のDOTとPNGを生成するのにあまり速くない手元の環境で二分程度なので速度的に遅すぎる訳ではない。 レンダリングに時間がかかるようだ。 やっていることがGraphviz本来の使…

ライフゲーム #18

第0世代のalive属性を長々と設定するところをもう少し何とかしよう。 glider_gun.txt 1,23 1,24 2,23 2,24 ...snip 35,25 35,26 36,25 36,26のようにalive属性を付与するノード名のリストを作成しておく。 このリストを読み込み、name属性がそのどれかに一致…

ライフゲーム #17

次に、画像化用の属性を付与するフィルタvis_alive.gを変更する。 vis_alive.g BEGIN { if (ARGC != 1) { printf(2, 'usage: gvpr -cf vis_alive.g -a size\n'); exit(0); } double size = ARGV[0]; if (size <= 0) { printf(2, 'error: size must be positi…

ライフゲーム #16

そういえば、gen_mesh.gが出力するものと似たようなグラフを、 Graphvizのgvgenコマンドにグリッド生成オプションを与えて、 gvgen -g 3,4 | neato -Elen=.75 -T png -o 3x4.png のように生成することはできる。 しかし、ノード名が1から始まる連番となって…

ライフゲーム #15

今までのコードを少し変更、整理してみる。 ノードのname属性を"nx_y"形式から"x,y"形式に変更する。 また、vis_alive.gにneatoでオプション指定していたものを組み入れる。 次世代を生成するnext_gen.gは触る必要は多分ないはず。まず、メッシュ生成プログ…

ライフゲーム #14

前の記事で示したコードの中に少しくどい部分があった。 pos属性をピン留めするために感嘆符を付加するコード、 c:\foo> gvpr -cf vis_alive.g glider_0.gv | gvpr -c "N{pos=sprintf('%s!',pos);}" | ...snip...は、posがstringなので、 c:\foo> gvpr -cf v…

ライフゲーム #13

さて、ノードのpos属性をピン留めする方向に進むか否かについて考えてみよう。 ピン留めしていない現在のグラフでは各ノードのpos属性の値は1単位で整数値を与えられている。 ピン留めされていないため、neatoのオプションで、 neato ...snip... -Nwidth=.2 …

ライフゲーム #12

コマ撮りでは面白みに欠けるので動画にしてみよう。 はてなで使える形式で大抵のグラフィカルなウエブブラウザで見られるものとなるとanimated GIFか。 手元にある環境でお手軽に作成するなら、Ubuntuの方にImageMagickを入れてあったのでこれを使う。 まず…

ライフゲーム #11

広くなった空で動かしてみよう。 既述の通り、コマンドラインシェルにあまり関係しないようgvprプログラムをシェルスクリプト代わりにする。 第0世代から第49世代まで7世代ごとの状況を画像化してみる。 gvpr "BEGIN{int i;for(i=0;i<49;i++)system(sprintf(…

ライフゲーム #10

6x6ではあんまりなのでGliderをもうちょっとだけ広い空で滑空させる。 メッシュサイズを20x16にして第0世代のグラフを今まで通りの方法で作る。 gvpr -f gen_mesh.g -a "20 16" | gvpr -c "N{if(name=='n16_2'||name=='n16_3'||name=='n17_1'||name=='n17_3'…