...
This project is all about developing a tree layout algorithm. We pity the fool who doesn't use Mr. Tree Layout!
This page will over time be filled with documentation written by the project team. But first, here's some The general information to get you started:
| Project Team |
| |
| Project Goals | The following are our the main goals for this project:
| |
| Plug-in Name | de.cau.cs.kieler.klay.tree | |
| Repository | KIELER Pragmatics | Branches |
| Example |  |
Page Contents
| Table of Contents | ||
|---|---|---|
|
Literature
Related publications:
- J. Q. Walker, II. 1990. A node-positioning algorithm for general trees. Softw. Pract. Exper. 20, 7 (July 1990), http://www.cs.unc.edu/techreports/89-034.pdf
- A. Rusu, Rowan University, Tree drawing algorithms, http://cs.brown.edu/~rt/gdhandbook/chapters/trees.pdf
- Kaufmann, M., & Wagner, D. (Eds.). (2001). Drawing graphs: methods and models (Vol. 2025). Springer.
Architecture
Mr. Tree is structured the same as its big brother KLay Layered. It consists of layout phases, intermediate processors, and a connected components processor. The picture below describes the control flow and therefore what is done when the tree algorithm operates.
The first thing that is done is the graph import. Since the algorithm works with KIML it is necessary to import the graph that should be layouted with Mr. Tree. The important data structure (KGraph) is a comparatively complex structure. The tree algorithm does not need all parts of this data structure, so the parts that are necessary are converted into a less complex data structure, the MrTGraph data structure (TGraph), which is described through a class diagram below. As mentioned before, Mr. Tree runs on that data structure. After execution of the tree algorithm, the TGraph gets reconverted to a KGraph in a graph export phase, so that everything works fine with KIML.
The heart of Mr. Tree are the following phases. They are described in more details on this page.
The first phase is named which the comparatively unfamiliar term "treeing". "Treeing" is a word that describes a process that builds a tree out of a graph that is no tree. In other words: Mr. Tree should also operate on graphs that are no trees, but that can be converted into trees. Imagine a graph that is nearly a tree. It contains one cycle that destroys the tree property. Now the first phase should detect that cycle, destroy it by removing the edge that destroys the tree property and reinsert that edge again after the tree algorithm was able to operate on that newly build tree.
Phase 2 and 3 calculate a place for every node in the layout. In phase 2 the nodes are ordered. They ordering depends on the maximal fan-out of every node. That means that nodes with many offspring and many following levels should be placed before nodes that do not have that many offspring or following levels. This phase computes such a node ordering. Phase 3 then placed the nodes. For placing the nodes, we use the algorithm developed by Walker et al. They developed a node positioning algorithm for general trees, that calculates coordinates for each node. This coordinates depend on many factors, such as position in a tree, number of offspring/ancestors and so on. A more detailed look can be found in the paper of Walker et al. which we also referenced in the Literature Section of this page.
The last phase of Mr. Tree is a simple edge-routing that simply connects the previously placed nodes directly.
MrTGraph Data Structure
The MrTGraph data structure is best explained by looking at the following diagram:
The basic data structure constis of the three classes TNode, TGraph and TEdge, which contain all the necessary properties to model a tree data structure. Therefore a TGraph consits of sets of TEdges and TNodes.
The TNodes are objects of the type TShape. That means that a nodes' size and position is defined by the attributes defined in the class TShape. The class TShape is an abstract superclass for the class TGraphElement. So the class TGrahpElement provides the utilites to declare any generic graph element of which a TGraph consits of.
...
Mr. Tree is a layout algorithm for trees. It uses the algorithm from A Node-Positioning Algorithm for General Trees, John Q.Walker II 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 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.
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.
Options
Currently only the node weighting for the node order can be changed by the user through the option: Weighting of Nodes
The possibilities for "Weighting of Nodes" are:
- DESCENDANTS: The weighting of a node is the number of nodes in the subtree starting at the corresponding node.
- FAN: The weighting of a node is the maximal number of nodes in the same level of the subtree starting at the corresponding node.
Literature
Related publications:
- J. Q. Walker, II. 1990. A node-positioning algorithm for general trees. Softw. Pract. Exper. 20, 7 (July 1990)
- A. Rusu, Rowan University, Tree drawing algorithms
- Wetherell, C.S. and A. Shannon. Tidy Drawings of Trees. IEEE Trans- actions on Software Engineering SE-5, 5 (September 1979) 514-520.
Features
Mr.Tree is a layout algorithm that lays out a graph in a tree layout. It contains the following features:
- Support for connected componentsSupport for node and edge labelsgraphs with cycles or other graphs that are hardly trees
- Support of aesthetic rules as described in Wetherell and Shannon
- Support of whitespace reduction
Some other features that can be thought of being implemented in the future:
- Support for graphs with cycles or other graphs that are hardly treesnode and edge labels
- Support for portsLayout options for customizing the algorithmdifferent weighting option
- Support for different edge routings
- Different kinds of tree layouts (top-down tree, left-to-right tree, radial tree...)
...