Series-parallel Layout

The series-parallel layout style specializes in the layout of series-parallel graphs, a special subset of so-called two-terminal graphs whose structure can be built recursively using two distinct composition operations as outlined in Terminology.

General graphs are processed by temporarily transforming them into a series-parallel structure for the layout calculation.

Similar to the hierarchical layout style, this style can highlight the main direction or flow within a directed graph. The nodes of a graph are placed such that the (majority of) edges of the graph show the same overall orientation, for example, top-to-bottom.

The layout algorithm places series structures of the given graph below each other and parallel structures side by side.

Note that for true series-parallel graphs, it is always possible to place the nodes such that there are no edge crossings.

Sample layout by class SeriesParallelLayout shows a series-parallel layout with top-to-bottom orientation of a series-parallel graph. Note that the series-parallel layout style can be combined with polyline, orthogonal, and octilinear edge routing. Also, layout of grouped graphs is supported by this layout style, too.

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. In between these terminal nodes, there can be any combination of series and parallel structures that are composed recursively using two distinct composition operations:

• series composition operation: two series-parallel graphs are joined by merging the source node of one with the sink node of the other; the resulting graph is a series of the two previous graphs; see the two left figures for the before and after 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 the two right figures for the before and after 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.

Class SeriesParallelLayout is a layout provider for series-parallel graphs.

It provides a set of options that affect its layout behavior. These options can be set using the properties of class SeriesParallelLayout. The options are documented within the API documentation of class SeriesParallelLayout.

Basic Options

These options configure class SeriesParallelLayout in detail.

Layout Orientation

layoutOrientation

Determines the main layout orientation, i.e., the overall orientation for the edges in a layout. This property is inherited from MultiStageLayout, the direct superclass of SeriesParallelLayout. The layout algorithm tries to arrange nodes in such a way that all edges point in the main layout direction. By default, the overall orientation for the edges will be from top to bottom. The other three layout directions can be set using the constants from the LayoutOrientation enumeration. Setting the layout orientation shows how to set the layout direction.

The documentation for the other layout options assumes that this default orientation is being used.

const spl = new SeriesParallelLayout()
// Use left-to-right main layout direction.
spl.layoutOrientation = LayoutOrientation.LEFT_TO_RIGHT

The order of parallel subgraphs can be controlled by a custom IComparer<T> implementation.

Out Edge Comparer

defaultOutEdgeComparer

Sets the default IComparer<T> implementation for outgoing edges.

If a terminal node has several outgoing edges, the out edge comparer is used to sort them by a certain criterion. The following left figure shows a graph where edges are sorted from left to right by the height of their target node.

It is important to understand that outgoing edges may not be completely independent, and in order to avoid edge crossings, only edges that connect into the same parallel subgraph are compared. The right figure shows an example of this when the outgoing edges are sorted using the same criterion. Although the middle edge has a smaller target node than the right edge, it is not sorted to the left because it connects to the same subgraph as the left edge.

SeriesParallelLayouter provides configuration for general drawing options like, e.g., edge routing styles, edge segment lengths, or minimum distances between graph elements.

Options which affect edge routing:

routingStyle

Configures the routing style for the edges in the graph.

Options that can be used to refine the edge routing:

Preferred Octilinear Segment Length

preferredOctilinearSegmentLength

Specifies the preferred length of the octilinear edge segment (the one with 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.

Further drawing style options for edges can be specified by means of the EdgeLayoutDescriptor class. An instance of this class is held by SeriesParallelLayout to store and retrieve default values for drawing style options, like, e.g., minimum lengths.

SeriesParallelLayout provides access to the default EdgeLayoutDescriptor instance through:

defaultEdgeLayoutDescriptor

Edge-related layout options.

An EdgeLayoutDescriptor instance can be specified individually for single edges by means of layout data. In the absence of an individual descriptor for an edge, the default EdgeLayoutDescriptor instance that is registered with SeriesParallelLayout will be used.

Options which affect node placement:

Minimum Node to Node Distance

minimumNodeToNodeDistance

Specifies the minimum distance between two nodes.

Minimum Node to Edge Distance

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 Minimum Node to Node Distance is used.

Minimum Edge to Edge Distance

minimumEdgeToEdgeDistance

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.

Vertical Alignment of Parallel Subgraphs

verticalAlignment

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.

To distribute the outgoing, respectively incoming edges at the terminal nodes before and after parallel subgraphs, SeriesParallelLayout by default uses an instance of class DefaultPortAssignment, which provides two port assignment modes as depicted in the following figure:

Note that in both modes certain aspects of port constraint configuration of the outgoing or incoming edges will be ignored in order to prevent situations where this would lead to confusing (or even conflicting) edge routes in the resulting layout. In particular, this applies to the direction specified by a port constraint of an outgoing or incoming edge. However, the ports of edges with a strong port constraint will get

• the original location relative to the terminal node’s center as specified by their strong port constraint.
• the original location relative to the terminal node’s center as specified by the first strong port constraint encountered among all edges that belong to the same edge group (as specified for source or target). Note that all edges that belong to the same edge group should yield the same strong port constraint.

Additionally, class DefaultPortAssignment also makes available two so-called fork styles that also affect the distribution of ports of outgoing, respectively incoming edges, as well as the routing of the edges:

SeriesParallelLayout provides access to the default IPortAssignment implementation through:

defaultPortAssignment

Configures the default IPortAssignment implementation that is used by SeriesParallelLayout. The factory default for this is an instance of class DefaultPortAssignment.

An IPortAssignment implementation can be specified individually for single nodes by means of layout data. In the absence of an individual implementation for a node, the default IPortAssignment implementation that is registered with SeriesParallelLayout will be used.

Labeling

Besides the generic labeling support as described in Generic Labeling, which is available with all yFiles layout algorithms, the series-parallel layout algorithm additionally supports integrated labeling. They are taken into consideration when determining both node placement and edge path generation and are placed according to their PreferredPlacementDescriptor. With this strategy it is guaranteed that no edge label will overlap other objects in the diagram.

Integrated labeling can be enabled or disabled using the following property:

integratedEdgeLabeling

Determines whether integrated labeling is enabled.

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, but instead their size needs to be considered for the placement of adjacent graph elements. Taking node labels into consideration during layout calculation guarantees that they will not overlap nodes in the diagram.

Node label awareness is enabled using:

considerNodeLabels

Takes into account the size of 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

Upon creation, SeriesParallelLayout is in non-incremental layout mode by default, i.e., it re-computes the entire layout of a given graph. The other layout mode, namely From Sketch mode, needs to be turned on explicitly using the following property.

If From Sketch mode is enabled, the original locations of the nodes are taken into account when arranging the subgraphs. The graph stays planar, because the original node locations are only considered for the subgraphs (see property Out Edge Comparer in Basic Options).

fromSketchMode

Enables From Sketch mode.

Handling Non-Series-parallel Graphs

To determine whether or not a graph is series-parallel, SeriesParallelLayout offers the following static method:

isSeriesParallelGraph

Whether the given graph is series-parallel.

It is possible to use SeriesParallelLayout on general graphs by activating the following property.

On a given general graph, the layout algorithm tries to find series-parallel structure by temporarily adding and/or removing edges to/from the graph structure. After a layout for the modified graph has been calculated, all modifications to the graph structure are then reverted.

Handling General Graphs

generalGraphHandling

Enables support for series-parallel layout calculation of general graphs.

Any previously removed edges are reinserted and routed using the edge routing algorithm that is returned by the following property. By default, class EdgeRouter is used.

nonSeriesParallelEdgeRouter

Configures the edge routing algorithm that is used to route edges of a general graph that do not conform to the series-parallel structure.

Note that if another edge routing algorithm is set, a data provider look-up key needs to be specified in addition. When invoking this edge routing algorithm, the look-up key is used by the series-parallel layout algorithm to communicate the set of non-conforming (i.e., non-series-parallel) edges that it should process.

nonSeriesParallelEdgesDpKey

Specifies the data provider look-up key used to communicate the set of non-conforming (i.e., non-series-parallel) edges that a custom edge routing algorithm should process.

Layout Data

When using class SeriesParallelLayout, supplemental layout data for a graph’s elements can be specified either by using class SeriesParallelLayoutData or by registering data providers with the graph using given look-up keys. Supplemental layout data lists all properties of SeriesParallelLayoutData and the corresponding look-up keys that SeriesParallelLayout tests during the layout process in order to query supplemental data.

Providing supplemental layout data is described in detail in Layout Data.

Supplemental layout data

edgeLayoutDescriptors

For each edge an EdgeLayoutDescriptor object that configures a number of edge-related options.

Data Provider Key: EDGE_LAYOUT_DESCRIPTOR_DP_KEY

Maps from edge to EdgeLayoutDescriptor

outEdgeComparers

For each (terminal) node an IComparer object that is used to sort the outgoing edges.

Data Provider Key: OUT_EDGE_COMPARER_DP_KEY

Maps from node to IComparer

portAssignments

For each (terminal) node an IPortAssignment implementation that assigns ports to the edges.

Data Provider Key: PORT_ASSIGNMENT_DP_KEY

Maps from node to IPortAssignment

-

For each edge an array of LabelLayoutData objects that encode size and preferred placement for all labels of the edge.

Data Provider Key: EDGE_LABEL_LAYOUT_DP_KEY

Maps from edge to LabelLayoutData[]

-

For each node an array of LabelLayoutData objects that encode size and preferred placement for all labels of the node.

Data Provider Key: NODE_LABEL_LAYOUT_DP_KEY

Maps from node to LabelLayoutData[]

sourceGroupIds

For each edge an arbitrary object indicating the group its source end is affiliated with.

Data Provider Key: SOURCE_GROUP_ID_DP_KEY

Maps from edge to object

targetGroupIds

For each edge an arbitrary object indicating the group its target end is affiliated with.

Data Provider Key: TARGET_GROUP_ID_DP_KEY

Maps from edge to object

abortHandler

An AbortHandler instance that will be queried by the layout algorithm to determine whether layout calculation shall be terminated.

Data Provider Key: ABORT_HANDLER_DP_KEY

Maps from graph to AbortHandler