Skip to Content

Changes for page The Five Phases

Last modified by Alexander Schulz-Rosengarten on 2023/07/11 10:33
From version 10.1
edited by cds
on 2013/05/10 15:18
Change comment: There is no comment for this version
To version 7.1
edited by msp
on 2012/07/17 13:04
Change comment: There is no comment for this version

Summary

Details

Page properties
Author
... ... @@ -1,1 +1,1 @@
1 -XWiki.cds
1 +XWiki.msp
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  )))|(((
... ... @@ -44,23 +44,24 @@
44 44  
45 45  |=(((
46 46  Preconditions
47 -)))|(((
48 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
49 +(((
48 48  * The graph is cycle-free.
49 49  * The nodes have not been layered yet.
50 50  )))
51 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
53 +|(% class="highlight" %)(% class="highlight" %)
52 52  (((
53 53  Postconditions
54 54  )))|(((
55 55  * The graph has a layering.
56 56  )))
57 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
59 +|(% class="highlight" %)(% class="highlight" %)
58 58  (((
59 59  Remarks
60 60  )))|(((
61 61  * Implementations should usually include a dependency on the {{code language="none"}}LayerConstraintHandler{{/code}}, unless they already adhere to layer constraints themselves.
62 62  )))
63 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
65 +|(% class="highlight" %)(% class="highlight" %)
64 64  (((
65 65  Implementations
66 66  )))|(((
... ... @@ -80,12 +80,13 @@
80 80  
81 81  |=(((
82 82  Preconditions
83 -)))|(((
85 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
86 +(((
84 84  * The graph has a proper layering. (except for self-loops)
85 85  * An implementation may allow in-layer connections.
86 86  * Usually, all nodes are required to have a least fixed port sides.
87 87  )))
88 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
91 +|(% class="highlight" %)(% class="highlight" %)
89 89  (((
90 90  Postconditions
91 91  )))|(((
... ... @@ -92,7 +92,7 @@
92 92  * The order of nodes in each layer is fixed.
93 93  * All nodes have a fixed port order.
94 94  )))
95 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
98 +|(% class="highlight" %)(% class="highlight" %)
96 96  (((
97 97  Remarks
98 98  )))|(((
... ... @@ -99,12 +99,11 @@
99 99  * If fixed port sides are required, the {{code language="none"}}PortPositionProcessor{{/code}} may be of use.
100 100  * Support for in-layer connections may be required to be able to handle certain problems. (odd port sides, for instance)
101 101  )))
102 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
105 +|(% class="highlight" %)(% class="highlight" %)
103 103  (((
104 104  Implementations
105 105  )))|(((
106 106  * {{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.
107 -* {{code language="none"}}InteractiveCrossingMinimizer.{{/code}} Detects the order of nodes according to the current layout, hence it reacts to the user's placement.
108 108  )))
109 109  
110 110  == Phase 4: Node Placement ==
... ... @@ -115,7 +115,8 @@
115 115  
116 116  |=(((
117 117  Preconditions
118 -)))|(((
120 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
121 +(((
119 119  * The graph has a proper layering. (except for self-loops)
120 120  * Node orders are fixed.
121 121  * Port positions are fixed.
... ... @@ -122,7 +122,7 @@
122 122  * An implementation may allow in-layer connections.
123 123  * An implementation may require node margins to be set.
124 124  )))
125 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
128 +|(% class="highlight" %)(% class="highlight" %)
126 126  (((
127 127  Postconditions
128 128  )))|(((
... ... @@ -130,7 +130,7 @@
130 130  * The height of each layer is set.
131 131  * The height of the graph is set to the maximal layer height.
132 132  )))
133 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
136 +|(% class="highlight" %)(% class="highlight" %)
134 134  (((
135 135  Remarks
136 136  )))|(((
... ... @@ -138,7 +138,7 @@
138 138  * If node margins are supported, the {{code language="none"}}NodeMarginCalculator{{/code}} can compute them.
139 139  * Port positions can be fixed by using the {{code language="none"}}PortPositionProcessor{{/code}}.
140 140  )))
141 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
144 +|(% class="highlight" %)(% class="highlight" %)
142 142  (((
143 143  Implementations
144 144  )))|(((
... ... @@ -146,7 +146,7 @@
146 146  ** (((
147 147  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.
148 148  )))
149 -* {{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.\\
152 +* {{code language="none"}}BKNodePlacer.{{/code}} ??? Inspired by\\
150 150  ** (((
151 151  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.
152 152  )))
... ... @@ -158,13 +158,14 @@
158 158  
159 159  |=(((
160 160  Preconditions
161 -)))|(((
164 +)))|=(% class="nohighlight" %)(% class="nohighlight" %)
165 +(((
162 162  * The graph has a proper layering. (except for self-loops)
163 163  * Nodes are assigned y coordinates.
164 164  * Layer heights are correctly set.
165 165  * An implementation may allow in-layer connections.
166 166  )))
167 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
171 +|(% class="highlight" %)(% class="highlight" %)
168 168  (((
169 169  Postconditions
170 170  )))|(((
... ... @@ -173,13 +173,13 @@
173 173  * The graph's width is set.
174 174  * The bend points of all edges are set.
175 175  )))
176 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
180 +|(% class="highlight" %)(% class="highlight" %)
177 177  (((
178 178  Remarks
179 179  )))|(((
180 180  None.
181 181  )))
182 -|=(% class="highlight-grey" data-highlight-colour="grey" %)(% class="highlight-grey" data-highlight-colour="grey" %)
186 +|(% class="highlight" %)(% class="highlight" %)
183 183  (((
184 184  Implementations
185 185  )))|(((
Confluence.Code.ConfluencePageClass[0]
Id
... ... @@ -1,1 +1,1 @@
1 -7111008
1 +1998960
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/7111008/The Five Phases
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/1998960/The Five Phases