Graphvizで描いたグラフをGIFアニメにする - 赤黒木を例に

皆さんの脳内でも赤西仁×黒木メイサが2-3-4木でいうところの3-節として内部表現されていることと存じますが、今日は赤黒木を題材にGraphvizで描いたグラフをGIFアニメにしてみたいと思います。というか単なる Graphviz入門です。

いきなりGraphvizの本家ドキュメント（英語）だけ眺めててもさっぱり分からないのでGraphvizチュートリアルとかdotを使ったグラフ描画(PDF)とかお勧めします。Graphvizに関する日本語の情報ってあまり多くない気がします。

デフォルト設定だと縦方向に間延びしたグラフが出来上がってくるので、ranksep とか nodesep を納得のいく値に調整しましょう。
あと、binary treeはノードの位置関係（左右）が重要だったりしますが放っておくと勝手に位置を差し替えられてしまうことがあるので注意が必要です。（ordering = out を指定しましょう。それでもsubgraphとか作ると効かないですね）

さて。Graphvizで

のような赤黒木画像を生成するにはDOT言語で

graph sample {
  graph [ center = "false", ordering = out, ranksep = 0.2, nodesep = 0.5 ];
  node [ fontname = "Courier", fontsize = 14, shape = circle, width = 0.2, height = 0.2, margin = 0.01 ];
  edge [ color = black, weight = 1 ];
  N3 [ label = "1" ]
  N3 -- N2;
  N2 [ label = "0" ]
  L2 [ shape = box, width = 0.1, height = 0.1, label = "" ];
  N2 -- L2;
  R2 [ shape = box, width = 0.1, height = 0.1, label = "" ];
  N2 -- R2;
  N3 -- N4;
  N4 [ label = "2" ]
  L4 [ shape = box, width = 0.1, height = 0.1, label = "" ];
  N4 -- L4;
  N4 -- N5 [ style = bold, color = red ];
  N5 [ label = "3" ]
  L5 [ shape = box, width = 0.1, height = 0.1, label = "" ];
  N5 -- L5;
  R5 [ shape = box, width = 0.1, height = 0.1, label = "" ];
  N5 -- R5;
}

みたいなのを手書きするなり自動生成するなりして、

$ dot -Tgif rbt.dot -o rbt.gif

とかすればGraphvizがグラフ画像を作ってくれます。
アニメ化にあたり１コマずつ作りたいのでここでは当然自動生成です。(rbt_gen.cc)

１コマ１コマの画像からGIFアニメを作るにはImageMagickが便利です。CUIなので自動化しやすいです。
ただ、Graphvizが、というか dot コマンドが生成するグラフって画像サイズが自動調整されるので、単に

$ animate *.gif

とかやるだけだと画像サイズもrootノードの位置もずれてて駄目駄目です。rootノードの位置座標をセンターに固定、とかできたら良いのですが何か簡単には出来なさそうなので、吐き出された画像を見てどうにかすることを考えます。

GIF89aのデータを展開とか面倒くさかったので、ImageMagickのconvertコマンドでbmpに変換し、黒っぽい色が付いている部分を走査してrootノードの上端座標を得るツールを自作しました (topcenter.c) 。この値と画像サイズから各グラフ画像のオフセット位置を算出し、convertコマンドに渡します。ファイル数が多いので、全コマ画像から

$ convert -delay 50 -size 1000x500 xc:White -page +120+0 rbt_000.gif -page +120+0 rbt_001.gif ... -loop 0 rbt_anim,gif

のようなコマンドを自動生成し実行するスクリプトを書きました。(rbt_anim_gen.awk)

以上の工程をmake一発で
0から昇順に追加：

ランダムに追加：

どんな順序でデータを挿入しても勝手にバランスを取っていく赤黒木の気持ち悪さ優秀さが視覚的に理解できますね。

コードは https://github.com/naoyat/rbt-anime にNYSLで置いておきます。煮るなり焼くなりお好きなように。