SeriesParallelLayout

Layout Style

Series-parallel graphs are directed graphs with a single source (node without incoming edges) and a single sink (node without outgoing edges). The layout algorithm highlights the main layout direction (from source to sink). It also emphasizes the paths through the graph because edges are routed with few bends.

SeriesParallelLayout is suitable for the visualization of circuits, call trees or flowcharts.

Concept

Series-parallel graphs are directed graphs with a single source (node without incoming edges) and a single sink (node without outgoing edges) that are built using only the following two rules:

1. Series composition: The source of a subgraph is merged with the sink of a second subgraph.
2. Parallel composition: The sources and sinks of two subgraphs are merged.

From the recursive structure of series-parallel graphs, the layout algorithm retrieves a decomposition tree where each node represents one of the decomposition types. Then, this tree is traversed recursively from bottom to top, aligning subgraphs above (series) or next to (parallel) each other until the whole graph is arranged. The edges are routed when both end nodes are placed. Different routing styles can be used.

To avoid moving all nodes several times and to be aware of the area that the subtrees occupy, the layout algorithm keeps track of the shape of the subtrees. These shapes are moved and merged during the layout calculation. The layout algorithm also stores the connections between nodes and nodes that haven't already been placed in these shapes.

Features

SeriesParallelLayout can take fixed LayoutPortCandidates into account. It will connect the edges to the specified locations. However, the directions will be ignored.

Grouping of nodes can also be handled by this layout algorithm. It is important that a group node contains a whole series-parallel subgraph. Otherwise, the group nodes may overlap with each other or with other nodes. Edges which are connected to non-empty group nodes are not allowed. Furthermore, the user may specify minimum size constraints for each group node using IMapper<K, V> key MINIMUM_GROUP_NODE_SIZE_DATA_KEY.

The layout algorithm can be configured to reserve space for node labels and to place the edge labels along the edge 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, labels that should be centered between source and target are placed close to the target node, unless this edge connects to the local source and sink of a subgraph.

Parallel subgraphs can be aligned in different ways. Depending on the node sizes, a different alignment can increase the compactness of the layout.

The way in which edges are distributed around their incident nodes is computed by an instance of ISeriesParallelLayoutPortAssigner. The default port assigner is able to consider LayoutPortCandidates and edge groups.

The fromSketchMode allows to take the initial locations of the nodes into account. However, the layout algorithm won't insert crossings because it maintains the order of children of each node.

SeriesParallelLayout supports custom sorting of the successors of a node, see childOrder.

This layout algorithm is designed to handle graphs with a series-parallel structure. When it is applied to a general graph, the layout algorithm will temporarily add and/or remove some edges from the input graph until a series-parallel graph is obtained. The edges that were removed will be routed afterward by the nonSeriesParallelEdgeRouter and their labels will be placed by nonSeriesParallelEdgeLabeling.

How port placement constraints are handled depends on the selected portAssigners. In addition, the PortPlacementStage is applied 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. The property routeCorrectionPolicy is set to LOCAL_ORTHOGONAL.
• 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.

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