ext/OGDF/ogdf/module/CrossingMinimizationModule.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 CrossingMinimization Module, an interface for crossing minimization algorithms
  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 #ifndef OGDF_CROSSING_MINIMIZATION_MODULE_H
  44 #define OGDF_CROSSING_MINIMIZATION_MODULE_H
  45
  46
  47
  48 #include <ogdf/planarity/PlanRep.h>
  49 #include <ogdf/basic/extended_graph_alg.h>
  50 #include <ogdf/basic/Module.h>
  51 #include <ogdf/basic/Logger.h>
  52 #include <ogdf/basic/Timeouter.h>
  53
  54
  55 namespace ogdf {
  56
  57 /**
  58  * \brief Interface for crossing minimization algorithms.
  59  *
  60  */
  61 class OGDF_EXPORT CrossingMinimizationModule : public Module, public Timeouter
  62 {
  63 public:
  64         //! Initializes a crossing minimization module.
  65         CrossingMinimizationModule() { }
  66
  67         // destruction
  68         virtual ~CrossingMinimizationModule() { }
  69
  70         /**
  71          * \brief Computes a planarized representation of the input graph.
  72          *
  73          * @param PG represents the input graph as well as the computed planarized
  74          *        representation after the call. \a PG has to be initialzed as a
  75          *        PlanRep of the input graph and is modified to obatain the planarized
  76          *        representation (crossings are replaced by dummy vertices with degree
  77          *        four.
  78          * @param cc is the number of the connected component in \a PG that is considered.
  79          * @param crossingNumber is assigned the number of crossings.
  80          * @param forbid points to an edge array indicating which edges are not allowed
  81          *        to be crossed, i.e., (*forbid)[e] = true. If forbid = 0, no edges are
  82          *        forbidden.
  83          * @param cost points to an edge array that gives the cost of each edge. If cost
  84          *        = 0, all edges have cost 1.
  85          * @param subgraphs
  86          * \return the status of the result.
  87          */
  88         ReturnType call(PlanRep &PG,
  89                         int cc,
  90                         int&  crossingNumber,
  91                         const EdgeArray<int>  * cost = 0,
  92                         const EdgeArray<bool> * forbid = 0,
  93                         const EdgeArray<unsigned int> * subgraphs = 0)
  94         {
  95                 m_useCost = (cost != 0);
  96                 m_useForbid = (forbid != 0);
  97                 m_useSubgraphs = (subgraphs != 0);
  98
  99                 if(!useCost())      cost      = OGDF_NEW EdgeArray<int> (PG.original(), 1);
 100                 if(!useForbid())    forbid    = OGDF_NEW EdgeArray<bool> (PG.original(), 0);
 101                 if(!useSubgraphs()) subgraphs = OGDF_NEW EdgeArray<unsigned int> (PG.original(), 1);
 102
 103                 ReturnType R = doCall(PG, cc, *cost, *forbid, *subgraphs, crossingNumber);
 104
 105                 if(!useCost())      delete cost;
 106                 if(!useForbid())    delete forbid;
 107                 if(!useSubgraphs()) delete subgraphs;
 108                 return R;
 109         };
 110
 111         //! Computes a planarized representation of the input graph (shorthand for call)
 112         ReturnType operator()(PlanRep &PG,
 113                         int cc,
 114                         int&  crossingNumber,
 115                         const EdgeArray<int>  * cost = 0,
 116                         const EdgeArray<bool> * forbid = 0,
 117                         const EdgeArray<unsigned int> * const subgraphs = 0) {
 118                 return call(PG, cc, crossingNumber, cost, forbid, subgraphs);
 119         };
 120
 121         //! Returns true iff edge costs are given.
 122         bool useCost() const { return m_useCost; }
 123
 124         //! Returns true iff forbidden edges are given.
 125         bool useForbid() const { return m_useForbid; }
 126
 127         bool useSubgraphs() const { return m_useSubgraphs; }
 128
 129 protected:
 130         /**
 131          * \brief Actual algorithm call that needs to be implemented by derived classed.
 132          *
 133          * @param PG represents the input graph as well as the computed planarized
 134          *        representation after the call. \a PG is initialzed as a
 135          *        PlanRep of the input graph and has to be modified so that it represents
 136          *        the planarized representation (crossings are replaced by dummy vertices
 137          *        with degree four).
 138          * @param cc is the number of the connected component in \a PG that is considered.
 139          * @param crossingNumber is assigned the number of crossings.
 140          * @param forbid points to an edge array indicating which edges are not allowed
 141          *        to be crossed, i.e., (*forbid)[e] = true.
 142          * @param cost points to an edge array that gives the cost of each edge.
 143          * @param subgraphs
 144          * \return the status of the result.
 145          */
 146         virtual ReturnType doCall(PlanRep &PG,
 147                 int cc,
 148                 const EdgeArray<int>  &cost,
 149                 const EdgeArray<bool> &forbid,
 150                 const EdgeArray<unsigned int> &subgraphs,
 151                 int& crossingNumber) = 0;
 152
 153         OGDF_MALLOC_NEW_DELETE
 154
 155 private:
 156         bool m_useCost; //!< True iff edge costs are given.
 157         bool m_useForbid; //!< True iff forbidden edges are given.
 158         bool m_useSubgraphs;
 159 };
 160
 161 } // end namespace ogdf
 162
 163 #endif