1 /** \file
2  * \brief Declaration of BoothLueker which implements a planarity
3  *        test and planar embedding algorithm.
4  *
5  * \author Sebastian Leipert, Markus Chimani
6  *
7  * \par License:
8  * This file is part of the Open Graph Drawing Framework (OGDF).
9  *
10  * \par
11  * Copyright (C)<br>
12  * See README.md in the OGDF root directory for details.
13  *
14  * \par
15  * This program is free software; you can redistribute it and/or
16  * modify it under the terms of the GNU General Public License
17  * Version 2 or 3 as published by the Free Software Foundation;
18  * see the file LICENSE.txt included in the packaging of this file
19  * for details.
20  *
21  * \par
22  * This program is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
25  * GNU General Public License for more details.
26  *
27  * \par
28  * You should have received a copy of the GNU General Public
29  * License along with this program; if not, see
30  * http://www.gnu.org/copyleft/gpl.html
31  */
32 
33 #pragma once
34 
35 #include <ogdf/basic/EdgeArray.h>
36 #include <ogdf/basic/NodeArray.h>
37 #include <ogdf/basic/SList.h>
38 #include <ogdf/planarity/PlanarityModule.h>
39 
40 namespace ogdf {
41 
42 //! Booth-Lueker planarity test.
43 /**
44  * @ingroup ga-planembed
45  *
46  * This class implements the linear-time planarity test proposed by Booth and Luecker, based on PQ-trees.\n
47  * This class is deprecated! You will usually want to use the more modern/faster/versatile linear-time planarity test
48  * by Boyer and Myrvold instead, implemented in the class BoyerMyrvold.
49  * Generally, it is suggested to use the direct function calls isPlanar and planarEmbed in extended_graph_alg.h (which in turn use BoyerMyrvold).
50  */
51 class OGDF_EXPORT BoothLueker : public PlanarityModule {
52 
53 public:
54 
BoothLueker()55 	BoothLueker() { }
~BoothLueker()56 	~BoothLueker() { }
57 
58 	//! Returns true, if G is planar, false otherwise.
59 	virtual bool isPlanarDestructive(Graph &G) override;
60 
61 	//! Returns true, if G is planar, false otherwise.
62 	virtual bool isPlanar(const Graph &G) override;
63 
64 	//! Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.
planarEmbed(Graph & G)65 	virtual bool planarEmbed(Graph &G) override {
66 		return preparation(G,true);
67 	}
68 
69 	//! Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.
70 	/**
71 	 * For BoothLueker, this procedure is exactly the same as planarEmbed. (See PlanarityModule or
72 	 * BoyerMyrvold for the rationale of this function's existence.
73 	 */
planarEmbedPlanarGraph(Graph & G)74 	virtual bool planarEmbedPlanarGraph(Graph &G) override {
75 		return preparation(G,true);
76 	}
77 
78 private:
79 
80 	//! Prepares the planarity test and the planar embedding
81 	bool preparation(Graph &G, bool embed);
82 
83 	/**
84 	 * Performs a planarity test on a biconnected component of \p G.
85 	 *
86 	 * \p numbering contains an st-numbering of the component.
87 	 */
88 	bool doTest(Graph &G,NodeArray<int> &numbering);
89 
90 	/**
91 	 * Performs a planarity test on a biconnected component of \p G and embedds it planar.
92 	 *
93 	 * \p numbering contains an st-numbering of the component.
94 	 */
95 	bool doEmbed(Graph &G,
96 		NodeArray<int>  &numbering,
97 		EdgeArray<edge> &backTableEdges,
98 		EdgeArray<edge> &forwardTableEdges);
99 
100 	// Used by doEmbed. Computes an entire embedding from an
101 	// upward embedding.
102 	void entireEmbed(Graph &G,
103 		NodeArray<SListPure<adjEntry> > &entireEmbedding,
104 		NodeArray<SListIterator<adjEntry> > &adjMarker,
105 		NodeArray<bool> &mark,
106 		node v);
107 
108 	void prepareParallelEdges(Graph &G);
109 
110 
111 	//private Members for handling parallel edges
112 	EdgeArray<ListPure<edge> > m_parallelEdges;
113 	EdgeArray<bool> m_isParallel;
114 	int	m_parallelCount;
115 };
116 
117 }
118