abego TreeLayout
Efficient and Customizable Tree Layout Algorithm in Java
Overview
The TreeLayout 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]:
- The layout displays the hierarchical structure of the tree, i.e. the y-coordinate of a node is given by its level.
- The edges do not cross each other and nodes on the same level have a minimal horizontal distance.
- The drawing of a subtree does not depend on its position in the tree, i.e. isomorphic subtrees are drawn identically up to translation.
- The order of the children of a node is displayed in the drawing.
- 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:
Download and Installation
- Sources: https://github.com/abego/treelayout
- JAR files:
- http://sourceforge.net/projects/treelayout/files/org.abego.treelayout.core.jar/download: the TreeLayout algorithm core.
- http://sourceforge.net/projects/treelayout/files/org.abego.treelayout.netbeans.jar/download: use the TreeLayout algorithm for the NetBeans visual API (GraphLayout, …). (When using this JAR make sure the NetBeans libraries ‘org.netbeans.api.visual’, ‘org.openide.util’, and ‘org.openide.util.lookup’ are in the classpath.)
- for more files (e.g. older or specific versions) see the download page.
- Twitter: @abego (e.g. for announcement of new releases)
TreeLayout is also available from Maven Central. You may want to add this to your POM:
<dependencies>
...
<dependency>
<groupId>org.abego.treelayout</groupId>
<artifactId>org.abego.treelayout.core</artifactId>
<version>1.0.3</version>
</dependency>
...
</dependencies>
Development
You may check out the TreeLayout source code from the GitHub repository.
The projects contain configurations for the Eclipse and NetBeans IDEs as well as ANT scripts to build them. Maven is also supported.
NetBeans and abego TreeLayout
The NetBeans Visual API already includes an algorithm to layout trees (and graphs in general). However the default implementation of NetBeans 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 comparison 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.
The following figure shows the results running the TreeLayout algorithm on a MacBook Pro 2.4 GHz Intel Core 2 Duo (2 GB Memory (-Xmx2000m)). The variously sized trees were created randomly.
The picture illustrates the linear time behavior of the algorithm and shows the applicability also for large number of nodes. In this setting it takes approx. 5 μs to place one node.
Known Usages
- In Mario AI Marcus Andersson uses genetic algorithms to evolve behavior trees, and other AIs, written in C++ that he ported to a Super Mario game written in Java. abego TreeLayout does the layouting of the behavior trees. Have a look at this video to see Mario AI and abego TreeLayout live in action.
- Actuate/OpenText is using abego TreeLayout in some of their products to help provide personalized analytics and insights.
- Terence Parr uses abego TreeLayout in ANTLR 4 to visualize parse trees.
- The Attack-Defense Tree Tool (ADTool) displays attack-defense trees using abego TreeLayout. ADTool allows users to model and analyze attack-defense scenarios represented with attack-defense trees and attack-defense terms.
- In his article “Zeichnen von Bäumen beliebigen Grades mithilfe der abego TreeLayout-Bibliothek und dem MVC-Design Pattern.” Thomas Kramer describes how he uses abego TreeLayout together with the Model-View-Controller pattern to create his application (sources included).
- Martin Skurla integrated abego TreeLayout in his AST visualizer and wrote a nice article about it (The story of javac AST Visualization on NetBeans Platform).
- The Logic-Learning Assistance Tool (LLAT), a "Visual Improvement to the Pedagogy of Introductory Logic", by Joshua Crotts et. al., uses abego TreeLayout to display Truth Trees.
- Zhang Yin and zhusichuang ported abego TreeLayout to .Net/C# (citexplore-code-treelayout).
(If you are using abego TreeLayout in your application please let me know. If you like I will also add you to this list.)
History
For a history see the Changes file.
New release of TreeLayout will be announced on Twitter @abego.
License
abego TreeLayout is distributed under a BSD license of abego Software. (License text)
Sponsors
The development of TreeLayout was generously sponsored by Terence Parr "The ANTLR Guy".
ej-technologies supports open source projects with its full-featured Java profiler JProfiler.
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.