RadialTreeLayout

Layout Style

RadialTreeLayout is designed to arrange directed and undirected tree graphs. Subtrees rooted at a node are placed in a radial fashion around their root node. All direct children of one node can be placed on a common circle around their parent node (depending on the alignment policy). Therefore, subtrees look like balloons or stars, especially if subtrees have similar sizes. The edges of the tree are drawn as straight lines.

Sample radial tree drawing of a large tree obtained with default settings

Sample radial tree drawing featuring interleaved child placement and ray-like node labels

Concept

The algorithm executes the following steps:

1. Select a root node according to the specified policy.
2. Determine the placement of subtrees around the root using a bottom-up recursive approach (starting with leaf nodes).
   • For a leaf node: calculate the convex hull of the node.
   • For a non-leaf node: arrange the children rooted at the node. Children are sorted according to a specified ordering policy and a distance to their parent is chosen. This distance will be chosen such that subtrees rooted at the current node fit into the preferred sector angle. The sector angle defines how much radial space a subtree occupies around its parent; it is computed using the convex hull of subtrees.

     Finally, the convex hull of the subtree rooted at the current node is updated in order to include all the convex hulls of child nodes. This is possible, because distances and sectors of the child subtrees are now known.

3. Assign the actual coordinates of nodes, again using a recursive approach (starting with the root node).

Features

The algorithm features integrated edge labeling as well as node labeling. Edge labels and node labels are placed automatically without generating overlaps with other labels or graph elements. There are different ways to place node labels. Edge labeling will take the settings of EdgeLabelPreferredPlacement into account.

Defining a preferred sector angle has a great influence on the layout style. Subtrees rooted at a node get a certain amount of radial space to be placed around the parent node, such that a preferred angle close to 360 degrees will generate drawings where subtrees look like balloons, while an angle close to 180 degrees could be chosen to get drawings where subtrees look like semicircles.

Since it is computationally not very complex, RadialTreeLayout is very well suited for large tree graphs. It performs well even for huge graphs.

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. If defined, the childOrder is stronger than the node type criterion. However, the node types are considered more important than the childOrderingPolicy.

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. These edges will later be reinserted and routed separately.

This layout algorithm handles port placement constraints by applying the PortPlacementStage as a postprocessing step.

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.
• GroupHidingStage: Removes group nodes and their adjacent edges before layout processing, and reinserts them afterward. The property hidingEmptyGroupNodes is set to false and resetEdgePaths is set to true.
• 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. The property style is set to circular component arrangement style.
• 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.
• 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.

Performance

The RadialTreeLayout algorithm is a fast algorithm that is generally well-suited to handle even large graphs.

With disconnected graphs that contain large unconnected components, it can be beneficial to change the component arrangement style of the used componentLayout from the default style PACKED_CIRCLE to the faster ROWS style.