Skip to Content

Changes for page The Five Phases

Last modified by Alexander Schulz-Rosengarten on 2023/07/11 10:33
From version 1.1
edited by cds
on 2012/03/23 15:31
Change comment: There is no comment for this version
To version 12.1
edited by uru
on 2013/05/27 15:50
Change comment: There is no comment for this version

Summary

Details

Page properties
Author
... ... @@ -1,1 +1,1 @@
1 -XWiki.cds
1 +XWiki.uru
Content
... ... @@ -1,4 +1,4 @@
1 -This page describes the algorithm's five main phases and the available implementations. You can find a list and descriptions of the intermediate processors below.
1 +This page describes the algorithm's five main phases and the available implementations. You can find a list and descriptions of the intermediate processors [[over here>>doc:Intermediate Processors]].
2 2  
3 3  == Phase 1: Cycle Removal ==
4 4  
... ... @@ -8,22 +8,39 @@
8 8  
9 9  The reversed edges have to be restored at some point. There's a processor for that, called ReversedEdgeRestorer. All implementations of phase one must include a dependency on that processor, to be included after phase 5.
10 10  
11 -=== Precondition ===
12 -
11 +|=(((
12 +Preconditions
13 +)))|(((
13 13  * No node is assigned to a layer yet.
14 -
15 -=== Postcondition ===
16 -
15 +)))
16 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
17 +(((
18 +Postconditions
19 +)))|(((
17 17  * The graph is now cycle-free. Still, no node is assigned to a layer yet.
21 +)))
22 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
23 +(((
24 +Remarks
25 +)))|(((
26 +* All implementations of phase one must include a dependency on the {{code language="none"}}ReversedEdgeRestorer{{/code}}, to be included after phase five.
27 +)))
28 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
29 +(((
30 +Implementations
31 +)))|(((
32 +* {{code language="none"}}GreedyCycleBreaker{{/code}}. Uses a greedy approach to cycle-breaking, inspired by \\
33 +** Peter Eades, Xuemin Lin, W. F. Smyth, A fast and effective heuristic for the feedback arc set problem. //Information Processing Letters// 47(6), pp. 319-323, 1993.
34 +* {{code language="none"}}InteractiveCycleBreaker.{{/code}} Detects feedback edges according to the current layout, hence it reacts to the user's placement.
35 +)))
36 +|=(% colspan="1" %)(% colspan="1" %)
37 +(((
38 +Tests
39 +)))|(% colspan="1" %)(% colspan="1" %)
40 +(((
41 +* The graph contains no cycles.
42 +)))
18 18  
19 -=== Remarks ===
20 -
21 -* All implementations of phase one must include a dependency on the ReversedEdgeRestorer, to be included after phase 5.
22 -
23 -=== Current Implementations ===
24 -
25 -* GreedyCycleBreaker. Uses a greedy approach to cycle-breaking.
26 -
27 27  == Phase 2: Layering ==
28 28  
29 29  The second phase assigns nodes to layers. (also called //ranks// in some papers) Nodes in the same layer are assigned the same x coordinate. (give or take) The problem to solve here is to assign each node x a layer i such that each successor of x is in a layer j>i. The only exception are self-loops, that may or may not be supported by later phases.
... ... @@ -32,50 +32,88 @@
32 32  
33 33  Note that nodes can have a property associated with them that constraints the layers they can be placed in.
34 34  
35 -=== Precondition ===
36 -
52 +|=(((
53 +Preconditions
54 +)))|(((
37 37  * The graph is cycle-free.
38 38  * The nodes have not been layered yet.
39 -
40 -=== Postcondition ===
41 -
57 +)))
58 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
59 +(((
60 +Postconditions
61 +)))|(((
42 42  * The graph has a layering.
63 +)))
64 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
65 +(((
66 +Remarks
67 +)))|(((
68 +* Implementations should usually include a dependency on the {{code language="none"}}LayerConstraintHandler{{/code}}, unless they already adhere to layer constraints themselves.
69 +)))
70 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
71 +(((
72 +Implementations
73 +)))|(((
74 +* {{code language="none"}}LongestPathLayerer{{/code}}. Layers nodes according to the longest paths between them. Very simple, and doesn't usually give the best results.
75 +* {{code language="none"}}NetworkSimplexLayerer{{/code}}. A way more sophisticated algorithm whose results are usually very good, inspired by\\
76 +** (((
77 +Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, Kiem-Phong Vo, A technique for drawing directed graphs. //Software Engineering// 19(3), pp. 214-230, 1993.
78 +)))
79 +* {{code language="none"}}InteractiveLayerer.{{/code}} Detects layers according to the current layout, hence it reacts to the user's placement.
80 +)))
81 +|=(% colspan="1" %)(% colspan="1" %)
82 +(((
83 +Tests
84 +)))|(% colspan="1" %)(% colspan="1" %)
85 +(((
86 +* The set of layerless nodes is empty.
87 +* For every edge that points from layer {{code language="none"}}i{{/code}} to layer {{code language="none"}}j, i<j{{/code}} holds.
88 +* No empty layer exists.
89 +* All nodes that existed prior to this phase are assigned to a layer.
90 +)))
43 43  
44 -=== Remarks ===
45 -
46 -* Implementations should usually include a dependency on the LayerConstraintHandler, unless they already adhere to layer constraints themselves.
47 -
48 -=== Current Implementations ===
49 -
50 -* LongestPathLayerer. Layers nodes according to the longest paths between them. Very simple, but doesn't usually give the best results.
51 -* NetworkSimplexLayerer. A way more sophisticated algorithm whose results are usually very good.
52 -
53 53  == Phase 3: Crossing Reduction ==
54 54  
55 -The objective of phase 3 is to determine how the nodes in each layer should be ordered. The order determines the number of edge crossings, and thus is a critical step towards readable diagrams. Unfortunately, the problem is NP-hard even for only two layers. Did I just hear you saying "heuristic"? The usual approach is to sweep through the pairs of layers from left to right and back, along the way applying some heuristic to minimize crossings between each pair of layers. The two most prominent and well-studied kinds of heuristics used here are the barycenter method and the median method. We have currently implemented the former.
94 +The objective of phase 3 is to determine how the nodes in each layer should be ordered. The order determines the number of edge crossings, and thus is a critical step towards readable diagrams. Unfortunately, the problem is NP-hard even for only two layers. Did I just hear you say "heuristic"? The usual approach is to sweep through the pairs of layers from left to right and back, along the way applying some heuristic to minimize crossings between each pair of layers. The two most prominent and well-studied kinds of heuristics used here are the barycenter method and the median method. We have currently implemented the former.
56 56  
57 57  Our crossing reduction implementations may or may not support the concepts of node successor constraints and layout groups. The former allows a node x to specify a node y!=x that may only appear after x. Layout groups are groups of nodes. Nodes belonging to different layout groups are not to be interleaved.
58 58  
59 -=== Precondition ===
60 -
98 +|=(((
99 +Preconditions
100 +)))|(((
61 61  * The graph has a proper layering. (except for self-loops)
62 62  * An implementation may allow in-layer connections.
63 -* Usually, all Nodes are required to have at least fixed port sides.
64 -
65 -=== Postcondition ===
66 -
103 +* Usually, all nodes are required to have a least fixed port sides.
104 +)))
105 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
106 +(((
107 +Postconditions
108 +)))|(((
67 67  * The order of nodes in each layer is fixed.
68 68  * All nodes have a fixed port order.
69 -
70 -=== Remarks ===
71 -
72 -* If fixed port sides are required, the PortPositionProcessor may be of use.
111 +)))
112 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
113 +(((
114 +Remarks
115 +)))|(((
116 +* If fixed port sides are required, the {{code language="none"}}PortPositionProcessor{{/code}} may be of use.
73 73  * Support for in-layer connections may be required to be able to handle certain problems. (odd port sides, for instance)
118 +)))
119 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
120 +(((
121 +Implementations
122 +)))|(((
123 +* {{code language="none"}}LayerSweepCrossingMinmizer{{/code}}. Does several sweeps across the layers, minimizing the crossings between each pair of layers using a barycenter heuristic. Supports node successor constraints and layout groups. Node successor constraints require one node to appear before another node. Layout groups specify sets of nodes whose nodes must not be interleaved. See [[this page>>doc:Layer Sweep Crossing Minimization]] for more information.
124 +* {{code language="none"}}InteractiveCrossingMinimizer.{{/code}} Detects the order of nodes according to the current layout, hence it reacts to the user's placement.
125 +)))
126 +|=(% colspan="1" %)(% colspan="1" %)
127 +(((
128 +Tests
129 +)))|(% colspan="1" %)(% colspan="1" %)
130 +(((
131 +* All nodes remain in their respective layer.
132 +)))
74 74  
75 -=== Current Implementations ===
76 -
77 -* [[LayerSweepCrossingMinimizer>>url:https://trac.rtsys.informatik.uni-kiel.de/trac/kieler/wiki/Projects/KLay/Layered/LayerSweepCrossingMinimizer||shape="rect" class="wiki"]]. Does several sweeps across the layers, minimizing the crossings between each pair of layers using a barycenter heuristic. Supports node successor constraints and layout groups. Node successor constraints require one node to appear before another node. Layout groups specify sets of nodes whose nodes must not be interleaved.
78 -
79 79  == Phase 4: Node Placement ==
80 80  
81 81  So far, the coordinates of the nodes have not been touched. That's about to change in phase 4, which determines the y coordinate. While phase 3 has an impact on the number of edge crossings, phase 4 has an influence on the number of edge bends. Usually, some kind of heuristic is employed to yield a good y coordinate.
... ... @@ -82,55 +82,95 @@
82 82  
83 83  Our node placers may or may not support node margins. Node margins define the space occupied by ports, labels and such. The idea is to keep that space free from edges and other nodes.
84 84  
85 -=== Precondition ===
86 -
140 +|=(((
141 +Preconditions
142 +)))|(((
87 87  * The graph has a proper layering. (except for self-loops)
88 88  * Node orders are fixed.
89 89  * Port positions are fixed.
90 90  * An implementation may allow in-layer connections.
91 91  * An implementation may require node margins to be set.
92 -
93 -=== Postcondition ===
94 -
148 +)))
149 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
150 +(((
151 +Postconditions
152 +)))|(((
95 95  * Each node is assigned a y coordinate such that no two nodes overlap.
96 96  * The height of each layer is set.
97 97  * The height of the graph is set to the maximal layer height.
98 -
99 -=== Remarks ===
100 -
156 +)))
157 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
158 +(((
159 +Remarks
160 +)))|(((
101 101  * Support for in-layer connections may be required to be able to handle certain problems. (odd port sides, for instance)
102 -* If node margins are supported, the NodeMarginCalculator can compute them.
103 -* Port positions can be fixed by using the PortPositionProcessor.
162 +* If node margins are supported, the {{code language="none"}}NodeMarginCalculator{{/code}} can compute them.
163 +* Port positions can be fixed by using the {{code language="none"}}PortPositionProcessor{{/code}}.
164 +)))
165 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
166 +(((
167 +Implementations
168 +)))|(((
169 +* {{code language="none"}}LinearSegmentsNodePlacer{{/code}}. Builds linear segments of nodes that should have the same y coordinate and tries to respect those linear segments. Linear segments are placed according to a barycenter heuristic. Inspired by\\
170 +** (((
171 +Georg Sander, A fast heuristic for hierarchical Manhattan layout. In //Proceedings of the Symposium on Graph Drawing (GD'95)//, LNCS vol. 1027, pp. 447-458, Springer, 1996.
172 +)))
173 +* {{code language="none"}}BKNodePlacer.{{/code}} Assembles nodes into blocks placed in straight lines in an attempt to minimize the number of edge bends, similar to the linear segments node placer. However, instead of using a barycenter heuristic to place nodes, the placement also tries to minimize the number of edge bends, usually resulting in diagrams that require more space.\\
174 +** (((
175 +Ulrik Brandes and Boris Köpf, Fast and simple horizontal coordinate assignment. In //Proceedings of the 9th International Symposium on Graph Drawing (GD'01)//, LNCS vol. 2265, pp. 33-36, Springer, 2002.
176 +)))
177 +)))
178 +|=(% colspan="1" %)(% colspan="1" %)
179 +(((
180 +Tests
181 +)))|(% colspan="1" %)(% colspan="1" %)
182 +(((
183 +* The nodes of a layer are strictly ordered with regards to their y coordinate.
184 +* Any two nodes of a layer do not overlap with regards to their bounding box (height + margins).
185 +)))
104 104  
105 -=== Current Implementations ===
106 -
107 -* LinearSegmentsNodePlacer. Builds linear segments of nodes that should have the same y coordinate and tries to respect those linear segments. Linear segments are placed according to a barycenter heuristic.
108 -
109 109  == Phase 5: Edge Routing ==
110 110  
111 111  In the last phase, it's time to determine x coordinates for all nodes and route the edges. The routing may support very different kinds of features, such as support for odd port sides, (input ports that are on the node's right side) orthogonal edges, spline edges etc. Often times, the set of features supported by an edge router largely determines the intermediate processors used during the layout process.
112 112  
113 -=== Precondition ===
114 -
191 +|=(((
192 +Preconditions
193 +)))|(((
115 115  * The graph has a proper layering. (except for self-loops)
116 116  * Nodes are assigned y coordinates.
117 117  * Layer heights are correctly set.
118 118  * An implementation may allow in-layer connections.
119 -
120 -=== Postcondition ===
121 -
198 +)))
199 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
200 +(((
201 +Postconditions
202 +)))|(((
122 122  * Nodes are assigned x coordinates.
123 123  * Layer widths are set.
124 124  * The graph's width is set.
125 125  * The bend points of all edges are set.
126 -
127 -=== Remarks ===
128 -
207 +)))
208 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
209 +(((
210 +Remarks
211 +)))|(((
129 129  None.
130 -
131 -=== Current Implementations ===
132 -
133 -* ComplexSplineRouter. TODO: Document.
134 -* OrthogonalEdgeRouter. Routes edges orthogonally. Supports routing edges going into an eastern port around a node. Tries to minimize the width of the space between each pair of layers used for edge routing.
135 -* PolylineEdgeRouter. TODO: Document.
136 -* SimpleSplineEdgeRouter. TODO: Document.
213 +)))
214 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
215 +(((
216 +Implementations
217 +)))|(((
218 +* {{code language="none"}}OrthogonalEdgeRouter{{/code}}. Routes edges orthogonally. Supports routing edges going into an eastern port around a node. Tries to minimize the width of the space between each pair of layers used for edge routing. Inspired by\\
219 +** (((
220 +Georg Sander, Layout of directed hypergraphs with orthogonal hyperedges. In //Proceedings of the 11th International Symposium on Graph Drawing (GD '03)//, LNCS vol. 2912, pp. 381-386, Springer, 2004.
221 +)))
222 +* {{code language="none"}}PolylineEdgeRouter{{/code}}. Simplest routing style that just inserts bend points at the position of long edge dummy nodes.
223 +* {{code language="none"}}SplineEdgeRouter{{/code}}. A simple method for routing the edges with splines. Uses the long edge dummy nodes as reference points for spline calculation.
224 +)))
225 +|=(% colspan="1" %)(% colspan="1" %)
226 +(((
227 +Tests
228 +)))|(% colspan="1" %)(% colspan="1" %)
229 +(((
230 +* {{code language="none"}}OrthogonalEdgeRouter{{/code}}: For any two succeeding bendpoints of an edge either the y coordinates or the x coordinates are the same. Starting with the same x coordinates, alternating equality is required.
231 +)))
Confluence.Code.ConfluencePageClass[0]
Id
... ... @@ -1,1 +1,1 @@
1 -884886
1 +10158143
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/884886/The Five Phases
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/10158143/The Five Phases