More Related Content
What's hot (20)
More from mfumi (12)
木を綺丽に描画するアルゴリズム
- 2. どうやって木を描画するか？ ? 木はグラフの一部なので描画方法はいろいろ ? どうやったら綺麗に描画できる? ? 以下，とりあえず2分木を対象
- 3. 描画原則 1. 親は子より上に描画? 特に2分木なら左の子は親より左，? 右の子は親より右に描画 2. 辺は交差しない 3. 同じ深さのノードは同じ高さで描画
- 5. (多分)一番简単な方法 ? 木をpre-orderで探索 ? x = 0から初めて探索していったノードから順に左 からx方向の値を割り振る ? 一説によるとknuthが考えたらしい? (というかknuthが1971年に出した論文のサンプルコードで使われていた手法)
- 6. (多分)一番简単な方法
- 7. (多分)一番简単な方法
- 8. (多分)一番简単な方法の問題 ? 木がだいたいバランスしている場合はこれでも十分 ? でも，木が偏っていると不格好になりがち ? 何がいけないのか? 1. 深さに対するノード数によらずx方向が決定される? => 結果として横にひろがりやすい 2. 2分木なのに親が子の中央に位置していない
- 9. 描画原則 改 1. 親は子より上に描画? 特に2分木なら左の子は親より左，? 右の子は親より右に描画 2. 辺は交差しない 3. 同じ深さのノードは同じ高さで描画 4. なるべく狭く描画する 5. 親は子の中央に位置させる
- 11. 狭く描画する
- 12. 亲を子の中央に配置する ? pre-orderで探索するとノードを描画するとき右の 子の位置が確定していない ? post-orderで探索し， ? 葉にはその深さで配置可能な場所に左詰めで配置 ? 親は子ノードの中央に配置? このとき，親の位置が親の深さで配置可能な場合より左の場合には，その 親をルートとするサブツリー全体をその分だけ右にシフトする
- 13. 亲を子の中央に配置する
- 15. 描画原則 改二 1. 親は子より上に描画? 特に2分木なら左の子は親より左，? 右の子は親より右に描画 2. 辺は交差しない 3. 同じ深さのノードは同じ高さで描画 4. なるべく狭く描画する 5. 親は子の中央に位置させる 6. 任意のサブツリーは場所によらず同じように描画する
- 16. Tilford-Reingold アルゴリズム ? 1980年考案 ? post-order で探索し， ? ノードが葉ならそのノードのx位置は0とする ? そうでなければ，右の子を左の子にできるだけ近づける ? 親の位置を子ノードの中央に設定 ? 単純そうに見えるが，実際には親の位置を決定するのに少し工夫 が必要 ? ちなみに，グラフ描画アルゴリズムのFruchterman-ReingoldアルゴリズムのReingoldと同じ人
- 18. 描画アルゴリズムのオーダー ? Tilford-Reingold アルゴリズムは，サブツリーの シフトが再帰的が発生するが，少し計算を工夫する ことでO(n^2) ? Tilford-Reingold を改良して，木の描画をO(n)で 配置するアルゴリズムが考案されているらしい? (末尾の文献を参照)
- 19. m分木への拡張 ? 今までは2分木を対称としていたが，Tilford- Reingoldアルゴリズムをm分木に拡張するのはそ れほど難しくない(はず) ? ようするに子の中央に親を配置するのがポイント
- 20. ところで，DOT ? グラフ記述言語? ex)? ? ? ? Graphvizの内部で使用 ? これで書いておけばGraphvizで描画できる? (他にも対応しているものはいろいろ) ? いちいちアルゴリズムを実装していられない時に ? DOTはあくまでグラフ描画用だが，Graphvizで木構造のレイアウトとして描画す ることができるらしい
- 21. DOT
- 22. (補足)? 木の描画方法の超簡単な歴史 ? 1971年: knuthの論文に描画のソースコードが載る? もっと前から何かあったかも ? 1979年: C.WetherellとA.Shannonが木の描画方法に関する論文を発表．これ 以降の論文の基礎になる (ちゃんと読んで無いけど多分このスライドの親を中央 に配置する方法を発表) ? 1980年: Tilford-Reingold アルゴリズム ? 1990年: Tilford-Reingold アルゴリズムを改良した方法をJ.Q.Walkerが発表． ? 2006年: Walker アルゴリズムがO(n^2)だったものを線形にしたアルゴリズム(?) をC.Bucheimらが考案? ちゃんとやるならこれを読めば良さげ
- 23. 参考文献 ? Bill Mil, Drawing Presentable Trees, http://billmill.org/pymag-trees/#foot1? 木の描画方法についてまとまっています．今回の作成にあたり一番参考にしました ? C. Wetherell and A. Shannon. 1979. Tidy Drawings of Trees. IEEE Trans. Softw. Eng. 5, 5 (September 1979), 514-520. DOI=10.1109/TSE.1979.234212 ? Reingold, Edward M.; Tilford, J.S., "Tidier Drawings of Trees," Software Engineering, IEEE Transactions on , vol.SE-7, no.2, pp.223,228, March 1981. doi: 10.1109/TSE.1981.234519 ? J. Q. Walker, II. 1990. A node-positioning algorithm for general trees. Softw. Pract. Exper. 20, 7 (July 1990), 685-705. DOI=10.1002/spe.4380200705 ? Christoph Buchheim, Michael Jünger, and Sebastian Leipert. 2006. Drawing rooted trees in linear time. Softw. Pract. Exper. 36, 6 (May 2006), 651-665. DOI=10.1002/spe.v36:6