The TL algorithm

> > > > >

This section shows the use of the tree layout (class IlvTreeLayout from the package ilog.views.graphlayout.tree).

The core algorithm for free, level, and radial layout modes has just two steps and is fast. The variations of tip-over layout mode perform the second step several times and pick the layout result that best fits the aspect ratio (the ratio between the width and height of the drawing area). For this reason, tip-over layout modes are slower.

Step 1: Calculating the spanning tree: If the graph is disconnected, the layout algorithm chooses a root node for each connected component. Starting from the root node, it traverses the graph to choose the links of the spanning tree. If the graph is a pure tree, all links are chosen. If the graph has cycles, some links are not included as part of the spanning tree. These links are called nontree links, while the links of the spanning tree are called tree links. The nontree links are ignored in step 2 of the algorithm.

In figures Tree layout in free layout mode with center alignment and flow direction to the right, Tree layout with flow direction to the bottom, orthogonal link style, and tip-over alignment at some leaf nodes, and Tree layout in radial layout mode with aspect ratio 1.5, the root is the node that has no parent node. In the spanning tree, each node except the root has a parent node. All nodes that have the same parent are called child nodes with respect to the parent and siblings with respect to one another. Nodes without child nodes are called leaves. Each child node at a node starts a subtree (also called a branch of the tree). A spanning tree shows an example of a spanning tree.

A spanning tree

Step 2: Calculating node positions and link shapes: The layout algorithm arranges the nodes according to the layout mode and the offset and alignment options. In free mode and level mode, the nodes are arranged horizontally or vertically so that all tree links flow roughly in the same direction. In radial layout modes, the nodes are arranged in circles or ellipses around the root so that all tree links flow radially away from the root. Finally, the link shapes are calculated according to the link style and alignment options.

Example of TL

In CSS

The following example is a specification in CSS using the Tree Layout algorithm. Since the Tree Layout places nodes and links, it is usually not necessary to specify an additional link layout in CSS. The specification in CSS can be loaded as a style file into an application that uses the IlvDiagrammer class.

SDM {
    GraphLayout : "true";
    LinkLayout  : "false";
}

GraphLayout {
    graphLayout       : "Tree";
    layoutMode        : "FREE";
    flowDirection     : "Bottom";
    globalLinkStyle   : "ORTHOGONAL_STYLE";
    globalAlignment   : "CENTER";
    connectorStyle    : "EVENLY_SPACED_PINS";
    siblingOffset     : "15";
    branchOffset      : "30";
    parentChildOffset : "20";
    position          : "200,20";
}

However, it is possible to enable the link layout additionally and in this case, the link layout determines the shapes of the links.

In Java

The following code sample uses the IlvTreeLayout class in Java. This code sample shows how to perform a Tree Layout on a grapher directly without using a diagram component or any style sheet:

...
import ilog.views.*;
import ilog.views.graphlayout.*;
import ilog.views.graphlayout.tree.*;
 ...
IlvGrapher grapher = new IlvGrapher();
IlvManagerView view = new IlvManagerView(grapher);

 ... /* Fill in the grapher with nodes and links here */
 ... /* Suppose we have added rootNode as a node in the grapher */

IlvTreeLayout layout = new IlvTreeLayout();
layout.attach(grapher);

/* Specify the root node, orientation and alignment */
layout.setRoot(rootNode);  
layout.setFlowDirection(IlvDirection.Right);
layout.setGlobalAlignment(IlvTreeLayout.CENTER);

try {
        IlvGraphLayoutReport layoutReport = layout.performLayout();

        int code = layoutReport.getCode();

        System.out.println("Layout completed (" +
          layoutReport.codeToString(code) + ")");
}
catch (IlvGraphLayoutException e) {
        System.err.println(e.getMessage());
}

Important

All explanations in the subsequent sections regarding the shape of the links in Tree Layout are valid only if the link layout is disabled.

Current section

Tree Layout (TL)