Wiki source code of Layer Sweep Crossing Minimization
Last modified by msp on 2023/07/11 10:33
Show last authors
| author | version | line-number | content |
|---|---|---|---|
| 1 | Crossing minimization is hard to get right and hard to understand once written. Case in point is our layer sweep crossing minimizer, that implements layer sweep crossing minimization in a monolithic bunch of some 1,200 lines of gloriously hard-to-understand code. (at the time of writing) A new structure is required! | ||
| 2 | |||
| 3 | [[image:attach:class_diagram.png]] | ||
| 4 | |||
| 5 | The new structure factors out much of what can possibly be factored out: | ||
| 6 | |||
| 7 | * {{code language="none"}}LayerSweepCrossingMinimizer{{/code}} is still the main class and implements the layer-sweep approach to crossing minimization. However, it does not know anymore how to do the actual crossing minimization step for a given pair of layers. However, it implements the cross counting algorithms, since these are not affected by the actual crossing minimization algorithm used. | ||
| 8 | * (% style="line-height: 1.4285715;" %)An {{code language="none"}}ICrossingMinimizationHeuristic{{/code}} is used to determine the ordering of a given set of nodes. The result is expected to adhere to any constraints, such as node successor constraints and layout unit constraints. The usual heuristic would be the {{code language="none"}}BarycenterHeuristic{{/code}}. | ||
| 9 | * The {{code language="none"}}IPortDistributor{{/code}} is used by the {{code language="none"}}LayerSweepCrossingMinimizer{{/code}} to calculate port ranks needed to determine node barycenters, and to handle the final port distribution. The standard implementation is the {{code language="none"}}NodeRelativePortDistributor{{/code}}. We're planning to add a {{code language="none"}}SimplePortDistributer{{/code}} as well that calculates port ranks as KLoDD did back in the day. | ||
| 10 | * If a heuristic doesn't know how to handle constraints, it can make use of an {{code language="none"}}IConstraintResolver{{/code}} to resolve any constraints after it has determined an initial node ordering. The standard implementation is the {{code language="none"}}ForsterConstraintResolver{{/code}}, which implements a constraint resolving heuristic proposed by Michael Forster. | ||
| 11 | * {{code language="none"}}NodeGroup{{/code}}s are used by the {{code language="none"}}CompoundGraphLayerCrossingMinimizer{{/code}} to encapsulate sets of nodes contained in a single compound node, to treat them as an atomic group with fixed ordering. |