# 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 `layerChoiceConstraint`s and `positionsChoiceConstraint`s 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 `layerConstraint`s 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.

- 2022
- Rectpacking
- Edge Routing with Libavoid
- 2023
- Layered: Constraining the Model
- Top-down Layout: Zoom in the Layout Process