Skip to Content

Changes for page The Five Phases

Last modified by Alexander Schulz-Rosengarten on 2023/07/11 10:33
From version 13.1
edited by cds
on 2014/11/23 14:32
Change comment: There is no comment for this version
To version 9.1
edited by cds
on 2012/07/17 13:11
Change comment: There is no comment for this version

Summary

Details

Page properties
Parent
... ... @@ -1,1 +1,0 @@
1 -KLay Layered
Content
... ... @@ -10,22 +10,23 @@
10 10  
11 11  |=(((
12 12  Preconditions
13 -)))|(((
13 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
14 +(((
14 14  * No node is assigned to a layer yet.
15 15  )))
16 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
17 +|(% class="highlight" %)(% class="highlight" %)
17 17  (((
18 18  Postconditions
19 19  )))|(((
20 20  * The graph is now cycle-free. Still, no node is assigned to a layer yet.
21 21  )))
22 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
23 +|(% class="highlight" %)(% class="highlight" %)
23 23  (((
24 24  Remarks
25 25  )))|(((
26 26  * All implementations of phase one must include a dependency on the {{code language="none"}}ReversedEdgeRestorer{{/code}}, to be included after phase five.
27 27  )))
28 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
29 +|(% class="highlight" %)(% class="highlight" %)
29 29  (((
30 30  Implementations
31 31  )))|(((
... ... @@ -33,13 +33,6 @@
33 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 34  * {{code language="none"}}InteractiveCycleBreaker.{{/code}} Detects feedback edges according to the current layout, hence it reacts to the user's placement.
35 35  )))
36 -|=(% colspan="1" %)(% colspan="1" %)
37 -(((
38 -Tests
39 -)))|(% colspan="1" %)(% colspan="1" %)
40 -(((
41 -* The graph contains no cycles.
42 -)))
43 43  
44 44  == Phase 2: Layering ==
45 45  
... ... @@ -51,23 +51,24 @@
51 51  
52 52  |=(((
53 53  Preconditions
54 -)))|(((
48 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
49 +(((
55 55  * The graph is cycle-free.
56 56  * The nodes have not been layered yet.
57 57  )))
58 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
53 +|(% class="highlight" %)(% class="highlight" %)
59 59  (((
60 60  Postconditions
61 61  )))|(((
62 62  * The graph has a layering.
63 63  )))
64 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
59 +|(% class="highlight" %)(% class="highlight" %)
65 65  (((
66 66  Remarks
67 67  )))|(((
68 68  * Implementations should usually include a dependency on the {{code language="none"}}LayerConstraintHandler{{/code}}, unless they already adhere to layer constraints themselves.
69 69  )))
70 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
65 +|(% class="highlight" %)(% class="highlight" %)
71 71  (((
72 72  Implementations
73 73  )))|(((
... ... @@ -78,16 +78,6 @@
78 78  )))
79 79  * {{code language="none"}}InteractiveLayerer.{{/code}} Detects layers according to the current layout, hence it reacts to the user's placement.
80 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 -)))
91 91  
92 92  == Phase 3: Crossing Reduction ==
93 93  
... ... @@ -97,12 +97,13 @@
97 97  
98 98  |=(((
99 99  Preconditions
100 -)))|(((
85 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
86 +(((
101 101  * The graph has a proper layering. (except for self-loops)
102 102  * An implementation may allow in-layer connections.
103 103  * Usually, all nodes are required to have a least fixed port sides.
104 104  )))
105 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
91 +|(% class="highlight" %)(% class="highlight" %)
106 106  (((
107 107  Postconditions
108 108  )))|(((
... ... @@ -109,7 +109,7 @@
109 109  * The order of nodes in each layer is fixed.
110 110  * All nodes have a fixed port order.
111 111  )))
112 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
98 +|(% class="highlight" %)(% class="highlight" %)
113 113  (((
114 114  Remarks
115 115  )))|(((
... ... @@ -116,7 +116,7 @@
116 116  * If fixed port sides are required, the {{code language="none"}}PortPositionProcessor{{/code}} may be of use.
117 117  * Support for in-layer connections may be required to be able to handle certain problems. (odd port sides, for instance)
118 118  )))
119 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
105 +|(% class="highlight" %)(% class="highlight" %)
120 120  (((
121 121  Implementations
122 122  )))|(((
... ... @@ -123,13 +123,6 @@
123 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 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 125  )))
126 -|=(% colspan="1" %)(% colspan="1" %)
127 -(((
128 -Tests
129 -)))|(% colspan="1" %)(% colspan="1" %)
130 -(((
131 -* All nodes remain in their respective layer.
132 -)))
133 133  
134 134  == Phase 4: Node Placement ==
135 135  
... ... @@ -139,7 +139,8 @@
139 139  
140 140  |=(((
141 141  Preconditions
142 -)))|(((
121 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
122 +(((
143 143  * The graph has a proper layering. (except for self-loops)
144 144  * Node orders are fixed.
145 145  * Port positions are fixed.
... ... @@ -146,7 +146,7 @@
146 146  * An implementation may allow in-layer connections.
147 147  * An implementation may require node margins to be set.
148 148  )))
149 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
129 +|(% class="highlight" %)(% class="highlight" %)
150 150  (((
151 151  Postconditions
152 152  )))|(((
... ... @@ -154,7 +154,7 @@
154 154  * The height of each layer is set.
155 155  * The height of the graph is set to the maximal layer height.
156 156  )))
157 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
137 +|(% class="highlight" %)(% class="highlight" %)
158 158  (((
159 159  Remarks
160 160  )))|(((
... ... @@ -162,7 +162,7 @@
162 162  * If node margins are supported, the {{code language="none"}}NodeMarginCalculator{{/code}} can compute them.
163 163  * Port positions can be fixed by using the {{code language="none"}}PortPositionProcessor{{/code}}.
164 164  )))
165 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
145 +|(% class="highlight" %)(% class="highlight" %)
166 166  (((
167 167  Implementations
168 168  )))|(((
... ... @@ -174,16 +174,7 @@
174 174  ** (((
175 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 176  )))
177 -* {{code language="none"}}InteractiveNodePlacer{{/code}}. Tries to keep the preset coordinates of nodes from the original layout. For dummy nodes, a guess is made to infer their coordinates. Requires the other interactive phase implementations to have run as well.
178 178  )))
179 -|=(% colspan="1" %)(% colspan="1" %)
180 -(((
181 -Tests
182 -)))|(% colspan="1" %)(% colspan="1" %)
183 -(((
184 -* The nodes of a layer are strictly ordered with regards to their y coordinate.
185 -* Any two nodes of a layer do not overlap with regards to their bounding box (height + margins).
186 -)))
187 187  
188 188  == Phase 5: Edge Routing ==
189 189  
... ... @@ -191,13 +191,14 @@
191 191  
192 192  |=(((
193 193  Preconditions
194 -)))|(((
165 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
166 +(((
195 195  * The graph has a proper layering. (except for self-loops)
196 196  * Nodes are assigned y coordinates.
197 197  * Layer heights are correctly set.
198 198  * An implementation may allow in-layer connections.
199 199  )))
200 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
172 +|(% class="highlight" %)(% class="highlight" %)
201 201  (((
202 202  Postconditions
203 203  )))|(((
... ... @@ -206,13 +206,13 @@
206 206  * The graph's width is set.
207 207  * The bend points of all edges are set.
208 208  )))
209 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
181 +|(% class="highlight" %)(% class="highlight" %)
210 210  (((
211 211  Remarks
212 212  )))|(((
213 213  None.
214 214  )))
215 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
187 +|(% class="highlight" %)(% class="highlight" %)
216 216  (((
217 217  Implementations
218 218  )))|(((
... ... @@ -223,10 +223,3 @@
223 223  * {{code language="none"}}PolylineEdgeRouter{{/code}}. Simplest routing style that just inserts bend points at the position of long edge dummy nodes.
224 224  * {{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.
225 225  )))
226 -|=(% colspan="1" %)(% colspan="1" %)
227 -(((
228 -Tests
229 -)))|(% colspan="1" %)(% colspan="1" %)
230 -(((
231 -* {{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.
232 -)))
Confluence.Code.ConfluencePageClass[0]
Id
... ... @@ -1,1 +1,1 @@
1 -884883
1 +7110890
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/884883/The Five Phases
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/7110890/The Five Phases