Layout Stages

The task of a layout algorithm is a major undertaking that involves arbitrarily complex logic. However, a number of well-defined (sub-)tasks can be identified that even completely different algorithms do in a similar manner. yFiles factors out such tasks into layout stages and re-uses them in various contexts.

In addition to these distinct tasks, more complex layout algorithms and even the full-fledged layout styles and edge routers are implemented as layout stages, too. These layout stages can be plugged together to realize complex layout processes tailored to your requirements.

The Layout Stage Concept

A layout stage serves as a kind of container that encapsulates arbitrary layout functionality, and provides a general means to string together multiple stages into a compound layout process. Interface ILayoutStage defines the basis for a layout stage.

ILayoutStage is a specialization of the ILayoutAlgorithm interface, and thus can be used as a stand-alone layout provider as well as a part of a larger layout process.

When used in the context of a larger layout process, a layout stage can easily be used to simplify the core layout algorithm’s task. It can perform preprocessing steps on the input graph before the core algorithm’s invocation, and/or post-processing steps thereafter.

The following layout stages are part of each major layout algorithm since they are part of the default multi-stage layout pipeline:

The following layout stages are not part of the default pipeline but can be used to enhance the layout process nevertheless:

RecursiveGroupLayout

Applies a specified layout algorithm to the direct children of each group node (recursively).

GraphLayoutLineWrapper

Line-wraps or column-wraps a graph layout to accomplish a desired aspect ratio or fixed width or height.

LayoutMultiplexer

Applies different layout algorithms which are dynamically chosen at runtime by inspecting the nodes of the input graph.

FixGroupLayoutStage

Guarantees that a core layout algorithm will maintain the relative positions of nodes within the same group.

CompositeLayoutStage

Combines multiple ILayoutStages organized in a pipeline.

All major layout algorithms are implemented as layout stages and thus can preprocess or postprocess another layout. For example, this can be used to run edge routing or automatic labeling after any major layout.

Default Multi-Stage Layout Pipeline

All major layout algorithms take the concept of layout stages one step further and provide a conveniently configurable layout pipeline for performing preprocessing and postprocessing steps on the input graph.

The pipeline of predefined ILayoutStages of MultiStageLayout (when all are activated) causes the following sequence of steps:

1. Hides the group nodes.
2. Hides all except for the induced subgraph.
3. Decomposes the graph into its connected components. Performs steps 4-12 on each component.
4. Prepares for label placement.
5. Prepares the layout for an orientation change.
6. Hides self-loops.
7. Hides parallel edges.
8. Invokes the layout algorithm on the simplified graph.
9. Un-hides and routes parallel edges.
10. Un-hides and routes self-loops.
11. Completes orientation change of the layout.
12. Assigns label positions.
13. Arranges the connected components of the graph.
14. Un-hides non-induced subgraph.
15. Un-hides the group nodes.

This layout pipeline is defined by the MultiStageLayout class and provides all the layout stages listed in Predefined layout stages. The following properties can be used to configure the pipeline:

disableAllStages

hideGroupsStageEnabled

componentLayoutEnabled

orientationLayoutEnabled

labelingEnabled

selfLoopRouterEnabled

subgraphLayoutEnabled

parallelEdgeRouterEnabled

Methods for enabling and disabling the predefined layout stages, and also for controlling their enabled state.

appendStage(stage: ILayoutStage): void

prependStage(stage: ILayoutStage): void

removeStage(stage: ILayoutStage): void

Methods to add and remove individual layout stages.

In MultiStageLayout, all stages except generic labeling and subgraph layout are enabled by default. However, layout styles that extend this class might disable more stages. Most notably, the hierarchical style disables all stages except orientation layout.

The layout stages themselves can be accessed using the following properties:

hideGroupsStage

componentLayout

orientationLayout

labeling

selfLoopRouter

subgraphLayout

parallelEdgeRouter

Properties for predefined layout stages.

Layout of Unconnected Components

The ComponentLayout class arranges the connected components of a graph. It invokes its core layout algorithm on each of the input graph’s components and afterwards arranges the separate components while keeping the relative layout within each component fixed.

ComponentLayout is already part of the default multi-stage layout pipeline.

Using ComponentLayout’s services with a given ILayoutAlgorithm implementation as its core layout algorithm has several benefits:

• The core layout algorithm needs not be able to handle non-connected graphs itself. It can safely assume that its input graph is connected. This often simplifies the formulation of a core algorithm substantially.
• The core layout algorithm needs not be able to arrange the separate components of an input graph. This is done by ComponentLayout.
• Customization of the layout strategy used for arranging separate components can conveniently be done by tailoring, or even exchanging, the ComponentLayout. All core algorithms can take advantage of this customization immediately.
• ComponentLayout objects can be used in conjunction with arbitrary core layout algorithms, since the services provided by ComponentLayout are highly reusable.

Class ComponentLayout provides a number of data provider keys to specify supplemental layout data for the graph elements:

The ComponentLayout class provides a set of options that affect its behavior.

Component Arrangement Style

style

Specifies the style for arranging the components of a graph.

Arranging Components

componentArrangement

Determines whether the separate components should be arranged or not. By default, component arrangement is enabled.

Component Spacing

componentSpacing

Defines the minimum distance between the bounding boxes of adjacent components.

Grid Spacing

gridSpacing

Defines the spacing of the grid on which the separate components are placed.

Label Awareness

considerLabels

Determines whether labels are taken into account when computing the bounding boxes of components.

Support for Grouped Graphs

considerGrouping

Specifies whether the grouped graph’s hierarchy of nodes is taken into account when determining its components.

Wrapping Wide or High Layouts

The GraphLayoutLineWrapper class is a layout stage that can be used to line-wrap or column-wrap a graph layout, respectively. It allows, for example, to specify a desired aspect ratio for a wrapped layout, or a fixed width (height) for the lines (columns) of a wrapped layout.

Most commonly, the GraphLayoutLineWrapper class is used in conjunction with hierarchical layouts. Hierarchical layout before and after line-wrapping presents a hierarchical layout that has been line-wrapped to achieve a desired aspect ratio.

Using GraphLayoutLineWrapper in conjunction with hierarchical layout shows how the GraphLayoutLineWrapper class can be used to wrap hierarchical top-to-bottom layouts.

const layoutLineWrapper = new GraphLayoutLineWrapper()
layoutLineWrapper.columnMode = true
layoutLineWrapper.mirror = false
// Use grouping-aware hierarchical layout as the core layout.
layoutLineWrapper.coreLayout = new HierarchicLayout()

// Invoke the layout.
graph.applyLayout(layoutLineWrapper)

GraphLayoutLineWrapper provides a set of options that influence its behavior.

Column Mode

columnMode

Determines whether the graph layout should be column-wrapped instead of line-wrapped.

Spacing

spacing

Defines the spacing between adjacent lines (columns) of the line-wrapped (column-wrapped) graph layout.

Edge Spacing

edgeSpacing

Defines the spacing between adjacent edge paths that connect consecutive lines (columns) of the line-wrapped (column-wrapped) graph layout.

Mirroring

mirror

Determines whether the lines (columns) of the line-wrapped (column-wrapped) graph layout should be arranged in an alternating manner so that every second line (column) goes from right to left (bottom to top) instead of left to right (top to bottom).

Pre-set vs. Automatic Line Width (Column Height)

fixedWidthLineBreaks

Determines whether the lines (columns) of the line-wrapped (column-wrapped) graph layout should use the width (height) as set using fixedWidth.

Fixed Line Width (Column Height)

fixedWidth

Defines the width (height) that should be used for the lines (columns) of the line-wrapped (column-wrapped) graph layout. This setting only has an effect if pre-set line width (column height) is enabled.

Aspect Ratio

targetRatio

Defines the desired aspect ratio that should be achieved for the line-wrapped (column-wrapped) graph layout. This setting only has an effect if automatic line width (column height) is enabled.

Alignment Stage

Class AlignmentStage is a layout stage that can be used to automatically align nodes on vertical and horizontal lines. The stage minimizes the number of used lines subject to the constraint that the position changes of the nodes are restricted.

The algorithm runs in two phases. In the first phase, the nodes are partitioned into disjoint sets for both the x-dimension and the y-dimension. Hence, in this phase the nodes are snapped to lines, whose positions are not defined yet. In the second phase, the positions of these lines and consequently their assigned nodes are determined. The positions are chosen such that the overall movement of the nodes is minimized.

The stage is intended to be used as a post-processing step on already properly arranged graphs. Although the stage resolves node overlaps, it is recommended to use it on graph layouts without node overlaps. If necessary, another stage that resolves node overlaps can be prepended (e.g. RemoveOverlapsStage)

Example of the node alignment stage. Left: input layout produced by OrganicLayout. Right: layout after applying the alignment stage.

Basic Properties

Alignment Policy

alignmentPolicy

The AlignmentStage allows to specify the direction for which the nodes are snapped. Choosing the x-direction means that the nodes are snapped on vertical grid lines, while choosing the y-direction means that the nodes are snapped to horizontal grid lines. In case that both axes are chosen, the snapping is done sequentially for the two orientations. See Table Example for the choice of the alignment policy. for an example.

Example for the choice of the alignment policy.

no node alignment	y-coordinates are snapped
x-coordinates are snapped	both x- and y-coordinates are snapped

Snap Distance

snapDistance

The snap distance describes the maximum distance between two nodes that can be snapped to the same line, i.e., two nodes are only aligned on the same line if their center-to-center distance does not exceed the given snap distance in the respective dimension. Therefore, large snap distances produce a more emphasized grid structure, while giving up more of the initial layout than small snap distances.

Separate Alignments

separateStripes

If this property is enabled, the nodes are placed in strictly separated rows and columns, i.e., the nodes that are aligned on consecutive lines are geometrically separated by lines. Table Example for separated alignments. (right column) shows an example with separated stripes. The nodes assigned to consecutive horizontal lines can be separated by a horizontal line, i.e., the nodes of one grid line are above that horizontal line, and nodes of the other are below. Similarly, the nodes assigned to consecutive vertical grid lines can be separated by a vertical line. Altogether, this leads to the visual impression that the nodes are placed in disjoint rows and columns. While enabling this property visually separates nodes, it may on the other hand reduce the compactness of the layout substantially.

Example for separated alignments.

not separated	separated

Grid Spacing

gridSpacing

It is possible to place the generated alignments in regular intervals to produce a grid-like appearance. If this property is set to a value greater than zero, the distance between any two parallel alignment axes will be set to some multiple of that value.

Example for regular alignments.

not regular	regular

Snap Offset

snapOffsets

By default the nodes are aligned with their centers on common lines. However, depending on the use case, it can be necessary to align other points of the nodes, e.g., their top-left corners. To that end, the snap point of a node can be customized through a snap offset. The snap offset is relative to the node’s center and defines a snap point in the interior or on the boundary of a node. If the snap point lies outside of the node, the point is mapped onto the boundary of the node. The snap offset for each node may be specified using the supplemental data that can be conveniently defined via class AlignmentStageData.

Grouped Graphs

The alignment stage can be applied on grouped inputs as well. In this case, the alignment stage will be performed on all nodes that are not group nodes or that do not have any children. The alignment of these nodes will conform to the Basic Properties. Group nodes with children themselves are not aligned, but it is ensured that they can be drawn without overlaps.

Example of alignments on grouped graphs.

not aligned	aligned

Layout Data

Supplemental layout data for a graph’s items can be specified by registering data providers with the graph using given look-up keys. The supplemental data can conveniently be defined via class AlignmentStageData. Table Supplemental layout data lists the properties of AlignmentStageData and the corresponding look-up keys that are used by AlignmentStage during the layout process.

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

Supplemental layout data

snapOffsets

A YPoint point that specifies the snap point of the node.

Data Provider Key: SNAP_OFFSET_DP_KEY

Maps from node to YPoint

nodeHalos

A NodeHalo object that specifies the halo sizes at each side of a node.

Data Provider Key: NODE_HALO_DP_KEY

Maps from node to NodeHalo

abortHandler

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

Data Provider Key: ABORT_HANDLER_DP_KEY

Maps from graph to AbortHandler

partitionGridData

Specifies a PartitionGrid for the alignment stage to consider.

PartitionGridData.grid

Specifies the partition grid structure for the graph. Can also be defined using the rowIndices and columnIndices properties.

Data Provider Key: PARTITION_GRID_DP_KEY

Maps from graph to PartitionGrid

PartitionGridData.cellIds

Specifies the partition cell id for a node. Alternatively, cell indices for a node can be specified using the rowIndices and columnIndices properties.

Data Provider Key: PARTITION_CELL_ID_DP_KEY

Maps from node to PartitionCellId