Stretchwidth
Stretchwidth is a layering algorithm proposed by Nikolas S. Nikolov, Alexandre Tarassov, and Jürgen Branke
in "In Search for Efficient Heuristics for Minimum-Width Graph Layering with Consideration of Dummy Nodes"
The description of this algorithm in this page refers to a top-down graph and so it may differ from the description of other algorithm in KLay Layered.
The algorithm tries to minimize the width of the layered graph by trying to apply a boundary in every layer and increasing this boundary, if it fails (e.g. if it would create an empty layer).
This approach first orders the nodes by their rank. Whereby the rank of a node v is defined as the maximum of the incoming edges in v and the maximum of the outgoing edges of all predecessors. Then it starts by the bottom of the graph and places the layerless node with the highest rank, whose successors are all already placed in a layer below. While placing the width of the actual layer and an estimation of the width of the next layer was taken into account. If the placement of a node would violate the boundary, the algorithm starts with the next layer.
Precondition: the graph has no cycles, but might contain self-loops.
Postcondition: all nodes have been assigned a layer such that edges connect only nodes from layers with increasing indices.
Implementation
In the first approach the checking if the algorithm should start a new layer was missinterpreted as " we first place the node and than we check if the boundary is violated". This includes that a placed node would only return to the layerless state if the algorithm restarts with the increased boundary.
Since this condition go up (CGU) would mostly result in a longest-path-layering, a variable was added to control the influence of the estimated next layer. It ranged from 0.0 to 1.0. Where 0.0 would result in a layering very similar to an one-node-layerer and 1.0. would again be the longest-path-layerer. In between were multiple nuances, whose nodes per layer increased monotonically from 0.0 to 1.0.
The actual CGU only hypothetically places the node and only if it doesn't violate the boundary, the node will be placed. With this CGU we were able to reproduce the results from the Paper in which the algorithm was proposed, but naturally the added variable doesn't work as clear as before.
If this variable could be further used , is going to be answered as one of the next goals.