有向非巡回グラフを綺麗に描くアルゴリズム (？)
有向非巡回グラフ
以前のブログで僕は「図は単純化して描け！もしあなたの描く図が複雑なら，それはあなたが対象を十分に理解していないことを意味する」という趣旨を書いた．対象を十分に理解している人なら，その意味的構造を綺麗に抽象した図を描ける．汚い図は理解不足の証拠なんだと．
その意味で，Wikipedia の有向非巡回グラフ (Directed Acyclic Graph, DAG) のページに載ってるグラフの例は面白い．単純な見た目ながら，思ったよりは意外と複雑なのだ．
上掲した Wikipedia のグラフは複雑だ．次のような構造を一見して見抜くのは難しい．こうした汚い図を見ると，僕は意味的構造を抽象して綺麗な図を作りたくなるんです．
- どこに始点 (入力辺を持たないノード) があるのか？
- どこに終点 (出力辺を持たないノード) があるのか？
- 中間ノード (始点でも終点でもないノードを，ここではそう呼ばせてください) はあるか？
- あるとすれば何個あるか？
“綺麗な図” を描くとすれば？
下に載せるのが，僕が最善と思う”綺麗な図”．この図が，冒頭に載せた Wikipedia の図よりも優れている点は，以下の5点．
- 始点が上段に集まっていること．それにより始点が3つあることが，一見して分かること
- 終点が下段に集まっていること．それにより終点が3つあることが，一見して分かること
- 中間ノードが中段に集まっていること．それにより中間ノードが2つあることが，一見して分かること
- すべての辺の向きが，必ず「上から下」の向きに揃っていること
- 計8つのノードが，幾何学的に整然に，3×3 の格子に乗って配置されていること
しかし，それでも「これがベストだな」と思える綺麗さの図にはなってない．Wikipedia が載せてる図は，実は想像以上に複雑だった．具体的には，できれば辺を交差させずに書きたかったんだけど，今回のグラフではそのような図の書き方は，どうやら不可能っぽい．
整然は，アルゴリズムで生み出せる
まず汚いグラフを整理するには，始点と終点とそれ以外をズバッと分類してやるのがいい．そして始点を上段に，終点を下段に，それ以外を中段 (今回は中段は1行で済んだけど，複数行が必要になることもあるでしょう) に置く．その整理のあとで，「では，何x何 の格子の上にノードを配置すればいいかな？」という全体構造を決める．今回は始点 3個，終点 3個，中間ノードが2個だったので，3×3 の格子を使えば良さそうだと見当がつく．
次に，最大次数のノード (最も多くの辺が差さってるのノード) を探す．今回の場合，それはノード 11 で，入力辺 2本と出力辺 3本がある．ノードを 3×3 の格子状に配置することを考えると，次数の大きいはど真ん中に配置したい．ど真ん中であれば，今回の場合は出力辺を左右対称に描けて，図形的に美しくできるから．
それと特例的に，始点 3 から終点 10 への辺は，できれば斜めにせず垂直に描きたい．図の中で最も長い辺が斜めになってると，図全体としての視覚的安定感を損なうからね．当然 3 と 10 の間にはノードがないので，3 と 10 は縦の同じ列に位置する必要があって，かつ中央の列ではダメだ (なぜなら中央には 11 が位置取ってるから)．
…と，全体を整然と配置するための合理的な制約を課していくと，上掲した以外の表示方法が無いのよね．2 と 9，5 と 7 は交換可能ではあるけど，やってみればすぐに分かる通り，不要な辺の交差を増やしてしまうだけで良くない．このグラフを僕なりに整理して書くなら，上掲の通り，2箇所の辺の交差を許容せざるを得ない．
もう1点，妥協なのは，3 → 8 の辺が他の斜めの辺と傾きが違うこと．他はどれも1つ隣の列に向かう斜め線なのに対して，3 → 8 の辺だけ2つ隣の列に向かってる．これが図の統一感を損なって美しさを欠く要因になってるんだけど，やっぱり避けようがない．
というわけで，Wikipedia に載ってる「有向非巡回グラフ」の例のグラフは，案外複雑なのでした．
