Layout-Praktikum SS 13
Child pages
  • Mr. Tree Layout (sgu, sor)
Skip to end of metadata
Go to start of metadata

You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 17 Next »

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
  • Sven Gundlach (sgu)
  • Sven Oliver Reimers (sor)
Project Goals

The following are our main goals for this project:

  • Develop a good, robust tree-based layout algorithm that can be published and shipped as part of our KLay library.
  • Supply good, useful documentation, both on this page (project-centric) as well as on a new page in the KIELER Wiki (user-centric).
Plug-in Namede.cau.cs.kieler.klay.tree
RepositoryKIELER Pragmatics
Branches
  • Main tree layout branch: prak/treelayout
  • Further development branches can be forked from the main tree layout branch; names should begin with prefix prak/


Page Contents

 

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. 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.

 

The processors can determine roots of components and fan outs or level neighbors of nodes.

Literature

Related publications:

Features

Mr.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...)

 

 

  • No labels