What is it, naokirin?

木構造を描くアルゴリズムについて(Reingold-Tilford Algorithm)

最近、UnityでPlayable APIというものを調べる機会がありました。

その際にそのPlayableの木構造をUnity上で表示できるEditor拡張としてPlayableGraphVisualizerというものがあると知ったので軽く見ていて、「Reingold Tilford」というものが出てきて調べていたので、それをまとめておきます。

(ちなみに、PlayableGraphVisualizer - https://bitbucket.org/Unity-Technologies/playablegraphvisualizer

結論としてはこの「Reingold Tilford」は「Reingold Tilford アルゴリズム」と呼ばれるもので、木構造を階層的に“きれいに”表示するためのアルゴリズムです。木構造のグラフ表示の機能を持ったJavascriptのライブラリなどではこの単語が出てくることもあるようですが、私は初めて見ました。

木構造を綺麗に描くための手法と歴史

いろいろ調べていて、非常に参考になったのが以下のサイトでした。

http://billmill.org/pymag-trees/

このサイトでは階層的な木構造の表示として、どのようなアルゴリズムを使えば、きれいな配置ができるか、またその法則や歴史的な流れについて非常にわかりやすくまとまっていました。

ざっくりそこで書かれている歴史(引用された論文+α)を書き出すと以下のような歴史になるようです。

  • 1971年:Knuth が「Optimum binary search trees」という論文の中でサンプルコードとして利用していた手法
  • 1979年:Whetherell, Shannon が「Tidy Drawings of Trees, IEEE Transactions on Software Engineering. Volume 5, Issue 5」で紹介した手法
  • 1981年:Reingold, Tilford が「Tidier Drawings of Trees, IEEE Transactions on Software Engineering. Volume 7, Issue 2」で紹介した手法(これがReingold Tilford アルゴリズム
  • 1990年:Walker が「A node-positioning algorithm for general trees」でReingold Tilfordの手法を改良してO(n2)にした手法
  • 2002年:Buchheim, Unger, Leipert が 「Improving Walker's algorithm to run in linear time.」でWalkerの手法をO(n)にした手法

意外と最近まで線形時間になっていなかったReingold Tilfordアルゴリズムですが、より大きなデータを扱うことが多くなった現代ではとくにその重要性が高いのではないかと思います。

Reingold Tilford アルゴリズムとは

本題ですが、正直上記で上げたURLの先を見てもらったほうが圧倒的にわかりやすく正確な情報になりそうなので、基本的にはそちらを参考にしてもらえれば良いかなと思います。

ちなみに木構造を“きれいに”表示するために、そもそも“きれいに”表示するためには何を守っていればいいのか、というのが重要になります。 Reingold Tilford アルゴリズムでは以下の5つが守られるようになっています。

  1. 木のエッジがその他のエッジと重ならない
  2. 同じ深さにあるノードが同じ水平のライン上にある
  3. 木が出来る限り狭く描かれる
  4. 親のノードがその子のノードの中央に描かれる
  5. サブツリーがどこに存在しても、同じ構造のサブツリーが同じように描かれる

これらを守るようにして描かれた木構造がこれになります。(Unity上で木構造をReingold Tilfordアルゴリズムでかけるようにして、表示してみたものです)
f:id:naokirin:20160213224723p:plain

どうでしょうか、木構造自体のバランスが悪いものの、表示としてはかなりバランスよく描かれているのではないでしょうか。

今後木構造をこのような形で描画する機会があったら、Reingold Tilfordアルゴリズムというものがあって、今はO(n)の手法が存在する、ということを思い出してもらえればと思います。そもそもこういうのは出来る限りライブラリなどに任せてしまうが良さそうですw

もし良いライブラリが見つからない時は、参考にしてみてください。