ext/OGDF/ogdf/planarity/FastPlanarSubgraph.h

   1 /*
   2  * $Revision: 2566 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 23:10:08 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of the FastPlanarSubgraph.
  11  *
  12  * \author Sebastian Leipert
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #ifdef _MSC_VER
  44 #pragma once
  45 #endif
  46
  47
  48 #ifndef OGDF_FAST_PLANAR_SUBGRAPH_H
  49 #define OGDF_FAST_PLANAR_SUBGRAPH_H
  50
  51
  52
  53 #include <ogdf/module/PlanarSubgraphModule.h>
  54
  55
  56 namespace ogdf {
  57
  58 /**
  59  * \brief Computation of a planar subgraph using PQ-trees.
  60  *
  61  * Literature: Jayakumar, Thulasiraman, Swamy 1989
  62  *
  63  * <h3>Optional Parameters</h3>
  64  *
  65  * <table>
  66  *   <tr>
  67  *     <th>Option</th><th>Type</th><th>Default</th><th>Description</th>
  68  *   </tr><tr>
  69  *     <td><i>runs</i></td><td>int</td><td>0</td>
  70  *     <td>the number of randomized runs performed by the algorithm; the best
  71  *         solution is picked among all the runs. If runs is 0, one
  72  *         deterministic run is performed.</td>
  73  *   </tr>
  74  * </table>
  75  *
  76  * Observe that this algorithm by theory does not compute a maximal
  77  * planar subgraph. It is however the fastest known good heuristic.
  78  */
  79 class OGDF_EXPORT FastPlanarSubgraph : public PlanarSubgraphModule{
  80
  81 public:
  82         //! Creates an instance of the fast planar subgraph algorithm.
  83         FastPlanarSubgraph() : PlanarSubgraphModule() {
  84                 m_nRuns = 0;
  85         };
  86
  87         // destructor
  88         ~FastPlanarSubgraph() { }
  89
  90
  91         // options
  92
  93         //! Sets the number of randomized runs to \a nRuns.
  94         void runs (int nRuns) {
  95                 m_nRuns = nRuns;
  96         }
  97
  98         //! Returns the current number of randomized runs.
  99         int runs() const {
 100                 return m_nRuns;
 101         }
 102
 103
 104 protected:
 105         //! Returns true, if G is planar, false otherwise.
 106         /**
 107          * \todo Add timeout support (limit number of runs when timeout is reached).
 108          */
 109         ReturnType doCall(const Graph &G,
 110                 const List<edge> &preferedEdges,
 111                 List<edge> &delEdges,
 112                 const EdgeArray<int>  *pCost,
 113                 bool preferedImplyPlanar);
 114
 115
 116 private:
 117         int m_nRuns;  //!< The number of runs for randomization.
 118
 119
 120         //! Computes the list of edges to be deleted in \a G.
 121         /** Also performs randomization of the planarization algorithm.
 122          */
 123         void computeDelEdges(const Graph &G,
 124                 const EdgeArray<int> *pCost,
 125                 const EdgeArray<edge> *backTableEdges,
 126                 List<edge> &delEdges);
 127
 128         //! Performs a planarization on a biconnected component pf \a G.
 129         /** The numbering contains an st-numbering of the component.
 130          */
 131         void planarize(
 132                 const Graph &G,
 133                 NodeArray<int> &numbering,
 134                 List<edge> &delEdges);
 135 };
 136
 137 }
 138 #endif