Skip to Content

Changes for page The Five Phases

Last modified by Alexander Schulz-Rosengarten on 2023/07/11 10:33
From version 7.1
edited by msp
on 2012/07/17 13:04
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.msp
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 +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 +)))
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,12 +102,20 @@
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 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.
124 +* {{code language="none"}}InteractiveCrossingMinimizer.{{/code}} Detects the order of nodes according to the current layout, hence it reacts to the user's placement.
110 110  )))
126 +|=(% colspan="1" %)(% colspan="1" %)
127 +(((
128 +Tests
129 +)))|(% colspan="1" %)(% colspan="1" %)
130 +(((
131 +* All nodes remain in their respective layer.
132 +)))
111 111  
112 112  == Phase 4: Node Placement ==
113 113  
... ... @@ -117,8 +117,7 @@
117 117  
118 118  |=(((
119 119  Preconditions
120 -)))|=(% class="nohighlight" %)(% class="nohighlight" %)
121 -(((
142 +)))|(((
122 122  * The graph has a proper layering. (except for self-loops)
123 123  * Node orders are fixed.
124 124  * Port positions are fixed.
... ... @@ -125,7 +125,7 @@
125 125  * An implementation may allow in-layer connections.
126 126  * An implementation may require node margins to be set.
127 127  )))
128 -|(% class="highlight" %)(% class="highlight" %)
149 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
129 129  (((
130 130  Postconditions
131 131  )))|(((
... ... @@ -133,7 +133,7 @@
133 133  * The height of each layer is set.
134 134  * The height of the graph is set to the maximal layer height.
135 135  )))
136 -|(% class="highlight" %)(% class="highlight" %)
157 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
137 137  (((
138 138  Remarks
139 139  )))|(((
... ... @@ -141,7 +141,7 @@
141 141  * If node margins are supported, the {{code language="none"}}NodeMarginCalculator{{/code}} can compute them.
142 142  * Port positions can be fixed by using the {{code language="none"}}PortPositionProcessor{{/code}}.
143 143  )))
144 -|(% class="highlight" %)(% class="highlight" %)
165 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
145 145  (((
146 146  Implementations
147 147  )))|(((
... ... @@ -149,11 +149,19 @@
149 149  ** (((
150 150  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.
151 151  )))
152 -* {{code language="none"}}BKNodePlacer.{{/code}} ??? Inspired by\\
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.\\
153 153  ** (((
154 154  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.
155 155  )))
156 156  )))
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 +)))
157 157  
158 158  == Phase 5: Edge Routing ==
159 159  
... ... @@ -161,14 +161,13 @@
161 161  
162 162  |=(((
163 163  Preconditions
164 -)))|=(% class="nohighlight" %)(% class="nohighlight" %)
165 -(((
193 +)))|(((
166 166  * The graph has a proper layering. (except for self-loops)
167 167  * Nodes are assigned y coordinates.
168 168  * Layer heights are correctly set.
169 169  * An implementation may allow in-layer connections.
170 170  )))
171 -|(% class="highlight" %)(% class="highlight" %)
199 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
172 172  (((
173 173  Postconditions
174 174  )))|(((
... ... @@ -177,13 +177,13 @@
177 177  * The graph's width is set.
178 178  * The bend points of all edges are set.
179 179  )))
180 -|(% class="highlight" %)(% class="highlight" %)
208 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
181 181  (((
182 182  Remarks
183 183  )))|(((
184 184  None.
185 185  )))
186 -|(% class="highlight" %)(% class="highlight" %)
214 +|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
187 187  (((
188 188  Implementations
189 189  )))|(((
... ... @@ -194,3 +194,10 @@
194 194  * {{code language="none"}}PolylineEdgeRouter{{/code}}. Simplest routing style that just inserts bend points at the position of long edge dummy nodes.
195 195  * {{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.
196 196  )))
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 -1998960
1 +10158143
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/1998960/The Five Phases
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/10158143/The Five Phases