Mr. Tree Layout Algorithm
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 general information to get you started:
Project Team |
|
Project Goals | The following are our main goals for this project:
|
Plug-in Name | de.cau.cs.kieler.klay.tree |
Repository | KIELER Pragmatics |
Branches |
|
Page Contents
Schedule
Some Ideas...
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 | Review tree layout methods and make a first decision on which ones are to be implemented. Presentation in weekly meeting. |
Literature Review
Some Ideas...
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
Some Ideas...
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
Some Ideas...
Since you won't want to directly work on the input KGraph
, you will need a custom data structure to represent graphs, called the MrTGraph
. For examples of such data structures, you can have a look at some of the following layout algorithms:
- KLay Layered uses the
LGraph
structure. - KLay Force uses the
FGraph
structure. - KLay Planar uses the
PGraph
structure.
All of these structures have in common that they don't necessarily model every property that might conceivably be used in the algorithm. Instead, graph structure members are property holders, which makes it easy to set an arbitrary amount of properties on them. To understand why this might make sense, look at KIML's LayoutOptions
class or KLay Layered's Properties
class. Both classes define a bunch of properties that can be set on graph elements.
Features
Some Ideas...
The bottom line is to develop an algorithm that lays out a graph in a tree layout. Here a some first ideas for further features you might look into.
- Support for connected components
- Different kinds of tree layouts (top-down tree, left-to-right tree, radial tree...)
- Support for node and edge labels
- Support for graphs with cycles
- Support for ports
- Layout options for customizing the algorithm
Feel free to think about further ways to enhance the algorithm. Make sure to set priorities and to properly divide responsibilities among the team members.