ext/OGDF/ogdf/planarity/FixedEmbeddingInserter.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 FixedEmbeddingInserter
  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 #ifdef _MSC_VER
  44 #pragma once
  45 #endif
  46
  47 #ifndef OGDF_FIXED_EMBEDDING_INSERTER_H
  48 #define OGDF_FIXED_EMBEDDING_INSERTER_H
  49
  50
  51
  52 #include <ogdf/module/EdgeInsertionModule.h>
  53 #include <ogdf/basic/CombinatorialEmbedding.h>
  54 #include <ogdf/basic/FaceArray.h>
  55
  56
  57 template <class E> class FaceArray;
  58
  59
  60 namespace ogdf {
  61
  62
  63 class OGDF_EXPORT FaceSetSimple;
  64
  65
  66 //! Edge insertion module that inserts each edge optimally into a fixed embedding.
  67 class OGDF_EXPORT FixedEmbeddingInserter : public EdgeInsertionModule
  68 {
  69 public:
  70         //! Creates an instance of fixed-embedding edge inserter.
  71         FixedEmbeddingInserter();
  72
  73         ~FixedEmbeddingInserter() { }
  74
  75         /**
  76          *  @name Optional parameters
  77          *  @{
  78          */
  79
  80         //! Sets the remove-reinsert postprocessing method.
  81         void removeReinsert(RemoveReinsertType rrOption) {
  82                 m_rrOption = rrOption;
  83         }
  84
  85         //! Returns the current setting of the remove-reinsert postprocessing method.
  86         RemoveReinsertType removeReinsert() const {
  87                 return m_rrOption;
  88         }
  89
  90
  91         //! Sets the option <i>percentMostCrossed</i> to \a percent.
  92         /**
  93          * This option determines the portion of most crossed edges used if the remove-reinsert
  94          * method is set to #rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.
  95          */
  96         void percentMostCrossed(double percent) {
  97                 m_percentMostCrossed = percent;
  98         }
  99
 100         //! Returns the current setting of option <i>percentMostCrossed</i>.
 101         double percentMostCrossed() const {
 102                 return m_percentMostCrossed;
 103         }
 104
 105         //! Sets the option <i>keepEmbedding</i> to \a keep.
 106         /**
 107          * This option determines if the planar embedding of the planarized representation \a PG passed to the call-method
 108          * is preserved, or if always a new embedding is computed. If <i>keepEmbedding</i> is set to true,
 109          * \a PG must always be planarly embedded.
 110          */
 111         void keepEmbedding(bool keep) {
 112                 m_keepEmbedding = keep;
 113         }
 114
 115         //! Returns the current setting of option <i>keepEmbedding</i>.
 116         bool keepEmbeding() const {
 117                 return m_keepEmbedding;
 118         }
 119
 120         /** @}
 121          *  @name Further information
 122          *  @{
 123          */
 124
 125         //! Returns the number of runs performed by the remove-reinsert method after the algorithm has been called.
 126         int runsPostprocessing() const {
 127                 return m_runsPostprocessing;
 128         }
 129
 130         //! @}
 131
 132 private:
 133         //! Implements the algorithm call.
 134         ReturnType doCall(
 135                 PlanRep &PG,                  // planarized representation
 136                 const List<edge> &origEdges,     // original edge to be inserted
 137                 bool forbidCrossinGens,          // frobid crossings between gen's
 138                 const EdgeArray<int> *costOrig,  // pointer to array of cost of
 139                                 // original edges; if pointer is 0 all costs are 1
 140                 const EdgeArray<bool> *forbiddenEdgeOrig = 0,
 141                 const EdgeArray<unsigned int> *edgeSubGraph = 0); // pointer to array deciding
 142                                 // which original edges are forbidden to cross; if pointer is
 143                                 // is 0 no edges are explicitly forbidden to cross
 144
 145         //! Construct the dual graph.
 146         /**
 147          * Marks dual edges corresponding to generalization in m_primalIsGen;
 148          * assumes that m_pDual, m_primalAdj and m_pNodeOf are already constructed.
 149          */
 150         void constructDualForbidCrossingGens(const PlanRepUML &PG,
 151                 const CombinatorialEmbedding &E);
 152
 153         //! Construct the dual graph.
 154         /**
 155          * Assumes that m_pDual, m_primalAdj and m_pNodeOf are already constructed.
 156          */
 157         void constructDual(const GraphCopy &GC,
 158                 const CombinatorialEmbedding &E,
 159                 const EdgeArray<bool> *forbiddenEdgeOrig);
 160
 161         //! Finds a shortest path in the dual graph augmented by \a s and \a t.
 162         /**
 163          * Returns the list of crossed adjacency entries (corresponding
 164          * to used edges in the dual) in \a crossed.
 165          */
 166         void findShortestPath(const CombinatorialEmbedding &E,
 167                 node s,
 168                 node t,
 169                 Graph::EdgeType eType,
 170                 SList<adjEntry> &crossed);
 171
 172         //! Finds a weighted shortest path in the dual graph augmented by \a s and \a t.
 173         /**
 174          * Uses edges weights given by costOrig;
 175          * returns the list of crossed adjacency entries (corresponding to used
 176          * edges in the dual) in \a crossed.
 177          */
 178         void findShortestPath(
 179                 const PlanRep &PG,
 180                 const CombinatorialEmbedding &E,
 181                 const EdgeArray<int> &costOrig,
 182                 node s,
 183                 node t,
 184                 Graph::EdgeType eType,
 185                 SList<adjEntry> &crossed,
 186                 const EdgeArray<unsigned int> *edgeSubGraph,
 187                 int eSubGraph);
 188
 189         void insertEdge(PlanRep &PG,
 190                 CombinatorialEmbedding &E,
 191                 edge eOrig,
 192                 const SList<adjEntry> &crossed,
 193                 bool forbidCrossingGens,
 194                 const EdgeArray<bool> *forbiddenEdgeOrig);
 195
 196         void removeEdge(
 197                 PlanRep &PG,
 198                 CombinatorialEmbedding &E,
 199                 edge eOrig,
 200                 bool forbidCrossingGens,
 201                 const EdgeArray<bool> *forbiddenEdgeOrig);
 202
 203         edge crossedEdge(adjEntry adj) const;
 204         int costCrossed(edge eOrig,
 205                 const PlanRep &PG,
 206                 const EdgeArray<int> &costOrig,
 207                 const EdgeArray<unsigned int> *subgraphs) const;
 208
 209         Graph m_dual;   //!< (Extended) dual graph, constructed/destructed during call.
 210
 211         EdgeArray<adjEntry> m_primalAdj;   //!< Adjacency entry in primal graph corresponding to edge in dual.
 212         FaceArray<node>     m_nodeOf;      //!< The node in dual corresponding to face in primal.
 213         EdgeArray<bool>     m_primalIsGen; //!< true iff corresponding primal edge is a generalization.
 214         FaceSetSimple       *m_delFaces;
 215         FaceSetPure         *m_newFaces;
 216
 217         node m_vS; //!< The node in extended dual representing s.
 218         node m_vT; //!< The node in extended dual representing t.
 219
 220
 221         RemoveReinsertType m_rrOption; //!< The remove-reinsert method.
 222         double m_percentMostCrossed;   //!< The portion of most crossed edges considered.
 223         bool m_keepEmbedding;
 224
 225         int m_runsPostprocessing; //!< Runs of remove-reinsert method.
 226 };
 227
 228 } // end namespace ogdf
 229
 230 #endif