Series-parallel Layout
The series-parallel layout style is specifically designed for series-parallel graphs, a special type of two-terminal graph. These graphs have a structure that can be built recursively using two distinct composition operations, as described in Terminology.
For general graphs, the algorithm temporarily transforms them into a series-parallel structure to calculate the layout.
Similar to the hierarchical layout style, this style can emphasize the main direction, or flow, within a directed graph. The nodes are positioned so that most edges have the same overall orientation, such as top-to-bottom.
The layout algorithm arranges series structures of the graph vertically, one below the other, and parallel structures horizontally, side by side.
For true series-parallel graphs, the algorithm can always place the nodes to avoid edge crossings.
Sample layout by class SeriesParallelLayout shows a series-parallel layout with a top-to-bottom orientation of a series-parallel graph. This layout style can be used with polyline, orthogonal, and octilinear edge routing. It also supports grouped graphs.
Terminology
In a series-parallel graph, there are two distinct terminal nodes: a source node with only outgoing edges and a sink node with only incoming edges. Between these terminal nodes, there can be any combination of series and parallel structures. These structures are composed recursively using two distinct composition operations:
- series composition operation: Two series-parallel graphs are joined by merging the source node of one graph with the sink node of the other. The resulting graph is a series of the two previous graphs; see figure Series-parallel composition operationsA and B for the before and after states of this composition operation.
- parallel composition operation: Two series-parallel graphs are joined by merging their source nodes and merging their sink nodes. In the resulting graph, the non-terminal nodes of the two previous graphs are in parallel. See Series-parallel composition operationsC and D for the before and after states of this composition operation.
Note that terminal nodes can also be identified in each parallel (sub)structure of a series-parallel graph. The beginning of the parallel (sub)structure is defined by a source node from which multiple edges leave, and the end is defined by a sink node into which multiple edges enter.
Relevant Classes
Relevant classes for this style lists the relevant classes for the series-parallel layout style.
Layout Orientation
- layoutOrientation
- Determines the main layout direction, which is the overall orientation for the edges in a layout. The layout algorithm arranges nodes so that edges generally point in this main layout direction. By default, edges are oriented from top to bottom. You can change this using the constants from the LayoutOrientation enumeration to set other layout directions.
The documentation for the other layout options assumes that this default orientation is being used.
Child Order
The order of parallel subgraphs can be controlled by specifying a custom child order using the SeriesParallelLayoutData.
- childOrder
- Used to configure the order of parallel subgraphs.
If a terminal node has several child nodes, the child order is used to sort them. Ordering parallel subgraphsA shows a graph where children are sorted from left to right by their height.
It is important to note that children may not be completely independent. To avoid edge crossings, only children of the same parallel subgraph are compared. Ordering parallel subgraphsB shows an example of this when the children are sorted using the same criterion. Although the middle child has a smaller height than the right child, it is placed before the right child because it is part of the left-most child’s subgraph.
Edge Routing
- Routing Style
- edgeRoutingStyle
- Configures the routing style for the edges in the graph.
The routing style can be further refined using the following properties:
- Preferred Octilinear Segment Length
- preferredOctilinearSegmentLength
- Specifies the preferred length of the octilinear edge segment (the segment with a 45-degree slope).
- Minimum Polyline Segment Length
- minimumPolylineSegmentLength
- Determines the minimum length of the sloped edge segment of polyline edges.
- Minimum Slope
- minimumSlope
- Determines the minimum slope of the sloped edge segment of polyline edges.
Additional drawing style options for edges can be specified using the SeriesParallelLayoutEdgeDescriptor class. An instance of this class is held by SeriesParallelLayout to store and retrieve default values for drawing style options, such as minimum lengths.
SeriesParallelLayout provides access to the default EdgeLayoutDescriptor instance through:
- Default Edge Descriptor
- defaultEdgeDescriptor
- Edge-related layout options.
In addition, it is possible to specify individual edge descriptors for each edge using the layout data’s edgeDescriptors property. In the absence of an individual descriptor for an edge, the default defaultEdgeDescriptor instance will be used.
Node placement
- Minimum Distances
- minimumNodeDistance
- Specifies the minimum distance between two nodes.
- minimumNodeToEdgeDistance
- Specifies the minimum distance between a node and a segment of an edge. If the facing sides of two parallel subgraphs both show nodes and edges, the maximum of this value and the minimumNodeDistance is used.
- minimumEdgeDistance
- Specifies the minimum distance between the segments of two edges. This only applies to edge segments that are not bundled in a bus or restricted through a common port.
- Parallel Subgraph Alignment
- parallelSubgraphAlignment
- Determines the vertical alignment of parallel subgraphs. Values can be set from 0.0 (top) to 1.0 (bottom). See also Vertical alignment of parallel subgraphs.
Port Assignment
To distribute the outgoing and incoming edges at the terminal nodes before and after parallel subgraphs, SeriesParallelLayout uses an instance of the SeriesParallelLayoutPortAssigner by default. It provides two port assignment modes that handle the port distribution across the sides of the terminal nodes, as shown in the following figure:
Note that in both modes, certain aspects of the outgoing or incoming edges' port candidate configuration are ignored to prevent confusing or conflicting edge routes in the resulting layout. In particular, this applies to the direction specified by a port candidate of an outgoing or incoming edge. However, the ports of edges with a fixed port candidate will get:
- the original location relative to the terminal node’s center, as specified by their fixed port candidate.
- the original location relative to the terminal node’s center, as specified by the first fixed port candidate encountered among all edges that belong to the same edge group. Note that all edges that belong to the same edge group should yield the same fixed port candidate.
Additionally, the distribution of ports can either be restricted to the two node sides oriented in the main layout direction, or allowed to use all four sides of the terminal nodes:
SeriesParallelLayout provides access to the default ISeriesParallelLayoutPortAssigner implementation through:
- defaultPortAssigner
- Configures the default ISeriesParallelLayoutPortAssigner implementation that is used by SeriesParallelLayout. The factory default for this is an instance of class SeriesParallelLayoutPortAssigner.
An ISeriesParallelLayoutPortAssigner implementation can be specified individually for single nodes using the portAssigners property. If an individual implementation for a node is not specified, the default implementation that is registered with SeriesParallelLayout will be used.
Labeling
Besides the generic labeling support described in Generic Labeling, which is available with all yFiles layout algorithms, the series-parallel layout algorithm also supports integrated labeling.
The labels are considered when determining both node placement and edge path generation and are placed according to their EdgeLabelPreferredPlacement. This strategy ensures that no edge label overlaps other objects in the diagram.
Integrated labeling can be enabled or disabled using the following property:
- edgeLabelPlacement
- Determines the labeling strategy for edge labels.
See also Integrated Labeling.
Optimal label placement with integrated labeling can be achieved using FreeEdgeLabelModel as the label model for the edges. As explained in Label Models, this edge label model is ideally suited in combination with integrated labeling and yields the best match for a label location that is computed by SeriesParallelLayout.
SeriesParallelLayout provides support for node label-aware layout. Node labels do not need to be placed explicitly. Instead, their size is considered for the placement of adjacent graph elements. Taking node labels into consideration during layout calculation ensures that they do not overlap nodes in the diagram.
Node label awareness is enabled using:
- nodeLabelPlacement
- Determines the strategy for handling node labels.
Grouped Graphs
SeriesParallelLayout supports grouped graphs. However, there are some restrictions with respect to the actual grouping structure of a grouped graph both inside and outside of groups:
- The inner graph of a group needs to be series-parallel.
- The part of the graph outside of a group needs to stay series-parallel when the group is closed.
In the special case that the inner graph of a group would be series-parallel when adding a source node and/or a sink node to it, then the inner graph is also considered series-parallel.
Incremental Layout
While SeriesParallelLayout is non-incremental by default (that is, it re-computes the entire layout of a given graph), it offers a From Sketch mode to incrementally improve existing series-parallel layouts.
If From Sketch mode is enabled, the initial locations of the nodes are taken into consideration when arranging the subgraphs. The graph remains planar because the initial node locations are only considered for the subgraphs (see Child Order).
- fromSketchMode
- Enables From Sketch mode.
Handling Non-Series-parallel Graphs
To determine whether a graph is series-parallel, SeriesParallelLayout offers the following static method:
It is possible to apply a SeriesParallelLayout to general graphs. If a graph is not series-parallel, the layout algorithm transforms the graph into a series-parallel structure by temporarily adding or removing edges from the graph. After a layout for the modified graph has been calculated, all modifications to the graph structure are reverted.
Any previously removed edges are reinserted and routed using the edge routing algorithm specified by the following property. By default, EdgeRouter is used.
- nonSeriesParallelEdgeRouter
- Configures the edge routing algorithm that is used to route graph edges that contradict the series-parallel structure.