Skip to Content

Changes for page The Five Phases

Last modified by Alexander Schulz-Rosengarten on 2023/07/11 10:33
From version 9.1
edited by cds
on 2012/07/17 13:11
Change comment: There is no comment for this version
To version 11.1
edited by uru
on 2013/05/27 08:43
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
... ... @@ -10,23 +10,22 @@
10 10  
11 11  |=(((
12 12  Preconditions
13 -)))|=(% class="nohighlight" %)(% class="nohighlight" %)
14 -(((
13 +)))|(((
15 15  * No node is assigned to a layer yet.
16 16  )))
17 -|(% class="highlight" %)(% class="highlight" %)
16 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
18 18  (((
19 19  Postconditions
20 20  )))|(((
21 21  * The graph is now cycle-free. Still, no node is assigned to a layer yet.
22 22  )))
23 -|(% class="highlight" %)(% class="highlight" %)
22 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
24 24  (((
25 25  Remarks
26 26  )))|(((
27 27  * All implementations of phase one must include a dependency on the {{code language="none"}}ReversedEdgeRestorer{{/code}}, to be included after phase five.
28 28  )))
29 -|(% class="highlight" %)(% class="highlight" %)
28 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
30 30  (((
31 31  Implementations
32 32  )))|(((
... ... @@ -34,6 +34,13 @@
34 34  ** 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.
35 35  * {{code language="none"}}InteractiveCycleBreaker.{{/code}} Detects feedback edges according to the current layout, hence it reacts to the user's placement.
36 36  )))
36 +|=(% colspan="1" %)(% colspan="1" %)
37 +(((
38 +Tests
39 +)))|(% colspan="1" %)(% colspan="1" %)
40 +(((
41 +* The graph contains no cycles.
42 +)))
37 37  
38 38  == Phase 2: Layering ==
39 39  
... ... @@ -45,24 +45,23 @@
45 45  
46 46  |=(((
47 47  Preconditions
48 -)))|=(% class="nohighlight" %)(% class="nohighlight" %)
49 -(((
54 +)))|(((
50 50  * The graph is cycle-free.
51 51  * The nodes have not been layered yet.
52 52  )))
53 -|(% class="highlight" %)(% class="highlight" %)
58 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
54 54  (((
55 55  Postconditions
56 56  )))|(((
57 57  * The graph has a layering.
58 58  )))
59 -|(% class="highlight" %)(% class="highlight" %)
64 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
60 60  (((
61 61  Remarks
62 62  )))|(((
63 63  * Implementations should usually include a dependency on the {{code language="none"}}LayerConstraintHandler{{/code}}, unless they already adhere to layer constraints themselves.
64 64  )))
65 -|(% class="highlight" %)(% class="highlight" %)
70 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
66 66  (((
67 67  Implementations
68 68  )))|(((
... ... @@ -73,6 +73,16 @@
73 73  )))
74 74  * {{code language="none"}}InteractiveLayerer.{{/code}} Detects layers according to the current layout, hence it reacts to the user's placement.
75 75  )))
81 +|=(% colspan="1" %)(% colspan="1" %)
82 +(((
83 +
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 +)))
76 76  
77 77  == Phase 3: Crossing Reduction ==
78 78  
... ... @@ -82,13 +82,12 @@
82 82  
83 83  |=(((
84 84  Preconditions
85 -)))|=(% class="nohighlight" %)(% class="nohighlight" %)
86 -(((
100 +)))|(((
87 87  * The graph has a proper layering. (except for self-loops)
88 88  * An implementation may allow in-layer connections.
89 89  * Usually, all nodes are required to have a least fixed port sides.
90 90  )))
91 -|(% class="highlight" %)(% class="highlight" %)
105 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
92 92  (((
93 93  Postconditions
94 94  )))|(((
... ... @@ -95,7 +95,7 @@
95 95  * The order of nodes in each layer is fixed.
96 96  * All nodes have a fixed port order.
97 97  )))
98 -|(% class="highlight" %)(% class="highlight" %)
112 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
99 99  (((
100 100  Remarks
101 101  )))|(((
... ... @@ -102,7 +102,7 @@
102 102  * If fixed port sides are required, the {{code language="none"}}PortPositionProcessor{{/code}} may be of use.
103 103  * Support for in-layer connections may be required to be able to handle certain problems. (odd port sides, for instance)
104 104  )))
105 -|(% class="highlight" %)(% class="highlight" %)
119 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
106 106  (((
107 107  Implementations
108 108  )))|(((
... ... @@ -109,6 +109,13 @@
109 109  * {{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.
110 110  * {{code language="none"}}InteractiveCrossingMinimizer.{{/code}} Detects the order of nodes according to the current layout, hence it reacts to the user's placement.
111 111  )))
126 +|=(% colspan="1" %)(% colspan="1" %)
127 +(((
128 +Tests
129 +)))|(% colspan="1" %)(% colspan="1" %)
130 +(((
131 +* All nodes remain in their respective layer.
132 +)))
112 112  
113 113  == Phase 4: Node Placement ==
114 114  
... ... @@ -118,8 +118,7 @@
118 118  
119 119  |=(((
120 120  Preconditions
121 -)))|=(% class="nohighlight" %)(% class="nohighlight" %)
122 -(((
142 +)))|(((
123 123  * The graph has a proper layering. (except for self-loops)
124 124  * Node orders are fixed.
125 125  * Port positions are fixed.
... ... @@ -126,7 +126,7 @@
126 126  * An implementation may allow in-layer connections.
127 127  * An implementation may require node margins to be set.
128 128  )))
129 -|(% class="highlight" %)(% class="highlight" %)
149 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
130 130  (((
131 131  Postconditions
132 132  )))|(((
... ... @@ -134,7 +134,7 @@
134 134  * The height of each layer is set.
135 135  * The height of the graph is set to the maximal layer height.
136 136  )))
137 -|(% class="highlight" %)(% class="highlight" %)
157 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
138 138  (((
139 139  Remarks
140 140  )))|(((
... ... @@ -142,7 +142,7 @@
142 142  * If node margins are supported, the {{code language="none"}}NodeMarginCalculator{{/code}} can compute them.
143 143  * Port positions can be fixed by using the {{code language="none"}}PortPositionProcessor{{/code}}.
144 144  )))
145 -|(% class="highlight" %)(% class="highlight" %)
165 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
146 146  (((
147 147  Implementations
148 148  )))|(((
... ... @@ -155,6 +155,14 @@
155 155  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.
156 156  )))
157 157  )))
178 +|=(% colspan="1" %)(% colspan="1" %)
179 +(((
180 +
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 +)))
158 158  
159 159  == Phase 5: Edge Routing ==
160 160  
... ... @@ -162,14 +162,13 @@
162 162  
163 163  |=(((
164 164  Preconditions
165 -)))|=(% class="nohighlight" %)(% class="nohighlight" %)
166 -(((
193 +)))|(((
167 167  * The graph has a proper layering. (except for self-loops)
168 168  * Nodes are assigned y coordinates.
169 169  * Layer heights are correctly set.
170 170  * An implementation may allow in-layer connections.
171 171  )))
172 -|(% class="highlight" %)(% class="highlight" %)
199 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
173 173  (((
174 174  Postconditions
175 175  )))|(((
... ... @@ -178,13 +178,13 @@
178 178  * The graph's width is set.
179 179  * The bend points of all edges are set.
180 180  )))
181 -|(% class="highlight" %)(% class="highlight" %)
208 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
182 182  (((
183 183  Remarks
184 184  )))|(((
185 185  None.
186 186  )))
187 -|(% class="highlight" %)(% class="highlight" %)
214 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
188 188  (((
189 189  Implementations
190 190  )))|(((
... ... @@ -195,3 +195,10 @@
195 195  * {{code language="none"}}PolylineEdgeRouter{{/code}}. Simplest routing style that just inserts bend points at the position of long edge dummy nodes.
196 196  * {{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.
197 197  )))
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 -7110890
1 +7111017
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/7110890/The Five Phases
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/7111017/The Five Phases