ext/OGDF/ogdf/module/MMEdgeInsertionModule.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 minor-monotone edge
  11  *        insertion 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 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_MM_EDGE_INSERTION_MODULE_H
  49 #define OGDF_MM_EDGE_INSERTION_MODULE_H
  50
  51
  52 #include <ogdf/planarity/PlanRepExpansion.h>
  53 #include <ogdf/basic/Module.h>
  54
  55
  56 namespace ogdf {
  57
  58 /**
  59  * \brief Interface for minor-monotone edge insertion algorithms.
  60  *
  61  * \see MMSubgraphPlanarizer
  62  */
  63 class OGDF_EXPORT MMEdgeInsertionModule : public Module {
  64 public:
  65         //! The postprocessing methods.
  66         enum RemoveReinsertType {
  67                 rrNone,        //!< No postprocessing.
  68                 rrInserted,    //!< Postprocessing only with the edges that have to be inserted.
  69                 rrMostCrossed, //!< Postprocessing with the edges involved in the most crossings.
  70                 rrAll,         //!< Postproceesing with all edges and all node splits.
  71                 rrIncremental  //!< Full postprocessing after each edge insertion.
  72         };
  73
  74         //! Initializes a minor-monotone edge insertion module.
  75         MMEdgeInsertionModule() { }
  76
  77         // destruction
  78         virtual ~MMEdgeInsertionModule() { }
  79
  80         /**
  81          * \brief Inserts all edges in \a origEdges into \a PG.
  82          *
  83          * @param PG is the input planarized expansion and will also receive the result.
  84          * @param origEdges is the list of original edges (edges in the original graph
  85          *        of \a PG) that have to be inserted.
  86          * \return the status of the result.
  87          */
  88         ReturnType call(PlanRepExpansion &PG, const List<edge> &origEdges) {
  89                 return doCall(PG, origEdges, 0);
  90         }
  91
  92         /**
  93          * \brief Inserts all edges in \a origEdges into \a PG and forbids crossing \a forbiddenEdges.
  94          *
  95          * @param PG is the input planarized expansion and will also receive the result.
  96          * @param origEdges is the list of original edges (edges in the original graph
  97          *        of \a PG) that have to be inserted.
  98          * @param forbiddenEdgeOrig is an edge array indicating if an original edge is
  99          *        forbidden to be crossed.
 100          * \return the status of the result.
 101          */
 102         ReturnType call(PlanRepExpansion &PG,
 103                 const List<edge> &origEdges,
 104                 const EdgeArray<bool> &forbiddenEdgeOrig)
 105         {
 106                 return doCall(PG, origEdges, &forbiddenEdgeOrig);
 107         }
 108
 109 protected:
 110         /**
 111          * \brief Actual algorithm call that has to be implemented by derived classes.
 112          *
 113          * @param PG is the input planarized expansion and will also receive the result.
 114          * @param origEdges is the list of original edges (edges in the original graph
 115          *        of \a PG) that have to be inserted.
 116          * @param forbiddenEdgeOrig points to an edge array indicating if an original edge is
 117          *        forbidden to be crossed.
 118          */
 119         virtual ReturnType doCall(PlanRepExpansion &PG,
 120                 const List<edge> &origEdges, const EdgeArray<bool> *forbiddenEdgeOrig) = 0;
 121
 122
 123         OGDF_MALLOC_NEW_DELETE
 124 };
 125
 126 } // end namespace ogdf
 127
 128 #endif