ext/OGDF/ogdf/planarity/VariableEmbeddingInserter.h

   1 /*
   2  * $Revision: 2566 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 23:10:08 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class VariablEmbeddingInserter.
  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_VARIABLE_EMBEDDING_INSERTER_H
  48 #define OGDF_VARIABLE_EMBEDDING_INSERTER_H
  49
  50
  51 #include <ogdf/module/EdgeInsertionModule.h>
  52 #include <ogdf/basic/CombinatorialEmbedding.h>
  53 #include <ogdf/basic/FaceArray.h>
  54
  55
  56 namespace ogdf {
  57
  58 class PlanarSPQRTree;
  59 class ExpandedGraph;
  60 class PlaneGraphCopy;
  61
  62
  63 class BiconnectedComponent;
  64
  65
  66 //! Optimal edge insertion module.
  67 /**
  68  * The class VariableEmbeddingInserter represents the optimal edge insertion
  69  * algorithm, which inserts a single edge with a minum number of crossings
  70  * into a planar graph.
  71  *
  72  * The implementation is based on the following publication:
  73  *
  74  * Carsten Gutwenger, Petra Mutzel, Rene Weiskircher: <i>Inserting an Edge into
  75  * a Planar %Graph</i>. Algorithmica 41(4), pp. 289-308, 2005.
  76  */
  77 class OGDF_EXPORT VariableEmbeddingInserter : public EdgeInsertionModule
  78 {
  79 public:
  80         //! Creates an instance of variable embedding edge inserter.
  81         VariableEmbeddingInserter();
  82
  83         ~VariableEmbeddingInserter() { }
  84
  85         /**
  86          * \brief Calls only the postprocessing; assumes that all edges in \a origEdges are already inserted into \a PG.
  87          *
  88          * @param PG is the input planarized representation and will also receive the result.
  89          * @param origEdges is the list of original edges (edges in the original graph
  90          *        of \a PG) that have to be inserted.
  91          * \return the status of the result.
  92          */
  93         ReturnType callPostprocessing(PlanRep &PG, const List<edge> &origEdges) {
  94                 return doCallPostprocessing(PG, origEdges, false, 0, 0, 0);
  95         }
  96
  97
  98         /**
  99          *  @name Optional parameters
 100          *  @{
 101          */
 102
 103         //! Sets the remove-reinsert postprocessing method.
 104         void removeReinsert(RemoveReinsertType rrOption) {
 105                 m_rrOption = rrOption;
 106         }
 107
 108         //! Returns the current setting of the remove-reinsert postprocessing method.
 109         RemoveReinsertType removeReinsert() const {
 110                 return m_rrOption;
 111         }
 112
 113
 114         //! Sets the option <i>percentMostCrossed</i> to \a percent.
 115         /**
 116          * This option determines the portion of most crossed edges used if the remove-reinsert
 117          * method is set to #rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.
 118          */
 119         void percentMostCrossed(double percent) {
 120                 m_percentMostCrossed = percent;
 121         }
 122
 123         //! Returns the current setting of option percentMostCrossed.
 124         double percentMostCrossed() const {
 125                 return m_percentMostCrossed;
 126         }
 127
 128         /** @}
 129          *  @name Further information
 130          *  @{
 131          */
 132
 133         //! Returns the number of runs performed by the remove-reinsert method after the algorithm has been called.
 134         int runsPostprocessing() const {
 135                 return m_runsPostprocessing;
 136         }
 137
 138         //! @}
 139
 140 private:
 141         //! Implements the algorithm call.
 142         ReturnType doCall(
 143                 PlanRep &PG,                  // planarized representation
 144                 const List<edge> &origEdges,     // original edge to be inserted
 145                 bool forbidCrossingGens,         // frobid crossings between gen's
 146                 const EdgeArray<int> *costOrig,  // pointer to array of cost of original edges; if pointer is 0 all costs are 1
 147                 const EdgeArray<bool> *forbiddenEdgeOrig, // pointer to array deciding
 148                                 // which original edges are forbidden to cross; if pointer is
 149                                 // is 0 no edges are explicitly forbidden to cross
 150                 const EdgeArray<unsigned int> *edgeSubGraph); // pointer to array of SubGraphInformation
 151         // used in Simultaneous Drawing
 152
 153         ReturnType doCallPostprocessing(
 154                 PlanRep &PG,                  // planarized representation
 155                 const List<edge> &origEdges,     // original edge to be inserted
 156                 bool forbidCrossingGens,         // frobid crossings between gen's
 157                 const EdgeArray<int> *costOrig,  // pointer to array of cost of original edges; if pointer is 0 all costs are 1
 158                 const EdgeArray<bool> *forbiddenEdgeOrig, // pointer to array deciding
 159                                 // which original edges are forbidden to cross; if pointer is
 160                                 // is 0 no edges are explicitly forbidden to cross
 161                 const EdgeArray<unsigned int> *edgeSubGraph); // pointer to array of SubGraphInformation
 162
 163         edge crossedEdge(adjEntry adj) const;
 164         int costCrossed(edge eOrig) const;
 165
 166         bool                   m_forbidCrossingGens;
 167         const EdgeArray<int>  *m_costOrig;
 168         const EdgeArray<bool> *m_forbiddenEdgeOrig;
 169         const EdgeArray<unsigned int>  *m_edgeSubgraph;
 170         Graph::EdgeType        m_typeOfCurrentEdge;
 171
 172         void insert(node s, node t, SList<adjEntry> &eip);
 173         void blockInsert(const BiconnectedComponent &G,
 174                 node s,
 175                 node t,
 176                 List<adjEntry> &L);
 177
 178         bool dfsVertex(node v, int parent);
 179         bool dfsComp(int i, node parent, node &repT);
 180
 181         PlanRep *m_pPG;
 182         node   m_s, m_t;
 183         edge   m_st;
 184         SList<adjEntry> *m_pEip;
 185
 186         static int m_bigM;  // used for SimDraw
 187
 188         NodeArray<SList<int> > m_compV;
 189         Array<SList<node> >    m_nodeB;
 190         Array<SList<edge> >    m_edgeB;
 191         NodeArray<node>        m_GtoBC;
 192
 193         bool pathSearch(node v, edge parent, List<edge> &path);
 194         void buildSubpath(node v,
 195                 edge eIn,
 196                 edge eOut,
 197                 List<adjEntry> &L,
 198                 ExpandedGraph &Exp,
 199                 node s,
 200                 node t);
 201         edge insertEdge(node v, node w, Graph &Exp,
 202                 NodeArray<node> &GtoExp, List<node> &nodesG);
 203
 204         node m_v1, m_v2;
 205
 206         RemoveReinsertType m_rrOption; //!< The remove-reinsert method.
 207         double m_percentMostCrossed;   //!< The portion of most crossed edges considered.
 208
 209         int m_runsPostprocessing; //!< Runs of remove-reinsert method.
 210 };
 211
 212 } // end namespace ogdf
 213
 214 #endif