Brief Description of the Algorithm
This algorithm works in four steps.
Step 1: Leveling
The nodes are partitioned into groups. Each group of nodes forms a level. The objective is to group the nodes in such a way that the links always point from a level with a smaller index to a level with a larger index.
Step 2: Crossing Reduction
The nodes are sorted within each level. The algorithm tries to keep the number of link crossings small when, for each level, the nodes are placed in this order on a line (see Level and Position Indices). This ordering results in the relative position index of each node within its level.
Step 3: Node Positioning
From the level indices and position indices, balanced coordinates for the nodes are calculated. For instance, for a layout where the link flow is from top to bottom, the nodes are placed along horizontal lines such that all nodes belonging to the same level have (approximately) the same y-coordinate. The nodes of a level with a smaller index have a smaller y-coordinate than the nodes of a level with a higher index. Within a level, the nodes with a smaller position index have a smaller x-coordinate than the nodes with a higher position index.
Step 4: Link Routing
The shapes of the links are calculated such that the links bypass the nodes at the level lines. In many cases, this requires that a bend point be created whenever a link needs to cross a level line. In a top-to-bottom layout, these bend points have the same y-coordinate as the level line they cross. (Note that these bend points also obtain a position index).
Level and Position Indices shows how the Hierarchical Layout algorithm uses the level and position indices to draw the graph.
Level and Position Indices
The steps of the layout algorithm can be affected in several ways. For instance, you can specify the desired level index that the algorithm should choose for a node in Step 1 or the desired relative node position within the level in Step 2. You can also specify the justification of the nodes within a level and the style of the links shapes.
Code Sample
Below is a code sample using the IlvHierarchicalLayout class:
// ... IlvGrapher* grapher = new IlvGrapher(display); // ... Fill in the grapher with nodes and links here IlvHierarchicalLayout* layout = new IlvHierarchicalLayout(); layout->attach(grapher); // Set the layout parameters, e.g., flow to bottom: layout->setFlowDirection(IlvBottom); // ... // 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; |
Published date: 05/24/2022
Last modified date: 02/24/2022
