TreeLayout

Layout Style

TreeLayout provides multiple different arrangements of trees and subtrees. It is easy to customize the order of edges, the port assigner and the arrangement of the nodes for each subtree.

Tree layout algorithms are commonly applied to visualize relational data and produce diagrams of high quality that are able to reveal possible hierarchical properties of the graph. More precisely, they find applications in dataflow analysis, software engineering, bioinformatics and business administration.

Example graph with a layout calculated by TreeLayout using default settings

Tree layout using different ISubtreePlacers and rotations

Concept

The layout algorithm starts from the leaves and continues with their parents, then with the parents of the parents and so on. When a node is processed, the algorithm will use the corresponding ISubtreePlacer instance to move its children (along with their subtrees) to a suitable position and to route the outgoing edges of this node. Then, the next local root node will be processed.

To avoid moving all nodes several times and to know the area that the subtrees occupy, the layout algorithm uses SubtreeShapes. These SubtreeShapes are moved and merged during layout calculation.

Features

Each subtree can have a different style of node placement. ISubtreePlacers are responsible for arranging subtrees and their common root node. They can be specified separately for each local root via layout data property subtreePlacers.

A custom node can be defined as root of the tree using layout data property treeRoot.

The layout algorithm can be configured to reserve space for node labels and place the edge labels along edges such that the labels won't overlap with other graph elements. Edge labels are placed according to the information stored in an EdgeLabelPreferredPlacement instance. However, the placement along the edge will only affect the order of multiple labels at the same edge. The algorithm will always place the labels close to the target node.

Grouping of nodes can also be handled by this layout algorithm. It is important that a group node contains a whole subtree. Otherwise, the group nodes may overlap with each other or with other nodes. Furthermore, the user may specify minimum size constraints for each group node using IMapper<K,V> key MINIMUM_GROUP_NODE_SIZE_DATA_KEY.

TreeLayout supports custom sorting of the outgoing edges of a node. For example, a ISubtreePlacer instance that implements IFromSketchSubtreePlacer provides a comparator that keeps the current order of siblings, allowing to extend the graph incrementally.

nodeTypes are considered such that the type of the nodes is used as a criterion for sorting the child nodes of a local root node, with the effect that nodes of the same type are placed consecutively, if possible. The primary ordering criterion is still specified by the childOrder.

How port placement constraints are handled depends on the selected portAssigners. In addition, the PortPlacementStage is applied as a postprocessing step.

This layout algorithm can only handle graphs with a tree structure. To make it applicable to general graphs, the treeReductionStage is used by default. This stage will temporarily remove some edges of the input graph until a tree is obtained. After the layout calculation, the stage will reinsert the edges that were removed and route them separately.

For particularly fast layout computations you may use the following configuration. Note that this limits the layout to specific styles. All settings not shown in the snippet must be set to their default values.

const subtreePlacer = new LevelAlignedSubtreePlacer()
subtreePlacer.busAlignment = busAlignment
subtreePlacer.layerSpacing = layerSpacing
subtreePlacer.rootAlignment = SubtreeRootAlignment.CENTER_OF_PORTS
subtreePlacer.edgeRoutingStyle = routingStyle
subtreePlacer.spacing = spacing // must be at most busAlignment * layerSpacing

const treeLayout = new TreeLayout({
  defaultSubtreePlacer: subtreePlacer,
})

Layout Stages

This class provides a configurable pipeline that contains various ILayoutStages. Each ILayoutStage can incorporate preprocessing or postprocessing steps into the layout calculation to streamline the input graph and enhance the resulting layout. Additionally, custom ILayoutStages can be added and executed either before or after the predefined ones.

The following default ILayoutStages are included:

• PortPlacementStage: Assigns edges to ports. The property routeCorrectionPolicy is set to MOVE_PORTS.
• GroupHidingStage: Removes group nodes and their adjacent edges before layout processing, and reinserts them afterward. Note: This stage is disabled by default.
• SubgraphLayoutStage: Filters a graph to include only specific nodes and edges from a subgraph while maintaining the positions of excluded elements. Note: This stage is disabled by default.
• ComponentLayout: Arranges graph components with customizable styles.
• GenericLabeling: Efficiently places node and edge labels. The property fillEmptyScope is set to false and stopDuration is set to ZERO.
• OrientationStage: Changes the layout orientation in four possible directions, with or without mirroring on the x or y-axis. The property edgeLabelPlacement is set to IGNORE.
• SelfLoopRouter: Routes self-loops in a graph, allowing for either orthogonal or rounded routing styles.
• ParallelEdgeRouter: Routes multiple edges between the same nodes in parallel.
• TreeReductionStage: Temporarily reduces general graphs to tree structures, allowing them to be processed by a tree layout algorithm. The property nonTreeEdgeRouter is set to a StraightLineEdgeRouter instance.

With these layoutStages the layout algorithm is configured well, so they usually don't need to be changed.