Graph Layout > Layout Algorithms > Tree Layout > Brief Description of the Algorithm
 
Brief Description of the Algorithm
For the Tree Layout, the core algorithm for the layout modes free, level, and radial works in just two steps and is very fast.
*Step 1: Calculation of the spanning tree
*Step 2: Calculation of node positions and link shapes
The variations for the layout mode tip-over perform the second step several times and pick the result that best fits the given aspect ratio (the ratio between width and height of the drawing area). Therefore, the tip-over layout modes are slower.
Step 1: Calculation of 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 will be chosen. If the graph has cycles, some links will not become part of the spanning tree. These links are called non-tree links, while the links of the spanning tree are called tree links. The non-tree links are ignored in step 2 of the algorithm.
The root is the black node in Figure 4.1, Figure 4.2 and Figure 4.3. In the spanning tree, each node except the root has a parent node. All nodes that have the same parent are called children with respect to the parent and siblings among themselves. Nodes without children are called leaves. Each child at a node starts a subtree (also called a branch of the tree). Sketch of Spanning Tree illustrates a spanning tree.
Sketch of Spanning Tree
Step 2: Calculation of node positions and link shapes
The layout algorithm arranges the nodes according to the layout mode and the offset and alignment options. In free and level modes, the nodes are arranged horizontally or vertically so that all tree links flow roughly in the same direction. In the radial 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.
Code Sample
Below is a code sample using the IlvTreeLayout class:
// ...
 
IlvGrapher* grapher = new IlvGrapher(display);
IlvView* view = new IlvView(display, "", "", IlvRect(0, 0, 100, 100));
grapher->addView(view);
view->show();
// ... Fill in the grapher with nodes and links here
// ... Suppose we have added rootNode as a node in the grapher
IlvGraphic* rootNode = 0;
IlvTreeLayout* layout = new IlvTreeLayout();
layout->attach(grapher);
// Specify the root node, orientation and alignment
layout->setRoot(rootNode);
layout->setFlowDirection(IlvRight);
layout->setGlobalAlignment(IlvLayoutCenterAlignment);
// Perform the layout
IlvGraphLayoutReport* layoutReport = layout->performLayout();
if (layoutReport->getCode() != IlvLayoutReportLayoutDone)
IlvWarning("Layout not done. Error code = %d\n", layoutReport->getCode());
 
// If this grapher is not anymore subject of layout:
layout->detach();
 
// Once the layout algorithm is not anymore needed:
delete layout;
 

Version 6.2.1
Copyright © 2018, Rogue Wave Software, Inc. All Rights Reserved.