6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
10 * \brief Implementation of the Booth-Lueker planarity test.
12 * Implements planarity test and planar embedding algorithm.
14 * \author Sebastian Leipert
17 * This file is part of the Open Graph Drawing Framework (OGDF).
21 * See README.txt in the root directory of the OGDF installation for details.
24 * This program is free software; you can redistribute it and/or
25 * modify it under the terms of the GNU General Public License
26 * Version 2 or 3 as published by the Free Software Foundation;
27 * see the file LICENSE.txt included in the packaging of this file
31 * This program is distributed in the hope that it will be useful,
32 * but WITHOUT ANY WARRANTY; without even the implied warranty of
33 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
34 * GNU General Public License for more details.
37 * You should have received a copy of the GNU General Public
38 * License along with this program; if not, write to the Free
39 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
40 * Boston, MA 02110-1301, USA.
42 * \see http://www.gnu.org/copyleft/gpl.html
43 ***************************************************************/
46 #include <ogdf/basic/basic.h>
47 #include <ogdf/basic/Array.h>
48 #include <ogdf/basic/NodeArray.h>
49 #include <ogdf/basic/SList.h>
50 #include <ogdf/basic/simple_graph_alg.h>
51 #include <ogdf/basic/extended_graph_alg.h>
52 #include <ogdf/internal/planarity/PlanarPQTree.h>
53 #include <ogdf/internal/planarity/PlanarLeafKey.h>
54 #include <ogdf/planarity/BoothLueker.h>
55 #include <ogdf/internal/planarity/EmbedPQTree.h>
60 bool BoothLueker::isPlanarDestructive(Graph
&G
)
62 bool ret
= preparation(G
,false);
63 m_parallelEdges
.init();
69 bool BoothLueker::isPlanar(const Graph
&G
)
72 bool ret
= preparation(Gp
,false);
73 m_parallelEdges
.init();
79 // Prepares the planarity test and the planar embedding
80 // Parallel edges: do not need to be ignored, they can be handled
81 // by the planarity test.
82 // Selfloops: need to be ignored.
83 bool BoothLueker::preparation(Graph
&G
, bool embed
)
85 if (G
.numberOfEdges() < 9 && !embed
)
87 else if (G
.numberOfEdges() < 3 && embed
)
93 SListPure
<node
> selfLoops
;
94 makeLoopFree(G
,selfLoops
);
96 prepareParallelEdges(G
);
100 if (v
->degree() == 0)
103 if (((G
.numberOfNodes()-isolated
) > 2) &&
104 ((3*(G
.numberOfNodes()-isolated
) -6) < (G
.numberOfEdges() - m_parallelCount
)))
109 NodeArray
<node
> tableNodes(G
,0);
110 EdgeArray
<edge
> tableEdges(G
,0);
111 NodeArray
<bool> mark(G
,0);
113 EdgeArray
<int> componentID(G
);
115 // Determine Biconnected Components
116 int bcCount
= biconnectedComponents(G
,componentID
);
118 // Determine edges per biconnected component
119 Array
<SList
<edge
> > blockEdges(0,bcCount
-1);
122 blockEdges
[componentID
[e
]].pushFront(e
);
125 // Determine nodes per biconnected component.
126 Array
<SList
<node
> > blockNodes(0,bcCount
-1);
128 for (i
= 0; i
< bcCount
; i
++)
130 SListIterator
<edge
> it
;
131 for (it
= blockEdges
[i
].begin(); it
.valid(); ++it
)
134 if (!mark
[e
->source()])
136 blockNodes
[i
].pushBack(e
->source());
137 mark
[e
->source()] = true;
139 if (!mark
[e
->target()])
141 blockNodes
[i
].pushBack(e
->target());
142 mark
[e
->target()] = true;
145 SListIterator
<node
> itn
;
146 for (itn
= blockNodes
[i
].begin(); itn
.valid(); ++itn
)
150 // Perform Planarity Test for every biconnected component
154 if (G
.numberOfEdges() >= 2)
156 // Compute st-numbering
157 NodeArray
<int> numbering(G
,0);
161 stNumber(G
,numbering
);
162 OGDF_ASSERT_IF(dlConsistencyChecks
,testSTnumber(G
,numbering
,n
))
164 EdgeArray
<edge
> backTableEdges(G
,0);
166 backTableEdges
[e
] = e
;
169 planar
= doEmbed(G
,numbering
,backTableEdges
,backTableEdges
);
171 planar
= doTest(G
,numbering
);
176 NodeArray
<SListPure
<adjEntry
> > entireEmbedding(G
);
177 for (i
= 0; i
< bcCount
; i
++)
181 SListIterator
<node
> itn
;
182 for (itn
= blockNodes
[i
].begin(); itn
.valid(); ++ itn
)
185 node w
= C
.newNode();
189 NodeArray
<node
> backTableNodes(C
,0);
192 for (itn
= blockNodes
[i
].begin(); itn
.valid(); ++ itn
)
193 backTableNodes
[tableNodes
[*itn
]] = *itn
;
196 SListIterator
<edge
> it
;
197 for (it
= blockEdges
[i
].begin(); it
.valid(); ++it
)
200 edge f
= C
.newEdge(tableNodes
[e
->source()],tableNodes
[e
->target()]);
204 EdgeArray
<edge
> backTableEdges(C
,0);
205 for (it
= blockEdges
[i
].begin(); it
.valid(); ++it
)
206 backTableEdges
[tableEdges
[*it
]] = *it
;
208 if (C
.numberOfEdges() >= 2)
210 // Compute st-numbering
211 NodeArray
<int> numbering(C
,0);
215 stNumber(C
,numbering
);
216 OGDF_ASSERT_IF(dlConsistencyChecks
,testSTnumber(C
,numbering
,n
))
219 planar
= doEmbed(C
,numbering
,backTableEdges
,tableEdges
);
221 planar
= doTest(C
,numbering
);
231 node w
= backTableNodes
[v
];
235 edge e
= backTableEdges
[a
->theEdge()];
236 adjEntry adj
= (e
->adjSource()->theNode() == w
)?
237 e
->adjSource() : e
->adjTarget();
238 entireEmbedding
[w
].pushBack(adj
);
247 G
.sort(v
,entireEmbedding
[v
]);
252 while (!selfLoops
.empty())
254 v
= selfLoops
.popFrontRet();
258 OGDF_ASSERT_IF(dlConsistencyChecks
,
259 planar
== false || embed
== false || G
.representsCombEmbedding())
265 // Performs a planarity test on a biconnected component
266 // of G. numbering contains an st-numbering of the component.
267 bool BoothLueker::doTest(Graph
&G
,NodeArray
<int> &numbering
)
271 NodeArray
<SListPure
<PlanarLeafKey
<IndInfo
*>* > > inLeaves(G
);
272 NodeArray
<SListPure
<PlanarLeafKey
<IndInfo
*>* > > outLeaves(G
);
273 Array
<node
> table(G
.numberOfNodes()+1);
279 forall_adj_edges(e
,v
)
281 if (numbering
[e
->opposite(v
)] > numbering
[v
])
282 //sideeffect: loops are ignored
284 PlanarLeafKey
<IndInfo
*>* L
= OGDF_NEW PlanarLeafKey
<IndInfo
*>(e
);
285 inLeaves
[v
].pushFront(L
);
288 table
[numbering
[v
]] = v
;
293 SListIterator
<PlanarLeafKey
<IndInfo
*>* > it
;
294 for (it
= inLeaves
[v
].begin(); it
.valid(); ++it
)
296 PlanarLeafKey
<IndInfo
*>* L
= *it
;
297 outLeaves
[L
->userStructKey()->opposite(v
)].pushFront(L
);
303 T
.Initialize(inLeaves
[table
[1]]);
304 for (int i
= 2; i
< G
.numberOfNodes(); i
++)
306 if (T
.Reduction(outLeaves
[table
[i
]]))
308 T
.ReplaceRoot(inLeaves
[table
[i
]]);
309 T
.emptyAllPertinentNodes();
319 T
.emptyAllPertinentNodes();
325 while (!inLeaves
[v
].empty())
327 PlanarLeafKey
<IndInfo
*>* L
= inLeaves
[v
].popFrontRet();
336 // Performs a planarity test on a biconnected component
337 // of G and embedds it planar.
338 // numbering contains an st-numbering of the component.
339 bool BoothLueker::doEmbed(
341 NodeArray
<int> &numbering
,
342 EdgeArray
<edge
> &backTableEdges
,
343 EdgeArray
<edge
> &forwardTableEdges
)
346 NodeArray
<SListPure
<PlanarLeafKey
<IndInfo
*>* > > inLeaves(G
);
347 NodeArray
<SListPure
<PlanarLeafKey
<IndInfo
*>* > > outLeaves(G
);
348 NodeArray
<SListPure
<edge
> > frontier(G
);
349 NodeArray
<SListPure
<node
> > opposed(G
);
350 NodeArray
<SListPure
<node
> > nonOpposed(G
);
351 Array
<node
> table(G
.numberOfNodes()+1);
352 Array
<bool> toReverse(1,G
.numberOfNodes()+1,false);
359 forall_adj_edges(e
,v
)
361 if (numbering
[e
->opposite(v
)] > numbering
[v
])
363 PlanarLeafKey
<IndInfo
*>* L
= OGDF_NEW PlanarLeafKey
<IndInfo
*>(e
);
364 inLeaves
[v
].pushFront(L
);
367 table
[numbering
[v
]] = v
;
372 SListIterator
<PlanarLeafKey
<IndInfo
*>* > it
;
373 for (it
= inLeaves
[v
].begin(); it
.valid(); ++it
)
375 PlanarLeafKey
<IndInfo
*>* L
= *it
;
376 outLeaves
[L
->userStructKey()->opposite(v
)].pushFront(L
);
382 T
.Initialize(inLeaves
[table
[1]]);
384 for (i
= 2; i
<= G
.numberOfNodes(); i
++)
386 if (T
.Reduction(outLeaves
[table
[i
]]))
388 T
.ReplaceRoot(inLeaves
[table
[i
]], frontier
[table
[i
]], opposed
[table
[i
]], nonOpposed
[table
[i
]], table
[i
]);
389 T
.emptyAllPertinentNodes();
396 while (!inLeaves
[v
].empty())
398 PlanarLeafKey
<IndInfo
*>* L
= inLeaves
[v
].popFrontRet();
406 // Reverse adjacency lists if necessary
407 // This gives an upward embedding
408 for (i
= G
.numberOfNodes(); i
>= 2; i
--)
412 while (!nonOpposed
[table
[i
]].empty())
414 v
= nonOpposed
[table
[i
]].popFrontRet();
415 toReverse
[numbering
[v
]] = true;
417 frontier
[table
[i
]].reverse();
421 while (!opposed
[table
[i
]].empty())
423 v
= opposed
[table
[i
]].popFrontRet();
424 toReverse
[numbering
[v
]] = true;
427 nonOpposed
[table
[i
]].clear();
428 opposed
[table
[i
]].clear();
431 // Compute the entire embedding
432 NodeArray
<SListPure
<adjEntry
> > entireEmbedding(G
);
435 while (!frontier
[v
].empty())
437 edge e
= frontier
[v
].popFrontRet();
438 entireEmbedding
[v
].pushBack(
439 (e
->adjSource()->theNode() == v
)? e
->adjSource() : e
->adjTarget());
443 NodeArray
<bool> mark(G
,false);
444 NodeArray
<SListIterator
<adjEntry
> > adjMarker(G
,0);
446 adjMarker
[v
] = entireEmbedding
[v
].begin();
447 v
= table
[G
.numberOfNodes()];
448 entireEmbed(G
,entireEmbedding
,adjMarker
,mark
,v
);
450 NodeArray
<SListPure
<adjEntry
> > newEntireEmbedding(G
);
451 if (m_parallelCount
> 0)
456 SListIterator
<adjEntry
> it
;
457 for(it
=entireEmbedding
[v
].begin();it
.valid();it
++)
459 edge e
= (*it
)->theEdge(); // edge in biconnected component
460 edge trans
= backTableEdges
[e
]; // edge in original graph.
461 if (!m_parallelEdges
[trans
].empty())
463 // This original edge is the reference edge
464 // of a bundle of parallel edges
466 ListIterator
<edge
> it
;
467 // If v is source of e, insert the parallel edges
468 // in the order stored in the list.
469 if (e
->adjSource()->theNode() == v
)
471 adjEntry adj
= e
->adjSource();
472 newEntireEmbedding
[v
].pushBack(adj
);
473 for (it
= m_parallelEdges
[trans
].begin(); it
.valid(); it
++)
475 edge parallel
= forwardTableEdges
[*it
];
476 adjEntry adj
= parallel
->adjSource()->theNode() == v
?
477 parallel
->adjSource() : parallel
->adjTarget();
478 newEntireEmbedding
[v
].pushBack(adj
);
482 // v is target of e, insert the parallel edges
483 // in the opposite order stored in the list.
484 // This keeps the embedding.
486 for (it
= m_parallelEdges
[trans
].rbegin(); it
.valid(); it
--)
488 edge parallel
= forwardTableEdges
[*it
];
489 adjEntry adj
= parallel
->adjSource()->theNode() == v
?
490 parallel
->adjSource() : parallel
->adjTarget();
491 newEntireEmbedding
[v
].pushBack(adj
);
493 adjEntry adj
= e
->adjTarget();
494 newEntireEmbedding
[v
].pushBack(adj
);
497 else if (!m_isParallel
[trans
])
498 // normal non-multi-edge
500 adjEntry adj
= e
->adjSource()->theNode() == v
?
501 e
->adjSource() : e
->adjTarget();
502 newEntireEmbedding
[v
].pushBack(adj
);
504 // else e is a multi-edge but not the reference edge
509 G
.sort(v
,newEntireEmbedding
[v
]);
514 G
.sort(v
,entireEmbedding
[v
]);
521 while (!inLeaves
[v
].empty())
523 PlanarLeafKey
<IndInfo
*>* L
= inLeaves
[v
].popFrontRet();
531 // Used by doEmbed. Computes an entire embedding from an
533 void BoothLueker::entireEmbed(
535 NodeArray
<SListPure
<adjEntry
> > &entireEmbedding
,
536 NodeArray
<SListIterator
<adjEntry
> > &adjMarker
,
537 NodeArray
<bool> &mark
,
541 SListIterator
<adjEntry
> it
;
542 for (it
= adjMarker
[v
]; it
.valid(); ++it
)
545 edge e
= a
->theEdge();
546 adjEntry adj
= (e
->adjSource()->theNode() == v
)?
547 e
->adjTarget() : e
->adjSource();
548 node w
= adj
->theNode();
549 entireEmbedding
[w
].pushFront(adj
);
551 entireEmbed(G
,entireEmbedding
,adjMarker
,mark
,w
);
557 void BoothLueker::prepareParallelEdges(Graph
&G
)
561 // Stores for one reference edge all parallel edges.
562 m_parallelEdges
.init(G
);
563 // Is true for any multiedge, except for the reference edge.
564 m_isParallel
.init(G
,false);
565 getParallelFreeUndirected(G
,m_parallelEdges
);
569 if (!m_parallelEdges
[e
].empty())
571 ListIterator
<edge
> it
;
572 for (it
= m_parallelEdges
[e
].begin(); it
.valid(); it
++)
574 m_isParallel
[*it
] = true;