1 /** \file
2 * \brief Implements class PlanarDrawLayout
3 *
4 * \author Carsten Gutwenger
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32
33 #include <ogdf/planarlayout/PlanarDrawLayout.h>
34 #include <ogdf/basic/simple_graph_alg.h>
35 #include <ogdf/augmentation/PlanarAugmentation.h>
36 #include <ogdf/augmentation/PlanarAugmentationFix.h>
37 #include <ogdf/planarlayout/BiconnectedShellingOrder.h>
38 #include <ogdf/planarity/SimpleEmbedder.h>
39
40 namespace ogdf {
41
42
PlanarDrawLayout()43 PlanarDrawLayout::PlanarDrawLayout()
44 {
45 m_sizeOptimization = true;
46 m_sideOptimization = false;
47 m_baseRatio = 0.33;
48
49 m_augmenter.reset(new PlanarAugmentation);
50 m_computeOrder.reset(new BiconnectedShellingOrder);
51 m_embedder.reset(new SimpleEmbedder);
52 }
53
54
doCall(const Graph & G,adjEntry adjExternal,GridLayout & gridLayout,IPoint & boundingBox,bool fixEmbedding)55 void PlanarDrawLayout::doCall(
56 const Graph &G,
57 adjEntry adjExternal,
58 GridLayout &gridLayout,
59 IPoint &boundingBox,
60 bool fixEmbedding)
61 {
62 // require to have a planar graph without multi-edges and self-loops;
63 // planarity is checked below
64 OGDF_ASSERT(isSimple(G));
65
66 if (G.numberOfNodes() < 2) {
67 return;
68 }
69
70 // we make a copy of G since we use planar biconnected augmentation
71 GraphCopySimple GC(G);
72
73 if(fixEmbedding) {
74 PlanarAugmentationFix augmenter;
75 augmenter.call(GC);
76
77 } else {
78 // augment graph planar biconnected
79 m_augmenter->call(GC);
80
81 // embed augmented graph
82 m_embedder->call(GC,adjExternal);
83 }
84
85 // compute shelling order
86 m_computeOrder->baseRatio(m_baseRatio);
87
88 ShellingOrder order;
89 m_computeOrder->call(GC,order,adjExternal);
90
91 // compute grid coordinates for GC
92 NodeArray<int> x(GC), y(GC);
93 computeCoordinates(GC,order,x,y);
94
95 boundingBox.m_x = x[order(1,order.len(1))];
96 boundingBox.m_y = 0;
97 for(node v : GC.nodes)
98 if(y[v] > boundingBox.m_y) boundingBox.m_y = y[v];
99
100 // copy coordinates from GC to G
101 for(node v : G.nodes) {
102 node vCopy = GC.copy(v);
103 gridLayout.x(v) = x[vCopy];
104 gridLayout.y(v) = y[vCopy];
105 }
106 }
107
computeCoordinates(const Graph & G,ShellingOrder & order,NodeArray<int> & x,NodeArray<int> & y)108 void PlanarDrawLayout::computeCoordinates(const Graph &G,
109 ShellingOrder &order,
110 NodeArray<int> &x,
111 NodeArray<int> &y)
112 {
113 // let c_1,...,c_q be the the current contour, then
114 // next[c_i] = c_i+1, prev[c_i] = c_i-1
115 NodeArray<node> next(G), prev(G);
116
117 // upper[v] = w means x-coord. of v is relative to w
118 // (abs. x-coord. of v = x[v] + abs. x-coord of w)
119 NodeArray<node> upper(G,nullptr);
120
121 // maximal rank of a neighbour
122 NodeArray<int> maxNeighbour(G,0);
123 // internal nodes (nodes not on contour)
124 ArrayBuffer<node> internals(G.numberOfNodes());
125
126 for(node v : G.nodes)
127 {
128 for(adjEntry adj : v->adjEntries) {
129 int r = order.rank(adj->twinNode());
130 if (r > maxNeighbour[v])
131 maxNeighbour[v] = r;
132 }
133 }
134
135 // initialize contour with base
136 const ShellingOrderSet &V1 = order[1];
137 node v1 = V1[1];
138 node v2 = V1[V1.len()];
139 node rightSide = v2;
140
141 int i;
142 for (i = 1; i <= V1.len(); ++i)
143 {
144 y[V1[i]] = 0;
145 x[V1[i]] = (i == 1) ? 0 : 1;
146 if (i < V1.len())
147 next[V1[i]] = V1[i+1];
148 if (i > 1)
149 prev[V1[i]] = V1[i-1];
150 }
151 prev[v1] = next[v2] = nullptr;
152
153 // process shelling order from bottom to top
154 for (int k = 2; k <= order.length(); k++)
155 {
156 // Referenz auf aktuelle Menge Vk (als Abk?rzung)
157 const ShellingOrderSet &Vk = order[k]; // Vk = { z_1,...,z_l }
158 int len = Vk.len();
159
160 node z1 = Vk[1];
161 node cl = Vk.left(); // left vertex
162 node cr = Vk.right(); // right vertex
163
164 bool isOuter;
165 if (m_sideOptimization && cr == rightSide && maxNeighbour[cr] <= k)
166 {
167 isOuter = true;
168 rightSide = Vk[len];
169 } else
170 isOuter = false;
171
172 // compute relative x-distance from c_i to cl for i = len+1, ..., r
173 int sum = 0;
174 for (node v = next[cl]; v != cr; v = next[v]) {
175 sum += x[v];
176 x[v] = sum;
177 }
178 x[cr] += sum;
179
180 int eps = (maxNeighbour [cl] <= k && k > 2) ? 0 : 1;
181
182 int x_cr, y_z;
183 if (m_sizeOptimization)
184 {
185 int yMax;
186 if (isOuter)
187 {
188 yMax = max(y[cl]+1-eps,
189 y[cr] + ((x[cr] == 1 && eps == 1) ? 1 : 0));
190 for (node v = next[cl]; v != cr; v = next[v]) {
191 if (x[v] < x[cr]) {
192 int y1 = (y[cr]-y[v])*(eps-x[cr])/(x[cr]-x[v])+y[cr];
193 if (y1 >= yMax)
194 yMax = 1+y1;
195 }
196 }
197 for (node v = cr; v != cl; v = prev[v]) {
198 if (y[prev[v]] > y[v] && maxNeighbour[v] >= k) {
199 if (yMax <= y[v] + x[v] - eps) {
200 eps = 1;
201 yMax = y[v] + x[v];
202 }
203 break;
204 }
205 }
206 x_cr = max(x[cr]-eps-len+1, (y[cr] == yMax) ? 1 : 0);
207 y_z = yMax;
208
209 } else {
210 // yMax = max { y[c_i] | len <= i <= r }
211 yMax = y[cl] - eps;
212 for (node v = cr; v != cl; v = prev[v]) {
213 if (y[v] > yMax)
214 yMax = y[v];
215 }
216 int offset = max (yMax-x[cr]+len+eps-y[cr],
217 (y[prev[cr]] > y[cr]) ? 1 : 0);
218 y_z = y[cr] + x[cr] + offset - len + 1 - eps;
219 x_cr = y_z - y[cr];
220 }
221
222 } else {
223 y_z = y[cr] + x[cr] + 1 - eps;
224 x_cr = y_z - y[cr];
225 }
226
227 node alpha = cl;
228 for (node v = next[cl];
229 maxNeighbour[v] <= k-1 && order.rank(v) <= order.rank(prev[v]);
230 v = next[v])
231 {
232 if (order.rank (v) < order.rank (alpha))
233 alpha = v;
234 if (v == cr)
235 break;
236 }
237
238 node beta = prev[cr];
239 for (node v = prev[cr];
240 maxNeighbour[v] <= k-1 && order.rank(v) <= order.rank(next[v]);
241 v = prev[v])
242 {
243 if (order.rank (v) <= order.rank (beta))
244 beta = v;
245 if (v == cl)
246 break;
247 }
248
249 for (i = 1; i <= len; ++i) {
250 x[Vk[i]] = 1;
251 y[Vk[i]] = y_z;
252 }
253 x[z1] = eps;
254
255 for (node v = alpha; v != cl; v = prev [v]) {
256 upper[v] = cl;
257 internals.push (v);
258 }
259 for (node v = next [beta]; v != cr; v = next [v]) {
260 upper[v] = cr;
261 x [v] -= x[cr];
262 internals.push (v);
263 }
264 for (node v = beta; v != alpha; v = prev[v]) {
265 upper[v] = z1;
266 x [v] -= x[z1];
267 internals.push (v);
268 }
269
270 x[cr] = x_cr;
271
272 // update contour after insertion of z_1,...,z_l
273 for (i = 1; i <= len; i++) {
274 if (i < len)
275 next[Vk[i]] = Vk[i+1];
276 if (i > 1)
277 prev[Vk[i]] = Vk[i-1];
278 }
279 next [cl] = z1;
280 next [Vk[len]] = cr;
281 prev [cr] = Vk[len];
282 prev [z1] = cl;
283 }
284
285 // compute final x-coordinates for the nodes on the (final) contour
286 int sum = 0;
287 for (node v = v1; v != nullptr; v = next[v])
288 x [v] = (sum += x[v]);
289
290 // compute final x-coordinates for the internal nodes
291 while (!internals.empty()) {
292 node v = internals.popRet();
293 x[v] += x[upper[v]];
294 }
295 }
296
297 }
298