Udo Borkowski is an independent software engineer, consultant, and coach with over 20 years of experience in various facets of software development. Udo has worked on clinical research systems, health care management, operating systems, visualization, database engines, user interface design, cross-platform systems, energy management, workflow systems, and insurance management. Udo is the founder of abego Software GmbH, Aachen (www.abego.org). Udo has posted 1 posts at DZone. View Full User Profile

Efficient and Customizable TreeLayout Algorithm in Java

10.22.2011
| 11409 views |
  • submit to reddit
The Java TreeLayout described below creates tree layouts for arbitrary trees. It is not restricted to a specific output or format, but can be used for any kind of two dimensional diagram. Examples are Swing based components, SVG files, and many more. This is possible because TreeLayout separates the layout of a tree from the actual rendering.

To use the TreeLayout you mainly need to supply an instance of the TreeLayout class with the nodes of the tree (including "children" links), together with the "size" of each node. In addition you can configure the layout by specifying parameters like "gap between levels" etc..

Based on this information TreeLayout creates a compact, nice looking layout. The layout has the following properties [2]:

  1. The layout displays the hierarchical structure of the tree, i.e. the y-coordinate of a node is given by its level.
  2. The edges do not cross each other and nodes on the same level have a minimal horizontal distance.
  3. The drawing of a subtree does not depend on its position in the tree, i.e. isomorphic subtrees are drawn identically up to translation.
  4. The order of the children of a node is displayed in the drawing.
  5. The algorithm works symmetrically, i.e. the drawing of the reflection of a tree is the reflected drawing of the original tree.

Here an example tree layout:

Content

 

Download and Installation

 

NetBeans and abego TreeLayout

The NetBeans Visual Library API already includes an algorithm to lay out trees (and graphs in general). However, the default implementation of the NetBeans Visual Library does not always generate layouts as compact as the abego TreeLayout implementation:

Layout using abego TreeLayout Layout using NetBeans' default Tree GraphLayout

Both screenshots are taken from the demo application in the "org.abego.treelayout.netbeans.demo" project, also provided in the sources. The demo project includes the "org.abego.treelayout.netbeans" library to easily access the abego TreeLayout algorithm from standard NetBeans visual code.

As the following comparision shows using the abego TreeLayout in NetBeans visual code is as simple as using the standard GraphLayout:

Use abego TreeLayout to create a SceneLayout:

AbegoTreeLayoutForNetbeans<N, E> graphLayout = 
        new AbegoTreeLayoutForNetbeans<N, E>(root, 100, 100, 50, 50, true);
SceneLayout sceneLayout = LayoutFactory.createSceneGraphLayout(scene,graphLayout);
...

Use NetBeans' default Tree GraphLayout to create a SceneLayout:

GraphLayout<N, E> graphLayout = 
        GraphLayoutFactory.createTreeGraphLayout(100, 100, 50, 50, true);
GraphLayoutSupport.setTreeGraphLayoutRootNode(graphLayout, root);
SceneLayout sceneLayout = LayoutFactory.createSceneGraphLayout(scene, graphLayout);
...

 

Documentation

For detailed documentation see the javaDoc in the source code and this pdf document.

In addition you may also find the example code helpful. It is included in the "demo" packages.

 

Algorithm Performance

Based on Walker's algorithm [1] with enhancements suggested by Buchheim, Jünger, and Leipert [2] the software builds tree layouts in linear time. I.e. even trees with many nodes are built fast. Other than with the Reingold–Tilford algorithm [3] one is not limited to binary trees.

In a benchmark the algorithm could layout trees with a speed of approx. 5 micro seconds per node. (Running on a 2.4 GHz Intel Core 2 Duo machine).

 

Development

You may check out the TreeLayout source code from the TreeLayout SVN repository.

The projects contain configurations for the Eclipse and NetBeans IDEs as well as ANT scripts to build them.

 

License

abego TreeLayout is distributed under a BSD license of abego Software. (License text)

 

References

[1] Walker JQ II. A node-positioning algorithm for general trees. Software—Practice and Experience 1990; 20(7):685–705.

[2] Buchheim C, Jünger M, Leipert S. Drawing rooted trees in linear time. Software—Practice and Experience 2006; 36(6):651–665

[3] Reingold EM, Tilford JS. Tidier drawings of trees. IEEE Transactions on Software Engineering 1981; 7(2):223–228.

Published at DZone with permission of its author, Udo Borkowski.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)