...
| 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
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
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. |
- 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
KLay 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 KLay Tree operates.
The first thing that is done is the graph import. Since KLay Tree works with KIML it is necessary to import the graph that should be layouted with KLay Tree. The data structure that gets important is a comparatively complex structure. KLay Tree does not need all parts of this data structure, so the parts that are necessary get converted into a less complex data structure, the MrTGraph data structure (TGraph), which is described through a class diagram below. As mentioned before, KLay Tree runs on that data structure. After execution of KLay Tree, the TGraph gets reconverted to a KGraph in a graph export phase, so that everything works fine with KIML.
The heart of KLay 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: KLay 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 KLay tree 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 KLay 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:
...
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... |
|---|
...
KLay Tree is a layout algorithm that lays out a graph in a tree layout.
...
It contains the following features:
- Support for connected components
...
- Support for node and edge labels
Some other features that can be thought of being implemented in the future:
- Support for graphs with cycles or other graphs that are hardly trees
- Support for ports
- Layout options for customizing the algorithm
...
- Different kinds of tree layouts (top-down tree, left-to-right tree, radial tree...)