Skip to Content
Last modified by msp on 2023/07/11 10:33
From version 1.1
edited by cds
on 2012/03/23 15:37
Change comment: There is no comment for this version
To version 9.2
edited by msp
on 2023/07/06 14:36
Change comment: Update document after refactoring.

Summary

Details

Page properties
Parent
... ... @@ -1,0 +1,1 @@
1 +KIELER.Home.Discontinued Projects.Layout Algorithms (KLay).KLay Layered.WebHome
Author
... ... @@ -1,1 +1,1 @@
1 -XWiki.cds
1 +XWiki.msp
Content
... ... @@ -1,0 +1,11 @@
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.
class_diagram.png
Author
... ... @@ -1,0 +1,1 @@
1 +XWiki.XWikiGuest
Size
... ... @@ -1,0 +1,1 @@
1 +29.9 KB
Content
Confluence.Code.ConfluencePageClass[0]
Id
... ... @@ -1,1 +1,1 @@
1 -884891
1 +884888
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/884891/Layer Sweep Crossing Minimization
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/884888/Layer Sweep Crossing Minimization