...
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 | ||
---|---|---|
|
Schedule
Info | ||
---|---|---|
| ||
Use this section to keep a schedule of milestones that you want to achieve, together with deadlines. This will help you to get work done on time, and it will help us to keep an overview of your project's status. |
Deadline | Milestone |
---|---|
2013-05-02 2013-05-10 | Review tree layout methods and make a first decision on which ones are to be implemented. Presentation in weekly meeting. Create and implement the start of the MrTGraph data structure. Presentation in weekly meeting. |
Literature Review
Info | ||
---|---|---|
| ||
Start by reading the papers Miro has already sent you. Going from there, decide what you'd like to implement and possibly read further papers. Collect paper references in this section so that you (and we) will be able to find them again. |
Architecture
Info | ||
---|---|---|
| ||
You will have to think about how you are going to implement your algorithm. One possible architecture is to divide the work of the algorithm into sub-algorithms, called phases. This makes it easy to provide different implementations of phases that result in different kinds of tree layouts. KLay Layered uses this approach. You can find some documentation about this approach on its Confluence page. Further information can be found in a paper we just wrote, but haven't published yet. If you are interested in reading it, feel free to ask for a copy of the paper. Remember: This will probably not be the only possibility for structuring your algorithm. Also remember: What starts with a first small and simple implementation will grow into a much more complex algorithm, with possibilities for customizing the result and different kinds of layouts that are computed. Design your architecture with this kind of complexity in mind. Feel free to talk to us once you've settled on an architecture. |
MrTGraph Data Structure
Info | ||
---|---|---|
| ||
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. Since an input KGraph is transformed into a TGraph, so that our algorithms can work on that TGraph, we do want to have the opportunity to set specific properties on graph elements. That is what the class TGraphElement is for. This specific way of implementation allows us not to model every property itself, but to model a class which can set an abritrary amount of properties on the graphs' elements. This data structure provides all the needs to perform a transformation from a KGraph to a TGraph that is as easy and therefore as evident as possible. |
Features
...
title | Some Ideas... |
---|
...
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 graphs 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 node and edge labels
- Support for different weighting option
- Support for different edge routings
- Different kinds of tree layouts (top-down tree, left-to-right tree, radial tree...)
...