StretchWidth
StretchWidth is a layering algorithm proposed by Nikolas S. Nikolov, Alexandre Tarassov, and Jürgen Branke
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 misinterpreted 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.
The evaluation of this variable indicates that downscaling of this upper layer bound results in smaller drawings. But it has yet to be evaluated for the pencil-metric.
Both following pictures show the width of the graphs. Orthogonal edge routing, the BK-node-placer and node promotion were used. In this case the used pixel were measured. The first image contains the results of StretchWidth with the original factor, the average out-degree. In this case StretchWidth ist is similar to LongestPath and a little to NetworkSimplex. The second diagram shows the results of other, fixed scaling factors between 0.1 and 1.0. The width is reduced (and the height increased) for values lesser then 1 indicating that there is an may be a better value, improving the original algorithm.
. In the width case all values less than 1, result in very similar behavior. But as explained later, the results, especially the pencil-metric, show no real improvement.
In both results the same graphs were used, in which all components have the same size.
Real Node Sizes
The original algorithm does not consider real node sizes. Every node and every dummy node has the same size and do not need to be differed.
The authors stated, that an implementation with real sizes should be easy. But we think that an simple addition of the real size or a normalized size (maybe by the smallest node) would reduce the validity of the rank and the upper layer estimation.
This task was realized by normalizing the width of every node by the minimum width in the graph. The width is selected dependent on the direction of the layering. Before adding the size, every placed node contributed a simple +1 to the current width. This was replaced by the normalized width of the placed node. Accordingly the CGU was adjusted.
The estimation for the next layer is still only used for the width created by the dummy nodes and in graphs with the same size for every component, the behavior should be the same as beforeThe next image shows the behavior for the height with the same configuration, but without node promotion, as in the second image. Regardless the similar results for the width, in this diagram, differences can be seen. If node promotion is used, the results would be nearly equal again. This is differently to the width, where a difference can barely be seen, not matter if with or without node promotion.
The pencil-metric for the exemplary value of 0.7( one of the lower heights) shows no overall improvement, so we don't pursue this attempt any further.
Node Promotion
Since StretchWidth, like MinWidth, creates many dummy-nodes in the layering, the authors recommend to use the node promotion Node Promotion as a post-processing step.
Our measurements show indeed, that the results improve. However the measurements show also, that node promotion doesn't have the huge impact as by MinWidth. The first Diagram shows the number of dummy nodes normalized by the number of original nodes. The results in second diagram have one through the additional post-processing of node promotion Node Promotion. The tendency may look the same, but it is important to notice the change in the y-scale.
First Results
We were able to recreate the results from the proposing paper. As additional characteristics we also measured the width and height in pixel and the pencil-metric.
We used orthogonal edge-routing and the BK-node-placer. As expected the results are very similar to longest-path, especially with increasing node count.
One example is the pencil-metric for one Din A4 sheet: the first without node promotion without Node Promotion and at the second with this post-processing step.
Both diagrams are normalized by the pencil-metric of Network Simplex to get an qualitative comparison.
Real Node Sizes
The original algorithm does not consider real node sizes. Every node and every dummy node has the same size and do not need to be differed.
The authors stated, that an implementation with real sizes should be easy. But we think that an simple addition of the real size or a normalized size (maybe by the smallest node) would reduce the validity of the rank and the upper layer estimation.
This task was realized by normalizing the width of every node by the minimum width in the graph. The width is selected dependent on the direction of the layering. Before adding the size, every placed node contributed a simple +1 to the current width. This was replaced by the normalized width of the placed node. Accordingly the CGU was adjusted.
The estimation for the next layer is still only used for the width created by the dummy nodes and in graphs with the same size for every component, the behavior is the same as before.
The size of the dummy nodes was considered over the edge spacing property. So even in the rome graphs the results differ from the first results.
The next picture shows again the pencil-metric for one A4 sheet, with Node Promotion. Please note that in this picture, MinWidth doesn't consider node sizes. There you can see an improvement to the picture from the previous section.
A second set of test graphs were SCG's but only numbered around 110. So every node may have an other size and the node could be nested.
In this pictures you can see again the pencil-metric for one A4 sheet. In the first image are the results of the original algorithm shown (no consideration of node size) and the second displays the results of the consideration of node size. MinWidth is still the original algorithm without node size. As one can see, the results show an improvement with for StretchWidth.
An unexpected result is that Node Promotion eliminates the improvements, as seen in the next image, where the size is considered and additionally Node Promotion is used.
Future Work ?
Conclusion
The original StretchWidth algorithm behaves very similar to longest path. Often only some nodes are swapped due to the sorting by the rank. Compared to its sibling algorithm MinWidth the results were rather disappointing. The first real improvement was reached, as the size of the dummy nodes was treated differently to the other nodes and was now lower than the normal nodes. This change was build along with the consideration of the real nodes sizes.
This consideration does also improve the behavior in heterogeneous graphs. But as one can imagine the displayed diagrams are drawn with the average of the results and if one looks at single graphs, especially the SCG's, one can see very different results. There are many cases in which StretchWidth fails to improve the layering and results that improve noticeably above the average. So one big remark is, that StretchWidth does benefit from the consideration of original and dummy node sizes and only in this way distinguished itself from Longest Path.
The second remark contains the understanding of the behavior in this algorithm. Especially the ConditionGoUp can be divided in to functions. First the next or upper layer estimation, which is used to estimate the dummy nodes of the next layer. Edges that reach over more than the next layer are not considered in this estimation. If one would change the influence of the dummy nodes, this criterion should be tweaked. The second part is the current layer estimation, which is initialized with the result of the upper layer estimation from the previous iteration. The nodes sizes will be added and the out-degrees subtracted. Here one can see one of the bigger estimations of this algorithm: Most of the long edges only span one layer and so only dummy nodes in the next layer will be estimated. If one want to weight the original nodes more one can mutiply the node size oder the maxwidth.
Overall the original StretchWidth does not reach its goal, to dynamically minimize the width, but rather behaves similar to Longest Path. Only if the nodes sizes are considered, and so the dummy and original nodes are weighted differently, the algorithm improves from Longest Path and produces decent results. It does not profit as strong as MinWidth from Node Promotion and this post-processing can (especially with consideration of size) even eliminate earlier improvements.