1 /** \file
2 * \brief Implementation of the Booth-Lueker planarity test.
3 *
4 * Implements planarity test and planar embedding algorithm.
5 *
6 * \author Sebastian Leipert
7 *
8 * \par License:
9 * This file is part of the Open Graph Drawing Framework (OGDF).
10 *
11 * \par
12 * Copyright (C)<br>
13 * See README.md in the OGDF root directory for details.
14 *
15 * \par
16 * This program is free software; you can redistribute it and/or
17 * modify it under the terms of the GNU General Public License
18 * Version 2 or 3 as published by the Free Software Foundation;
19 * see the file LICENSE.txt included in the packaging of this file
20 * for details.
21 *
22 * \par
23 * This program is distributed in the hope that it will be useful,
24 * but WITHOUT ANY WARRANTY; without even the implied warranty of
25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 * GNU General Public License for more details.
27 *
28 * \par
29 * You should have received a copy of the GNU General Public
30 * License along with this program; if not, see
31 * http://www.gnu.org/copyleft/gpl.html
32 */
33
34
35 #include <ogdf/basic/basic.h>
36 #include <ogdf/basic/Array.h>
37 #include <ogdf/basic/NodeArray.h>
38 #include <ogdf/basic/SList.h>
39 #include <ogdf/basic/simple_graph_alg.h>
40 #include <ogdf/basic/STNumbering.h>
41 #include <ogdf/planarity/booth_lueker/PlanarPQTree.h>
42 #include <ogdf/planarity/BoothLueker.h>
43 #include <ogdf/planarity/booth_lueker/EmbedPQTree.h>
44
45 namespace ogdf{
46
47 using namespace booth_lueker;
48
isPlanarDestructive(Graph & G)49 bool BoothLueker::isPlanarDestructive(Graph &G)
50 {
51 bool ret = preparation(G,false);
52 m_parallelEdges.init();
53 m_isParallel.init();
54
55 return ret;
56 }
57
isPlanar(const Graph & G)58 bool BoothLueker::isPlanar(const Graph &G)
59 {
60 Graph Gp(G);
61 bool ret = preparation(Gp,false);
62 m_parallelEdges.init();
63 m_isParallel.init();
64
65 return ret;
66 }
67
68 // Prepares the planarity test and the planar embedding
69 // Parallel edges: do not need to be ignored, they can be handled
70 // by the planarity test.
71 // Selfloops: need to be ignored.
preparation(Graph & G,bool embed)72 bool BoothLueker::preparation(Graph &G, bool embed)
73 {
74 if (G.numberOfEdges() < 9 && !embed)
75 return true;
76 else if (G.numberOfEdges() < 3 && embed)
77 return true;
78
79 SListPure<node> selfLoops;
80 makeLoopFree(G,selfLoops);
81
82 prepareParallelEdges(G);
83
84 int isolated = 0;
85 for(node v : G.nodes)
86 if (v->degree() == 0)
87 isolated++;
88
89 if (((G.numberOfNodes()-isolated) > 2) &&
90 ((3*(G.numberOfNodes()-isolated) -6) < (G.numberOfEdges() - m_parallelCount)))
91 return false;
92
93 bool planar = true;
94
95 NodeArray<node> tableNodes(G,nullptr);
96 EdgeArray<edge> tableEdges(G,nullptr);
97 NodeArray<bool> mark(G,0);
98
99 EdgeArray<int> componentID(G);
100
101 // Determine Biconnected Components
102 int bcCount = biconnectedComponents(G,componentID);
103
104 // Determine edges per biconnected component
105 Array<SList<edge> > blockEdges(0,bcCount-1);
106 for(edge e : G.edges)
107 {
108 blockEdges[componentID[e]].pushFront(e);
109 }
110
111 // Determine nodes per biconnected component.
112 Array<SList<node> > blockNodes(0,bcCount-1);
113 int i;
114 for (i = 0; i < bcCount; i++)
115 {
116 for (edge e : blockEdges[i])
117 {
118 if (!mark[e->source()])
119 {
120 blockNodes[i].pushBack(e->source());
121 mark[e->source()] = true;
122 }
123 if (!mark[e->target()])
124 {
125 blockNodes[i].pushBack(e->target());
126 mark[e->target()] = true;
127 }
128 }
129
130 for (node v : blockNodes[i])
131 mark[v] = false;
132 }
133
134 // Perform Planarity Test for every biconnected component
135
136 if (bcCount == 1)
137 {
138 if (G.numberOfEdges() >= 2)
139 {
140 // Compute st-numbering
141 NodeArray<int> numbering(G,0);
142 #ifdef OGDF_HEAVY_DEBUG
143 int n =
144 #endif
145 computeSTNumbering(G, numbering);
146 OGDF_HEAVY_ASSERT(isSTNumbering(G, numbering, n));
147
148 EdgeArray<edge> backTableEdges(G,nullptr);
149 for(edge e : G.edges)
150 backTableEdges[e] = e;
151
152 if (embed)
153 planar = doEmbed(G,numbering,backTableEdges,backTableEdges);
154 else
155 planar = doTest(G,numbering);
156 }
157 }
158 else
159 {
160 NodeArray<SListPure<adjEntry> > entireEmbedding(G);
161 for (i = 0; i < bcCount; i++)
162 {
163 Graph C;
164
165 for (node v : blockNodes[i])
166 {
167 node w = C.newNode();
168 tableNodes[v] = w;
169 }
170
171 NodeArray<node> backTableNodes(C,nullptr);
172 if (embed)
173 {
174 for (node v : blockNodes[i])
175 backTableNodes[tableNodes[v]] = v;
176 }
177
178 for (edge e : blockEdges[i])
179 {
180 edge f = C.newEdge(tableNodes[e->source()],tableNodes[e->target()]);
181 tableEdges[e] = f;
182 }
183
184 EdgeArray<edge> backTableEdges(C,nullptr);
185 for (edge e : blockEdges[i])
186 backTableEdges[tableEdges[e]] = e;
187
188 if (C.numberOfEdges() >= 2)
189 {
190 // Compute st-numbering
191 NodeArray<int> numbering(C,0);
192 #ifdef OGDF_HEAVY_DEBUG
193 int n =
194 #endif
195 computeSTNumbering(C, numbering);
196 OGDF_HEAVY_ASSERT(isSTNumbering(C, numbering, n));
197
198 if (embed)
199 planar = doEmbed(C,numbering,backTableEdges,tableEdges);
200 else
201 planar = doTest(C,numbering);
202
203 if (!planar)
204 break;
205 }
206
207 if (embed)
208 {
209 for(node v : C.nodes)
210 {
211 node w = backTableNodes[v];
212 for(adjEntry a : v->adjEntries)
213 {
214 edge e = backTableEdges[a->theEdge()];
215 adjEntry adj = (e->adjSource()->theNode() == w)?
216 e->adjSource() : e->adjTarget();
217 entireEmbedding[w].pushBack(adj);
218 }
219 }
220 }
221 }
222
223 if (planar && embed)
224 {
225 for(node v : G.nodes)
226 G.sort(v,entireEmbedding[v]);
227 }
228
229 }
230
231 while (!selfLoops.empty())
232 {
233 node v = selfLoops.popFrontRet();
234 G.newEdge(v,v);
235 }
236
237 OGDF_HEAVY_ASSERT(!planar || !embed || G.representsCombEmbedding());
238
239 return planar;
240 }
241
242
243 // Performs a planarity test on a biconnected component
244 // of G. numbering contains an st-numbering of the component.
doTest(Graph & G,NodeArray<int> & numbering)245 bool BoothLueker::doTest(Graph &G,NodeArray<int> &numbering)
246 {
247 bool planar = true;
248
249 NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > inLeaves(G);
250 NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > outLeaves(G);
251 Array<node> table(G.numberOfNodes()+1);
252
253 for(node v : G.nodes)
254 {
255 for(adjEntry adj : v->adjEntries) {
256 edge e = adj->theEdge();
257 if (numbering[e->opposite(v)] > numbering[v])
258 //sideeffect: loops are ignored
259 {
260 PlanarLeafKey<IndInfo*>* L = new PlanarLeafKey<IndInfo*>(e);
261 inLeaves[v].pushFront(L);
262 }
263 }
264 table[numbering[v]] = v;
265 }
266
267 for(node v : G.nodes)
268 {
269 for (PlanarLeafKey<IndInfo*>* L : inLeaves[v])
270 {
271 outLeaves[L->userStructKey()->opposite(v)].pushFront(L);
272 }
273 }
274
275 PlanarPQTree T;
276
277 T.Initialize(inLeaves[table[1]]);
278 for (int i = 2; i < G.numberOfNodes(); i++)
279 {
280 if (T.Reduction(outLeaves[table[i]]))
281 {
282 T.ReplaceRoot(inLeaves[table[i]]);
283 T.emptyAllPertinentNodes();
284
285 }
286 else
287 {
288 planar = false;
289 break;
290 }
291 }
292 if (planar)
293 T.emptyAllPertinentNodes();
294
295
296 // Cleanup
297 for(node v : G.nodes)
298 {
299 while (!inLeaves[v].empty())
300 {
301 PlanarLeafKey<IndInfo*>* L = inLeaves[v].popFrontRet();
302 delete L;
303 }
304 }
305
306 return planar;
307 }
308
309
310 // Performs a planarity test on a biconnected component
311 // of G and embedds it planar.
312 // numbering contains an st-numbering of the component.
doEmbed(Graph & G,NodeArray<int> & numbering,EdgeArray<edge> & backTableEdges,EdgeArray<edge> & forwardTableEdges)313 bool BoothLueker::doEmbed(
314 Graph &G,
315 NodeArray<int> &numbering,
316 EdgeArray<edge> &backTableEdges,
317 EdgeArray<edge> &forwardTableEdges)
318 {
319
320 NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > inLeaves(G);
321 NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > outLeaves(G);
322 NodeArray<SListPure<edge> > frontier(G);
323 NodeArray<SListPure<node> > opposed(G);
324 NodeArray<SListPure<node> > nonOpposed(G);
325 Array<node> table(G.numberOfNodes()+1);
326 Array<bool> toReverse(1,G.numberOfNodes()+1,false);
327
328 for(node v : G.nodes)
329 {
330 for(adjEntry adj : v->adjEntries) {
331 edge e = adj->theEdge();
332 if (numbering[e->opposite(v)] > numbering[v])
333 {
334 PlanarLeafKey<IndInfo*>* L = new PlanarLeafKey<IndInfo*>(e);
335 inLeaves[v].pushFront(L);
336 }
337 }
338 table[numbering[v]] = v;
339 }
340
341 for(node v : G.nodes)
342 {
343 for (PlanarLeafKey<IndInfo*>* L : inLeaves[v])
344 {
345 outLeaves[L->userStructKey()->opposite(v)].pushFront(L);
346 }
347 }
348
349 booth_lueker::EmbedPQTree T;
350
351 T.Initialize(inLeaves[table[1]]);
352 int i;
353 for (i = 2; i <= G.numberOfNodes(); i++)
354 {
355 if (T.Reduction(outLeaves[table[i]]))
356 {
357 T.ReplaceRoot(inLeaves[table[i]], frontier[table[i]], opposed[table[i]], nonOpposed[table[i]], table[i]);
358 T.emptyAllPertinentNodes();
359 }
360 else
361 {
362 // Cleanup
363 for(node v : G.nodes)
364 {
365 while (!inLeaves[v].empty())
366 {
367 PlanarLeafKey<IndInfo*>* L = inLeaves[v].popFrontRet();
368 delete L;
369 }
370 }
371 return false;
372 }
373 }
374
375 // Reverse adjacency lists if necessary
376 // This gives an upward embedding
377 for (i = G.numberOfNodes(); i >= 2; i--)
378 {
379 if (toReverse[i])
380 {
381 while (!nonOpposed[table[i]].empty())
382 {
383 node v = nonOpposed[table[i]].popFrontRet();
384 toReverse[numbering[v]] = true;
385 }
386 frontier[table[i]].reverse();
387 }
388 else
389 {
390 while (!opposed[table[i]].empty())
391 {
392 node v = opposed[table[i]].popFrontRet();
393 toReverse[numbering[v]] = true;
394 }
395 }
396 nonOpposed[table[i]].clear();
397 opposed[table[i]].clear();
398 }
399
400 // Compute the entire embedding
401 NodeArray<SListPure<adjEntry> > entireEmbedding(G);
402 for(node v : G.nodes)
403 {
404 while (!frontier[v].empty())
405 {
406 edge e = frontier[v].popFrontRet();
407 entireEmbedding[v].pushBack(
408 (e->adjSource()->theNode() == v)? e->adjSource() : e->adjTarget());
409 }
410 }
411
412 NodeArray<bool> mark(G,false);
413 NodeArray<SListIterator<adjEntry> > adjMarker(G,nullptr);
414 for(node v : G.nodes)
415 adjMarker[v] = entireEmbedding[v].begin();
416
417 entireEmbed(G, entireEmbedding, adjMarker, mark, table[G.numberOfNodes()]);
418
419 NodeArray<SListPure<adjEntry> > newEntireEmbedding(G);
420 if (m_parallelCount > 0)
421 {
422 for(node v : G.nodes)
423 {
424 for(adjEntry a : entireEmbedding[v])
425 {
426 edge e = a->theEdge(); // edge in biconnected component
427 edge trans = backTableEdges[e]; // edge in original graph.
428 if (!m_parallelEdges[trans].empty())
429 {
430 // This original edge is the reference edge
431 // of a bundle of parallel edges
432
433 // If v is source of e, insert the parallel edges
434 // in the order stored in the list.
435 if (e->adjSource()->theNode() == v)
436 {
437 adjEntry adj = e->adjSource();
438 newEntireEmbedding[v].pushBack(adj);
439 for (edge ei : m_parallelEdges[trans])
440 {
441 edge parallel = forwardTableEdges[ei];
442 adjEntry adjParallel = parallel->adjSource()->theNode() == v ?
443 parallel->adjSource() : parallel->adjTarget();
444 newEntireEmbedding[v].pushBack(adjParallel);
445 }
446 }
447 else
448 // v is target of e, insert the parallel edges
449 // in the opposite order stored in the list.
450 // This keeps the embedding.
451 {
452 for (edge parEdge : reverse(m_parallelEdges[trans])) {
453 edge parallel = forwardTableEdges[parEdge];
454 adjEntry adj = parallel->adjSource()->theNode() == v ?
455 parallel->adjSource() : parallel->adjTarget();
456 newEntireEmbedding[v].pushBack(adj);
457 }
458 adjEntry adj = e->adjTarget();
459 newEntireEmbedding[v].pushBack(adj);
460 }
461 }
462 else if (!m_isParallel[trans])
463 // normal non-multi-edge
464 {
465 adjEntry adj = e->adjSource()->theNode() == v?
466 e->adjSource() : e->adjTarget();
467 newEntireEmbedding[v].pushBack(adj);
468 }
469 // else e is a multi-edge but not the reference edge
470 }
471 }
472
473 for(node v : G.nodes)
474 G.sort(v,newEntireEmbedding[v]);
475 }
476 else
477 {
478 for(node v : G.nodes)
479 G.sort(v,entireEmbedding[v]);
480 }
481
482
483 //cleanup
484 for(node v : G.nodes)
485 {
486 while (!inLeaves[v].empty())
487 {
488 PlanarLeafKey<IndInfo*>* L = inLeaves[v].popFrontRet();
489 delete L;
490 }
491 }
492
493 return true;
494 }
495
496 // Used by doEmbed. Computes an entire embedding from an
497 // upward embedding.
entireEmbed(Graph & G,NodeArray<SListPure<adjEntry>> & entireEmbedding,NodeArray<SListIterator<adjEntry>> & adjMarker,NodeArray<bool> & mark,node v)498 void BoothLueker::entireEmbed(
499 Graph &G,
500 NodeArray<SListPure<adjEntry> > &entireEmbedding,
501 NodeArray<SListIterator<adjEntry> > &adjMarker,
502 NodeArray<bool> &mark,
503 node v)
504 {
505 mark[v] = true;
506 SListIterator<adjEntry> it;
507 for (it = adjMarker[v]; it.valid(); ++it)
508 {
509 adjEntry a = *it;
510 edge e = a->theEdge();
511 adjEntry adj = (e->adjSource()->theNode() == v)?
512 e->adjTarget() : e->adjSource();
513 node w = adj->theNode();
514 entireEmbedding[w].pushFront(adj);
515 if (!mark[w])
516 entireEmbed(G,entireEmbedding,adjMarker,mark,w);
517 }
518 }
519
prepareParallelEdges(Graph & G)520 void BoothLueker::prepareParallelEdges(Graph &G)
521 {
522 // Stores for one reference edge all parallel edges.
523 m_parallelEdges.init(G);
524 // Is true for any multiedge, except for the reference edge.
525 m_isParallel.init(G,false);
526 getParallelFreeUndirected(G,m_parallelEdges);
527 m_parallelCount = 0;
528 for(edge e : G.edges)
529 {
530 if (!m_parallelEdges[e].empty())
531 {
532 for (edge ei : m_parallelEdges[e])
533 {
534 m_isParallel[ei] = true;
535 m_parallelCount++;
536 }
537 }
538 }
539 }
540
541
542 }
543