Skip to Content

Changes for page KLay Mr. Tree

Last modified by Richard Kreissig on 2023/09/14 10:23
From version 8.6
edited by msp
on 2023/07/11 10:33
Change comment: Update document after refactoring.
To version 9.1
edited by Richard Kreissig
on 2023/09/14 10:23
Change comment: There is no comment for this version

Summary

Details

Page properties
Author
... ... @@ -1,1 +1,1 @@
1 -XWiki.msp
1 +XWiki.stu230980
Content
... ... @@ -1,8 +1,7 @@
1 -{{panel title="Project Overview"}}
1 +== Project Overview ==
2 2  Responsible:
3 3  
4 4  * {{mention reference="XWiki.cds" style="FULL_NAME" anchor="XWiki-cds-KlptB"/}}
5 -{{/panel}}
6 6  
7 7  This project is all about developing a tree layout algorithm. [[We pity the fool>>url:http://www.youtube.com/watch?v=DJnKm6ftPu0||shape="rect"]] who doesn't use Mr. Tree Layout!
8 8  
... ... @@ -12,9 +12,8 @@
12 12  
13 13  {{toc minLevel="2"/}}
14 14  
15 -
16 16  
17 -Mr. Tree is a layout algorithm for trees. It uses the algorithm from [[A Node-Positioning Algorithm for General Trees, John Q.Walker II>>url:http://dl.acm.org/citation.cfm?id=79026||shape="rect"]] to layout trees. To do this it uses four phases plus a pre-processing to build a corresponding data structure. The first phase "treeifying" transforms the given graph into a tree if necessary. To do this, edges which destroy the tree property will be removed and stored, so that they can be reinserted during a post processing. In the second phase "orderNodes" the nodes of each level are separated into leaves and inner nodes. Inner nodes are (% lang="en" class="short_text hps" %)arranged(%%) into the middle of the level and then whitespace in the level is filled with leaves. The third phase "NodePlacer" uses the algorithm first mentioned from John Q.Walker II to compute the actual position of the nodes. The last phase routeEdges sets the positions for the edges corresponding to the positions of the nodes.
15 +Mr. Tree is a layout algorithm for trees. It uses the algorithm from [[A Node-Positioning Algorithm for General Trees, John Q.Walker II>>url:http://dl.acm.org/citation.cfm?id=79026||shape="rect"]] to layout trees. To do this it uses four phases plus a pre-processing to build a corresponding data structure. The first phase "treeifying" transforms the given graph into a tree if necessary. To do this, edges which destroy the tree property will be removed and stored, so that they can be reinserted during a post processing. In the second phase "orderNodes" the nodes of each level are separated into leaves and inner nodes. Inner nodes are (% class="hps short_text" lang="en" %)arranged(%%) into the middle of the level and then whitespace in the level is filled with leaves. The third phase "NodePlacer" uses the algorithm first mentioned from John Q.Walker II to compute the actual position of the nodes. The last phase routeEdges sets the positions for the edges corresponding to the positions of the nodes.
18 18  
19 19  Each phase uses intermediate processors for small computations on the graph. The corresponding processors are defined in each phase. Some are defined multiple times, but they are invoked only once between phases.
20 20  
... ... @@ -32,7 +32,7 @@
32 32  Related publications:
33 33  
34 34  * [[J. Q. Walker, II. 1990. A node-positioning algorithm for general trees. Softw. Pract. Exper. 20, 7 (July 1990)>>url:http://dl.acm.org/citation.cfm?id=79026||shape="rect"]]
35 -* [[A. Rusu, Rowan University, Tree drawing algorithms>>url:http://cs.brown.edu/~~rt/gdhandbook/chapters/trees.pdf||shape="rect"]]
33 +* [[A. Rusu, Rowan University, Tree drawing algorithms>>url:http://cs.brown.edu/~~rt/gdhandbook/chapters/trees.pdf||shape="rect"]]
36 36  * (((
37 37  [[Kaufmann, M., & Wagner, D. (Eds.). (2001). Drawing graphs: methods and models (Vol. 2025). Springer>>url:http://dl.acm.org/citation.cfm?id=376944&coll=DL&dl=GUIDE&CFID=239149682&CFTOKEN=43363665||shape="rect"]]
38 38  )))
... ... @@ -49,10 +49,8 @@
49 49  Some other features that can be thought of being implemented in the future:
50 50  
51 51  * Support for node and edge labels
52 -* Support for different (% lang="en" class="short_text hps" %)weighting(% class="short_text" lang="en" %) (% lang="en" class="short_text hps" %)option
50 +* Support for different (% class="hps short_text" lang="en" %)weighting(% class="short_text" lang="en" %) (% class="hps short_text" lang="en" %)option
53 53  * Support for different edge routings
54 54  * Different kinds of tree layouts (top-down tree, left-to-right tree, radial tree...)
55 55  
56 -
57 57  
58 -