ext/OGDF/ogdf/module/MMCrossingMinimizationModule.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 MMCrossingMinimization Module, an interface
  11  * for minor-monotone crossing minimization algorithms.
  12  *
  13  * \author Carsten Gutwenger
  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 #ifndef OGDF_MM_CROSSING_MINIMIZATION_MODULE_H
  45 #define OGDF_MM_CROSSING_MINIMIZATION_MODULE_H
  46
  47
  48
  49 #include <ogdf/planarity/PlanRepExpansion.h>
  50 #include <ogdf/basic/Module.h>
  51 #include <ogdf/basic/Logger.h>
  52
  53
  54 namespace ogdf {
  55
  56 /**
  57  * \brief Interface for minor-monotone crossing minimization algorithms.
  58  *
  59  */
  60 class OGDF_EXPORT MMCrossingMinimizationModule : public Module
  61 {
  62 public:
  63         //! Initializes a minor-monotone crossing minimization module.
  64         MMCrossingMinimizationModule() { m_nodeSplits = 0; }
  65
  66         // destruction
  67         virtual ~MMCrossingMinimizationModule() { }
  68
  69         /**
  70          * \brief Computes a planarized representation of an expansion of the input graph.
  71          *
  72          * @param PG represents the input graph as well as the computed planarized
  73          *        expansion after the call. \a PG has to be initialzed as a
  74          *        PlanRepExpansion of the input graph and is modified to obatain the planarized
  75          *        representation (nodes are eventually expanded by splitting the node and
  76          *        crossings are replaced by dummy vertices with degree four).
  77          * @param cc is the number of the connected component in \a PG that is considered.
  78          * @param crossingNumber is assigned the number of crossings.
  79          * @param forbid points to an edge array indicating which edges are not allowed
  80          *        to be crossed, i.e., (*forbid)[e] = true. If forbid = 0, no edges are
  81          *        forbidden.
  82          * \return the status of the result.
  83          */
  84         ReturnType call(PlanRepExpansion &PG,
  85                         int cc,
  86                         int&  crossingNumber,
  87                         const EdgeArray<bool> *forbid = 0)
  88         {
  89                 return doCall(PG, cc, forbid, crossingNumber, m_nodeSplits, m_splittedNodes);
  90         };
  91
  92         /**
  93          * \brief Performs minor-monotone crossing minimization on \a G.
  94          *
  95          * @param G is the input graph.
  96          * @param cr is assigned the number of crossings.
  97          * @param forbid points to an edge array indicating which edges are not allowed
  98          *        to be crossed, i.e., (*forbid)[e] = true. If forbid = 0, no edges are
  99          *        forbidden.
 100          * \return the status of the result.
 101          */
 102         ReturnType call(const Graph &G, int &cr, const EdgeArray<bool> *forbid = 0);
 103
 104         /**
 105          * \brief Performs minor-monotone crossing minimization on \a G for given splittable nodes.
 106          *
 107          * @param G is the input graph.
 108          * @param splittableNodes is the list of nodes that are allowed to be split.
 109          * @param cr is assigned the number of crossings.
 110          * @param forbid points to an edge array indicating which edges are not allowed
 111          *        to be crossed, i.e., (*forbid)[e] = true. If forbid = 0, no edges are
 112          *        forbidden.
 113          * \return the status of the result.
 114          */
 115         ReturnType call(const Graph &G,
 116                 const List<node> &splittableNodes,
 117                 int &cr,
 118                 const EdgeArray<bool> *forbid = 0);
 119
 120         /**
 121          * \brief Returns the number of required node splits after the call.
 122          */
 123         int numberOfNodeSplits() const { return m_nodeSplits; }
 124
 125         int numberOfSplittedNodes() const { return m_splittedNodes; }
 126
 127 protected:
 128         /**
 129          * \brief Actual algorithm call that needs to be implemented by derived classed.
 130          *
 131          * @param PG represents the input graph as well as the computed planarized expansion
 132          *        after the call. \a PG is initialized as a PlanRepExpansion of the input
 133          *        graph and needs to be modified to obatain the planarized representation
 134          *        (crossings are replaced by dummy vertices with degree four).
 135          * @param cc is the number of the connected component in \a PG that is considered.
 136          * @param forbid points to an edge array indicating which edges are not allowed
 137          *        to be crossed, i.e., (*forbid)[e] = true.
 138          * @param crossingNumber needs to be assigned the number of crossings.
 139          * @param numNS needs to be assigned the required number of node splits.
 140          * @param numSN needs to be assigned the number of splitted nodes.
 141          * \return the status of the result.
 142          */
 143         virtual ReturnType doCall(PlanRepExpansion &PG,
 144                 int cc,
 145                 const EdgeArray<bool> *forbid,
 146                 int& crossingNumber,
 147                 int& numNS,
 148                 int& numSN) = 0;
 149
 150 private:
 151         int m_nodeSplits;    //!< The number of required node splits.
 152         int m_splittedNodes; //!< The number of nodes that are split.
 153
 154         OGDF_MALLOC_NEW_DELETE
 155 };
 156
 157 } // end namespace ogdf
 158
 159 #endif