Skip to Content

Changes for page The Five Phases

Last modified by Alexander Schulz-Rosengarten on 2023/07/11 10:33
From version 11.1
edited by uru
on 2013/05/27 08:43
Change comment: There is no comment for this version
To version 6.1
edited by cds
on 2012/03/24 14:45
Change comment: Linked to further documentation

Summary

Details

Page properties
Author
... ... @@ -1,1 +1,1 @@
1 -XWiki.uru
1 +XWiki.cds
Content
... ... @@ -10,36 +10,28 @@
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  )))|(((
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.
33 +* {{code language="none"}}GreedyCycleBreaker{{/code}}. Uses a greedy approach to cycle-breaking.
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,43 +51,30 @@
51 51  
52 52  |=(((
53 53  Preconditions
54 -)))|(((
46 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
47 +(((
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" %)
51 +|(% 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" %)
57 +|(% 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" %)
63 +|(% class="highlight" %)(% class="highlight" %)
71 71  (((
72 72  Implementations
73 73  )))|(((
74 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.
68 +* {{code language="none"}}NetworkSimplexLayerer{{/code}}. A way more sophisticated algorithm whose results are usually very good.
78 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 -
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 -)))|(((
79 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
80 +(((
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" %)
85 +|(% 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" %)
92 +|(% class="highlight" %)(% class="highlight" %)
113 113  (((
114 114  Remarks
115 115  )))|(((
... ... @@ -116,20 +116,12 @@
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" %)
99 +|(% class="highlight" %)(% class="highlight" %)
120 120  (((
121 121  Implementations
122 122  )))|(((
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 -* {{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 -)))|(((
114 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
115 +(((
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" %)
122 +|(% 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" %)
130 +|(% class="highlight" %)(% class="highlight" %)
158 158  (((
159 159  Remarks
160 160  )))|(((
... ... @@ -162,26 +162,17 @@
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" %)
138 +|(% class="highlight" %)(% class="highlight" %)
166 166  (((
167 167  Implementations
168 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 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).
143 +
144 +{{code language="none"}}
145 +LinearSegmentsNodePlacer
146 +{{/code}}
147 +
148 +. 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.
185 185  )))
186 186  
187 187  == Phase 5: Edge Routing ==
... ... @@ -190,13 +190,14 @@
190 190  
191 191  |=(((
192 192  Preconditions
193 -)))|(((
157 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
158 +(((
194 194  * The graph has a proper layering. (except for self-loops)
195 195  * Nodes are assigned y coordinates.
196 196  * Layer heights are correctly set.
197 197  * An implementation may allow in-layer connections.
198 198  )))
199 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
164 +|(% class="highlight" %)(% class="highlight" %)
200 200  (((
201 201  Postconditions
202 202  )))|(((
... ... @@ -205,27 +205,18 @@
205 205  * The graph's width is set.
206 206  * The bend points of all edges are set.
207 207  )))
208 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
173 +|(% class="highlight" %)(% class="highlight" %)
209 209  (((
210 210  Remarks
211 211  )))|(((
212 212  None.
213 213  )))
214 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
179 +|(% class="highlight" %)(% class="highlight" %)
215 215  (((
216 216  Implementations
217 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.
183 +* {{code language="none"}}ComplexSplineRouter{{/code}}.
184 +* {{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.
185 +* {{code language="none"}}PolylineEdgeRouter{{/code}}.
186 +* {{code language="none"}}impleSplineEdgeRouter{{/code}}.
221 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 -7111017
1 +1998958
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/7111017/The Five Phases
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/1998958/The Five Phases