ext/OGDF/ogdf/module/PlanarSubgraphModule.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 interface for planar subgraph algorithms.
  11  *
  12  * \author Carsten Gutwenger
  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 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_PLANAR_SUBGRAPH_MODULE_H
  49 #define OGDF_PLANAR_SUBGRAPH_MODULE_H
  50
  51
  52
  53 #include <ogdf/planarity/PlanRepUML.h>
  54 #include <ogdf/basic/Module.h>
  55 #include <ogdf/basic/Logger.h>
  56 #include <ogdf/basic/Timeouter.h>
  57
  58
  59 namespace ogdf {
  60
  61 /**
  62  * \brief Interface for planar subgraph algorithms.
  63  *
  64  * \see PlanarizationLayout, PlanarizationGridLayout
  65  */
  66 class OGDF_EXPORT PlanarSubgraphModule : public Module, public Timeouter {
  67 public:
  68         //! Initializes a planar subgraph module.
  69         PlanarSubgraphModule() { }
  70
  71         // destruction
  72         virtual ~PlanarSubgraphModule() { }
  73
  74         /**
  75          * \brief Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
  76          * @param G is the input graph.
  77          * @param preferedEdges are edges that should be contained in the planar subgraph.
  78          * @param delEdges is the set of edges that need to be deleted to obtain the planar subgraph.
  79          * @param preferedImplyPlanar indicates that the edges \a preferedEdges induce a planar graph.
  80          */
  81         ReturnType call(const Graph &G,
  82                 const List<edge> &preferedEdges,
  83                 List<edge> &delEdges,
  84                 bool preferedImplyPlanar = false)
  85         {
  86                 return doCall(G,preferedEdges,delEdges,0,preferedImplyPlanar);
  87         }
  88
  89
  90         /**
  91          * \brief Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
  92          * @param G is the input graph.
  93          * @param cost are the costs of edges.
  94          * @param delEdges is the set of edges that need to be deleted to obtain the planar subgraph.
  95          */
  96         ReturnType call(const Graph &G, const EdgeArray<int> &cost, List<edge> &delEdges) {
  97                 List<edge> preferedEdges;
  98                 return doCall(G,preferedEdges,delEdges, &cost);
  99         }
 100
 101         /**
 102          * \brief Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
 103          * @param G is the input graph.
 104          * @param delEdges is the set of edges that need to be deleted to obtain the planar subgraph.
 105          */
 106         ReturnType call(const Graph &G, List<edge> &delEdges) {
 107                 List<edge> preferedEdges;
 108                 return doCall(G,preferedEdges,delEdges);
 109         }
 110
 111
 112         //! Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
 113         ReturnType operator()(const Graph &G,
 114                 const List<edge> &preferedEdges,
 115                 List<edge> &delEdges,
 116                 bool preferedImplyPlanar = false)
 117         {
 118                 return call(G,preferedEdges,delEdges,preferedImplyPlanar);
 119         }
 120
 121         //! Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
 122         ReturnType operator()(const Graph &G, List<edge> &delEdges) {
 123                 return call(G,delEdges);
 124         }
 125
 126
 127         /**
 128          * \brief Makes \a G planar by deleting edges.
 129          * @param GC is a copy of the input graph.
 130          * @param preferedEdges are edges in \a GC that should be contained in the planar subgraph.
 131          * @param delOrigEdges is the set of original edges whose copy has been deleted in \a GC.
 132          * @param preferedImplyPlanar indicates that the edges \a preferedEdges induce a planar graph.
 133          */
 134         ReturnType callAndDelete(GraphCopy &GC,
 135                 const List<edge> &preferedEdges,
 136                 List<edge> &delOrigEdges,
 137                 bool preferedImplyPlanar = false);
 138
 139         /**
 140          * \brief Makes \a G planar by deleting edges.
 141          * @param GC is a copy of the input graph.
 142          * @param delOrigEdges is the set of original edges whose copy has been deleted in \a GC.
 143          */
 144         ReturnType callAndDelete(GraphCopy &GC, List<edge> &delOrigEdges) {
 145                 List<edge> preferedEdges;
 146                 return callAndDelete(GC,preferedEdges,delOrigEdges);
 147         }
 148
 149 protected:
 150         // computes set of edges delEdges, which have to be deleted
 151         // in order to get a planar subgraph; edges in preferedEdges
 152         // should be contained in planar subgraph
 153         // must be implemented by derived classes!
 154         /**
 155          * \brief Computes the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
 156          *
 157          * This is the actual algorithm call and needs to be implemented
 158          * by derived classes.
 159          * @param G is the input graph.
 160          * @param preferedEdges are edges that should be contained in the planar subgraph.
 161          * @param delEdges is the set of edges that need to be deleted to obtain the planar subgraph.
 162          * @param pCost is apointer to an edge array containing the edge costs; this pointer
 163          *        can be 0 if no costs are given (all edges have cost 1).
 164          * @param preferedImplyPlanar indicates that the edges \a preferedEdges induce a planar graph.
 165          */
 166         virtual ReturnType doCall(const Graph &G,
 167                 const List<edge> &preferedEdges,
 168                 List<edge> &delEdges,
 169                 const EdgeArray<int>  *pCost = 0,
 170                 bool preferedImplyPlanar = false) = 0;
 171
 172
 173
 174         OGDF_MALLOC_NEW_DELETE
 175 };
 176
 177 } // end namespace ogdf
 178
 179 #endif