Layered: Constraining the Model

By Sören Domrös, January 9, 2023

Since it is often desired to constrain the layout in a specific way to achieve a desired layout or to increase layout stability, this post should summarize all current (ELK 0.8.1) and future (planned for 0.9.0) ways to do that. The following will focus primarily on constraining the node order. If you wish to constrain the ports have a look at the portConstraints property and this example.

Layer Constraints

The layerConstraint property allows constraining a node to the first or last layer. This option is quite basic and should be compatible with the Partition and model order cycle breaking. Other approaches might produce unexpected results when used together.

Interactive Constraints

Interactive layout works by having previously defined positions and by using the following layout options for the layered algorithm:

cycleBreaking.strategy: INTERACTIVE
layering.strategy: INTERACTIVE
crossingMinimization.semiInteractive: true
separateConnectedComponents: false

There are two different ways to get positions for your nodes.

Using Pseudo Positions

Add pseudo positions to your nodes as seen here.

layout [position: 100, 0]

Using Constraints

KLighD configures a second layout run with the interactive strategies mentioned above if the interactiveLayout property is set on the root. For the second final run the layerChoiceConstraints and positionsChoiceConstraints are evaluated. In the future relative constraint will also be supported: crossingMinimization.inLayerPredOf, crossingMinimization.inLayerSuccOf.

These constraint are evaluated and translated in pseudo positions.

Examples with constraints and pseudo positions can be found here and in the example in the same category. Note that the constraints are not correctly applied since no second layout run is configured.

This solution requires more than ELK can deliver, ELK only specifies the corresponding constraints. Evaluating and enforcing them is not part of ELK.

Partition

By activating partition cycle breaking as well as layer assignment can be influenced, as seen in this example. partitioning.activate: true is set. By setting the partitioning.partition layers are established.

Also consider to have a look at the following example that showcase interactive constraints by pseudo positions and partition:

Horizontal Order Vertical Order

Model Order

In the following we assume that all states and edges are ordered in their (textual) model as it is indicated by their labels.

Cycle Breaking

ELK 0.8.1 introduced the GREEDY_MODEL_ORDER and the MODEL_ORDER cycleBreaking.strategy. The greedy model order cycle breaker optimizes for backward edges but refers to the textual ordering of the nodes if no unique alternative exists. The model order cycle breaker only refers to the textual ordering and reverses edges that go against it. Both cycle breakers support layerConstraints such as FIRST and LAST.

The difference between the GREEDY cycle breaker, the two model order cycle breakers mentioned above can be seen in the following.

The greedy cycle breaker. optimizes the number of backward edges and randomly makes a decision if no clear better alternative exists (such as for the edges between n1 and n2).

The greedy model order cycle breaker optimizes the number of backward edges and uses the model order as a tie-breaker. It reverse the edges from n2 to n1 since n2 is “after” n1 in the model.

The model order cycle breaker only uses the model order and reverses all edges that go against it such as the edge from n3 to n2 and the edges from n2 to n1.

Examples can be found here.

Layer Assignment (ELK 0.9.0)

ELK 0.9.0 will introduce model order layer assignment by node promotion. Setting nodePromotion to MODEL_ORDER_LEFT_TO_RIGHT together with LONGEST_PATH_SOURCE (and model order cycle breaking) allows to specify the layer of each node by ordering all nodes in a breath-first order.

The initial layer assignment places n4 in the layer before n3, which violates their ordering.

In the following n4 is moved in the correct layer using node promotion by model order.

Crossing Minimization (partly ELK 0.9.0)

ELK 0.8.1 already introduced model order as a tie-breaker with the considerModelOrder.strategy property, which allows to sort the nodes and ports before crossing minimization by the edge order (PREFER_EDGES), the node and the edge order (NODES_AND_EDGES), and the nodes (will be added in 0.9.0, PREFER_NODES).

The difference of the three strategies can be seen in the following drawings that were created by disabling crossing minimization:

The PREFER_EDGES pre-crossing minimization sorting strategy makes sure that the edge order is preserved before crossing minimization starts (which might scramble it again). The node order is only used for nodes without incoming edges.

The NODES_AND_EDGES pre-crossing minimization sorting strategy makes sure that the edge and node order are preserved before crossing minimization starts (which might scramble it again). Here this results in additional crossings since they are conflicting.

The PREFER_NODES pre-crossing minimization sorting strategy makes sure that the node order are preserved before crossing minimization starts (which might scramble it again). The order of the edges is also determined by the node order of their targets.

This allows the algorithm to consider the ordered graph during crossing minimization. Should it be crossing minimal, the ordering will always be used as the final solution.

If the initial ordering is not crossing minimal, the following properties allow to weight the ordering violations against the edge crossing to use model order as a tie-breaker: crossingCounterNodeInfluence, crossingCounterPortInfluence. We advice setting these to a value below zero to ensure that edge crossing are still more important than the ordering. E.g. a value of 0.1 might be optimal for some use case, which means that 10 order violations are as important as one edge crossing.

This allows to select the best ordered crossing minimal solution. Note that this is still limited by the number of random tries (see thoroughness), therefore, the optimal solution will not always be found if the thoroughness is not increased.

If one wants to only constrain the node order, this can be achieved by setting forceNodeModelOrder.

If the crossing minimization strategy is set to NONE and the greedySwitch.type is set to OFF the ordering created by the model order sorting strategy will not change and the model order is enforced.

An overview of model order as the tie-breaker, enforced node order, and no crossing minimization strategies can be seen in the following:

Examples for different model order crossing minimization strategies can be found here.

Component Ordering (partly ELK 0.9.0)

If the graph consist of several separate connected component and this separateConnectedComponent property is set to true. There are two different ways of ordering them.

• The separate components are ordered by size (default)
• The separate components are ordered by the sum of their priority property
• The separate components are ordered by model order using their minimal element (see considerModelOrder.components). The preferred strategy (MODEL_ORDER) will be introduced with the 0.9.0 release delivers a compact ordering of the separate components that considers to the model order.

I hope this helps to answer several reoccurring questions regarding ordering.