ext/OGDF/ogdf/planarity/MultiEdgeApproxInserter.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 MultiEdgeApproxInserter.
  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_MULTI_EDGE_APPROX_INSERTER_H
  48 #define OGDF_MULTI_EDGE_APPROX_INSERTER_H
  49
  50
  51 #include <ogdf/module/EdgeInsertionModule.h>
  52 #include <ogdf/decomposition/StaticPlanarSPQRTree.h>
  53
  54
  55 namespace ogdf {
  56
  57
  58 class OGDF_EXPORT MultiEdgeApproxInserter : public EdgeInsertionModule
  59 {
  60 public:
  61         //! Creates an instance of multi-edge inserter.
  62         MultiEdgeApproxInserter();
  63
  64         ~MultiEdgeApproxInserter() { }
  65
  66
  67         //! Sets the remove-reinsert postprocessing method.
  68         void removeReinsertFix(RemoveReinsertType rrOption) {
  69                 m_rrOptionFix = rrOption;
  70         }
  71
  72         //! Returns the current setting of the remove-reinsert postprocessing method.
  73         RemoveReinsertType removeReinsertFix() const {
  74                 return m_rrOptionFix;
  75         }
  76
  77         //! Sets the remove-reinsert postprocessing method.
  78         void removeReinsertVar(RemoveReinsertType rrOption) {
  79                 m_rrOptionVar = rrOption;
  80         }
  81
  82         //! Returns the current setting of the remove-reinsert postprocessing method.
  83         RemoveReinsertType removeReinsertVar() const {
  84                 return m_rrOptionVar;
  85         }
  86
  87         //! Sets the option <i>percentMostCrossed</i> to \a percent.
  88         /**
  89          * This option determines the portion of most crossed edges used if the remove-reinsert
  90          * method is set to #rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.
  91          */
  92         void percentMostCrossedFix(double percent) {
  93                 m_percentMostCrossedFix = percent;
  94         }
  95
  96         //! Returns the current setting of option percentMostCrossed.
  97         double percentMostCrossedFix() const {
  98                 return m_percentMostCrossedFix;
  99         }
 100
 101         //! Sets the option <i>percentMostCrossedVar</i> to \a percent.
 102         /**
 103          * This option determines the portion of most crossed edges used if the remove-reinsert
 104          * method (variable embedding) is set to #rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.
 105          */
 106         void percentMostCrossedVar(double percent) {
 107                 m_percentMostCrossedVar = percent;
 108         }
 109
 110         //! Returns the current setting of option percentMostCrossed (variable embedding).
 111         double percentMostCrossedVar() const {
 112                 return m_percentMostCrossedVar;
 113         }
 114
 115         void statistics(bool b) {
 116                 m_statistics = b;
 117         }
 118
 119         bool statistics() const {
 120                 return m_statistics;
 121         }
 122
 123         int sumInsertionCosts() const { return m_sumInsertionCosts; }
 124         int sumFEInsertionCosts() const { return m_sumFEInsertionCosts; }
 125
 126 private:
 127         enum PathDir { pdLeft, pdRight, pdNone };
 128         static PathDir s_oppDir[3];
 129
 130         class Block;
 131         class EmbeddingPreference;
 132
 133         struct VertexBlock {
 134                 VertexBlock(node v, int b) : m_vertex(v), m_block(b) { }
 135
 136                 node m_vertex;
 137                 int m_block;
 138         };
 139
 140         //! Implements the algorithm call.
 141         ReturnType doCall(
 142                 PlanRep &PG,
 143                 const List<edge> &origEdges,
 144                 bool forbidCrossingGens,
 145                 const EdgeArray<int> *costOrig,
 146                 const EdgeArray<bool> *forbiddenEdgeOrig,
 147                 const EdgeArray<unsigned int> *edgeSubGraph);
 148
 149         MultiEdgeApproxInserter::Block *constructBlock(int i);
 150         node copy(node vOrig, int b);
 151
 152         static bool dfsPathSPQR(node v, node v2, edge eParent, List<edge> &path);
 153         int computePathSPQR(int b, node v, node w, int k);
 154
 155         bool dfsPathVertex(node v, int parent, int k, node t);
 156         bool dfsPathBlock(int b, node parent, int k, node t);
 157         void computePathBC(int k);
 158
 159         void embedBlock(int b, int m);
 160         void recFlipPref(adjEntry adjP, NodeArray<EmbeddingPreference> &pi_pick, const NodeArray<bool> &visited, StaticPlanarSPQRTree &spqr);
 161
 162         void cleanup();
 163
 164         RemoveReinsertType m_rrOptionFix; //!< The remove-reinsert method for fixed embedding.
 165         RemoveReinsertType m_rrOptionVar; //!< The remove-reinsert method for variable embedding.
 166         double m_percentMostCrossedFix;   //!< The portion of most crossed edges considered (fixed embedding).
 167         double m_percentMostCrossedVar;   //!< The portion of most crossed edges considered (variable embedding).
 168         bool m_statistics; // !< Generates further statistic information.
 169
 170         PlanRep *m_pPG; // pointer to plan-rep passed in call
 171         const EdgeArray<int> *m_costOrig;
 172
 173         NodeArray<SList<int> > m_compV;     //  m_compV[v] = list of blocks containing v
 174         Array<SList<node> >    m_verticesB; // m_verticesB[i] = list of vertices in block i
 175         Array<SList<edge> >    m_edgesB;    // edgesB[i] = list of edges in block i
 176         NodeArray<node>        m_GtoBC;     // temporary mapping of nodes in PG to copies in block
 177         NodeArray<SList<VertexBlock> > m_copyInBlocks; // mapping of nodes in PG to copies in block
 178
 179         Array<edge> m_edge;                  // array of edges to be inserted
 180         Array<List<VertexBlock> > m_pathBCs; // insertion path in BC-tree for each edge
 181         Array<int> m_insertionCosts;         // computed insertion costs for each edge
 182         Array<Block*> m_block;               // array of blocks
 183
 184         // statistics of last run
 185         int m_sumInsertionCosts;
 186         int m_sumFEInsertionCosts;
 187
 188         // just for testing
 189         void constructDual(const PlanRep &PG);
 190         int findShortestPath(node s, node t);
 191
 192         ConstCombinatorialEmbedding m_E;
 193         Graph                       m_dual;
 194         FaceArray<node>             m_faceNode;
 195         AdjEntryArray<adjEntry>     m_primalAdj;
 196         node                        m_vS, m_vT;
 197 };
 198
 199
 200 } // end namespace ogdf
 201
 202 #endif