ext/OGDF/ogdf/planarity/SubgraphPlanarizer.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class SubgraphPlanarizer.
  11  *
  12  * \author Markus Chimani
  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
  44 #ifndef OGDF_SUBGRAPH_PLANARIZER_H
  45 #define OGDF_SUBGRAPH_PLANARIZER_H
  46
  47 #include <ogdf/module/CrossingMinimizationModule.h>
  48 #include <ogdf/module/PlanarSubgraphModule.h>
  49 #include <ogdf/module/EdgeInsertionModule.h>
  50 #include <ogdf/basic/ModuleOption.h>
  51 #include <ogdf/basic/Logger.h>
  52
  53
  54 namespace ogdf
  55 {
  56
  57 //! The planarization approach for crossing minimization.
  58 /**
  59  * This crossing minimization module represents a customizable implementation
  60  * of the planarization approach. This approach consists of two phases.
  61  * In the first phase, a planar subgraph is computed, and in the second
  62  * phase, the remaining edges are re-inserted one-by-one, each time with
  63  * as few crossings as possible; the crossings are then replaced by dummy
  64  * nodes of degree four, resulting in a <i>planarized representation</i> of the
  65  * graph.
  66  *
  67  * Both steps, the computation of the planar subgraph and the re-insertion
  68  * of a single edge, are implemented using module options. Additionaly,
  69  * the second phase can be repeated several times, each time with a randomly
  70  * permuted order of the edges to be re-inserted, and taking the solution
  71  * with the least crossings. This can improve the quality of the solution
  72  * significantly. More details on the planarization approach can be found in
  73  *
  74  * C. Gutwenger, P. Mutzel: <i>An Experimental Study of Crossing
  75  * Minimization Heuristics</i>. 11th International Symposium on %Graph
  76  * Drawing 2003, Perugia (GD '03), LNCS 2912, pp. 13-24, 2004.
  77  *
  78  * <H3>Optional parameters</H3>
  79  *
  80  * <table>
  81  *   <tr>
  82  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  83  *   </tr><tr>
  84  *     <td><i>permutations</i><td>int<td>1
  85  *     <td>The number of permutations the (complete) edge insertion phase is repeated.
  86  *   </tr><tr>
  87  *     <td><i>setTimeout</i><td>bool<td>true
  88  *     <td>If set to true, the time limit is also passed to submodules; otherwise,
  89  *     a timeout might be checked late when a submodule requires a lot of runtime.
  90  *   </tr>
  91  * </table>
  92  *
  93  * <H3>%Module options</H3>
  94  * The various phases of the algorithm can be exchanged by setting
  95  * module options allowing flexible customization. The algorithm provides
  96  * the following module options:
  97  *
  98  * <table>
  99  *   <tr>
 100  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
 101  *   </tr><tr>
 102  *     <td><i>subgraph</i><td>PlanarSubgraphModule<td>FastPlanarSubgraph
 103  *     <td>The module for the computation of the planar subgraph.
 104  *   </tr><tr>
 105  *     <td><i>inserter</i><td>EdgeInsertionModule<td>VariableEmbeddingInserter
 106  *     <td>The module used for edge insertion. The edges not contained in the planar
 107  *     subgraph are re-inserted one-by-one, each with as few crossings as possible.
 108  *   </tr>
 109  * </table>
 110 */
 111 class OGDF_EXPORT SubgraphPlanarizer : public CrossingMinimizationModule, public Logger
 112 {
 113         class CrossingStructure
 114         {
 115         public:
 116                 CrossingStructure() : m_numCrossings(0) { }
 117                 void init(PlanRep &PG, int weightedCrossingNumber);
 118                 void restore(PlanRep &PG, int cc);
 119
 120                 int numberOfCrossings() const { return m_numCrossings; }
 121                 int weightedCrossingNumber() const { return m_weightedCrossingNumber; }
 122                 const SListPure<int> &crossings(edge e) const { return m_crossings[e]; }
 123
 124         private:
 125                 int m_numCrossings;
 126                 int m_weightedCrossingNumber;
 127                 EdgeArray<SListPure<int> > m_crossings;
 128         };
 129
 130 protected:
 131         //! Implements the algorithm call.
 132         virtual ReturnType doCall(PlanRep &PG,
 133                 int cc,
 134                 const EdgeArray<int>  &cost,
 135                 const EdgeArray<bool> &forbid,
 136                 const EdgeArray<unsigned int>  &subgraphs,
 137                 int& crossingNumber);
 138
 139 public:
 140         //! Creates an instance of subgraph planarizer.
 141         SubgraphPlanarizer();
 142
 143         //! Sets the module option for the computation of the planar subgraph.
 144         void setSubgraph(PlanarSubgraphModule *pSubgraph) {
 145                 m_subgraph.set(pSubgraph);
 146         }
 147
 148         //! Sets the module option for the edge insertion module.
 149         void setInserter(EdgeInsertionModule *pInserter) {
 150                 m_inserter.set(pInserter);
 151         }
 152
 153         //! Returns the number of permutations.
 154         int permutations() { return m_permutations; }
 155
 156         //! Sets the number of permutations to \a p.
 157         void permutations(int p) { m_permutations = p; }
 158
 159         //! Returns the current setting of options <i>setTimeout</i>.
 160         bool setTimeout() { return m_setTimeout; }
 161
 162         //! Sets the option <i>setTimeout</i> to \a b.
 163         void setTimeout(bool b) { m_setTimeout = b; }
 164
 165 private:
 166         ModuleOption<PlanarSubgraphModule>  m_subgraph; //!< The planar subgraph algorithm.
 167         ModuleOption<EdgeInsertionModule>   m_inserter; //!< The edge insertion module.
 168
 169         int m_permutations;     //!< The number of permutations.
 170         bool m_setTimeout;      //!< The option for setting timeouts in submodules.
 171 };
 172
 173 }
 174
 175 #endif // OGDF_SUBGRAPH_PLANARIZER_H