ext/OGDF/ogdf/planarity/BoothLueker.h

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