Wiki source code of KLay Mr. Tree
Version 4.1 by sgu on 2013/08/20 14:35
Show last authors
| author | version | line-number | content |
|---|---|---|---|
| 1 | 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! | ||
| 2 | |||
| 3 | The general information to get you started: | ||
| 4 | |||
| 5 | |(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %) | ||
| 6 | ((( | ||
| 7 | **Project Team** | ||
| 8 | )))|((( | ||
| 9 | * Sven Oliver Reimers (sor) | ||
| 10 | * Sven Gundlach (sgu) | ||
| 11 | ))) | ||
| 12 | |(% class="highlight-grey" colspan="1" data-highlight-colour="grey" %)(% class="highlight-grey" colspan="1" data-highlight-colour="grey" %) | ||
| 13 | ((( | ||
| 14 | **Project Goals** | ||
| 15 | )))|(% colspan="1" %)(% colspan="1" %) | ||
| 16 | ((( | ||
| 17 | The following are the main goals for this project: | ||
| 18 | |||
| 19 | * Develop a good, robust tree-based layout algorithm that can be published and shipped as part of our KLay library. | ||
| 20 | * Supply useful documentation, both on this page (project-centric) as well as on a new page in the KIELER Wiki (user-centric). | ||
| 21 | ))) | ||
| 22 | |(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %) | ||
| 23 | ((( | ||
| 24 | **Plug-in Name** | ||
| 25 | )))|((( | ||
| 26 | {{code language="none"}} | ||
| 27 | de.cau.cs.kieler.klay.tree | ||
| 28 | {{/code}} | ||
| 29 | ))) | ||
| 30 | |(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %) | ||
| 31 | ((( | ||
| 32 | **Repository** | ||
| 33 | )))|((( | ||
| 34 | [[KIELER Pragmatics>>url:https://git.rtsys.informatik.uni-kiel.de/projects/KIELER/repos/pragmatics/browse||shape="rect"]] | ||
| 35 | ))) | ||
| 36 | |(% class="highlight-grey" colspan="1" data-highlight-colour="grey" %)(% class="highlight-grey" colspan="1" data-highlight-colour="grey" %) | ||
| 37 | ((( | ||
| 38 | **Example** | ||
| 39 | )))|(% colspan="1" %)(% colspan="1" %) | ||
| 40 | ((( | ||
| 41 | [[image:attach:randomWeb.png]] | ||
| 42 | ))) | ||
| 43 | |||
| 44 | ** | ||
| 45 | ** | ||
| 46 | |||
| 47 | **Page Contents** | ||
| 48 | |||
| 49 | |||
| 50 | |||
| 51 | {{toc minLevel="2"/}} | ||
| 52 | |||
| 53 | |||
| 54 | |||
| 55 | 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. | ||
| 56 | |||
| 57 | 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. | ||
| 58 | |||
| 59 | == Options == | ||
| 60 | |||
| 61 | Currently only the node weighting for the node order can be changed by the user through the option: Weighting of Nodes | ||
| 62 | |||
| 63 | The possibilities for "Weighting of Nodes" are: | ||
| 64 | |||
| 65 | * DESCENDANTS: The weighting of a node is the number of nodes in the subtree starting at the corresponding node. | ||
| 66 | * FAN: The weighting of a node is the maximal number of nodes in the same level of the subtree starting at the corresponding node. | ||
| 67 | |||
| 68 | == Literature == | ||
| 69 | |||
| 70 | Related publications: | ||
| 71 | |||
| 72 | * [[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"]] | ||
| 73 | * [[A. Rusu, Rowan University, Tree drawing algorithms>>url:http://cs.brown.edu/~~rt/gdhandbook/chapters/trees.pdf||shape="rect"]] | ||
| 74 | * ((( | ||
| 75 | [[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"]] | ||
| 76 | ))) | ||
| 77 | * [[Wetherell, C.S. and A. Shannon. Tidy Drawings of Trees. IEEE Trans- actions on Software Engineering SE-5, 5 (September 1979) 514-520.>>url:http://www.computer.org/csdl/trans/ts/1979/05/01702661-abs.html||shape="rect"]] | ||
| 78 | |||
| 79 | == Features == | ||
| 80 | |||
| 81 | Mr.Tree is a layout algorithm that lays out a graph in a tree layout. It contains the following features: | ||
| 82 | |||
| 83 | * Support for graphs with cycles or other graphs that are hardly trees | ||
| 84 | * Support of aesthetic rules as described in Wetherell and Shannon | ||
| 85 | * Support of whitespace reduction | ||
| 86 | |||
| 87 | Some other features that can be thought of being implemented in the future: | ||
| 88 | |||
| 89 | * Support for node and edge labels | ||
| 90 | * Support for different (% lang="en" class="short_text hps" %)weighting(% class="short_text" lang="en" %) (% lang="en" class="short_text hps" %)option | ||
| 91 | * Support for different edge routings | ||
| 92 | * Different kinds of tree layouts (top-down tree, left-to-right tree, radial tree...) | ||
| 93 | |||
| 94 | |||
| 95 | |||
| 96 |