ext/OGDF/ogdf/upward/FixedUpwardEmbeddingInserter.h

   1 /*
   2  * $Revision: 2555 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 12:12:10 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class FeasibleUpwardPlanarSubgraph which
  11  *        computes an feasible upward planar subgraph and a feasible upward embedding.
  12  *
  13  * \author Hoi-Ming Wong
  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
  49 #ifndef OGDF_FIXED_UPWARD_EMBEDDING_INSERTER_H
  50 #define OGDF_FIXED_UPWARD_EMBEDDING_INSERTER_H
  51
  52
  53
  54 #include <ogdf/basic/Module.h>
  55 #include <ogdf/upward/UpwardPlanarModule.h>
  56 #include <ogdf/basic/GraphCopy.h>
  57 #include <ogdf/upward/UpwardPlanRep.h>
  58
  59
  60 namespace ogdf {
  61
  62
  63 class OGDF_EXPORT FixedUpwardEmbeddingInserter : public Module
  64 {
  65 public:
  66         // construction
  67         FixedUpwardEmbeddingInserter();
  68
  69         // destruction
  70         ~FixedUpwardEmbeddingInserter(){ }
  71
  72         // Insert all edges in UPR
  73         Module::ReturnType call(UpwardPlanRep &UPR, List<edge> origEdges, EdgeArray<int> &cost);
  74
  75         bool isUpwardPlanar(Graph &G)
  76         {
  77                 UpwardPlanarModule upMod;
  78                 return upMod.upwardPlanarityTest(G);
  79         }
  80
  81 private:
  82
  83         const int infty;
  84
  85         //! compute a list of static locked edges, i.e. eges which a priory cannot included in a feasible insertion path.
  86         void staticLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, const List<edge> &origEdges, edge e_orig);
  87
  88         //! compute a list of dynamic locked edges
  89         void dynamicLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, face f, adjEntry e_cur);
  90
  91         void nextFeasibleEdges(UpwardPlanRep &UPR, List<adjEntry> &nextEdges, face f, adjEntry e_cur, EdgeArray<bool> &locked);
  92
  93         //! compute the minimal feasible insertion path
  94         void minFIP(UpwardPlanRep &UPR,
  95                                 List<edge> &origEdges,
  96                                 EdgeArray<int> &cost,
  97                                 edge e_orig,
  98                                 SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, false); }
  99
 100
 101
 102         //! compute a constraint feasible insertion path usig heuristic.
 103         void constraintFIP(UpwardPlanRep &UPR,
 104                                 List<edge> &origEdges,
 105                                 EdgeArray<int> &cost,
 106                                 edge e_orig,
 107                                 SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, true); }
 108
 109         //! compute an insertion path
 110         void getPath(UpwardPlanRep &UPR,
 111                                 List<edge> &origEdges,
 112                                 EdgeArray<int> &cost,
 113                                 edge e_orig,
 114                                 SList<adjEntry> &path,
 115                                 bool heuristic);
 116
 117
 118         //! mark the edges which are dominates by node v
 119         void markUp(const Graph &G, node v, EdgeArray<bool> &markedEdges);
 120
 121
 122         //! mark the edges which dominate node v
 123         void markDown(const Graph &G, node v, EdgeArray<bool> &markedEdges);
 124
 125         //! compute the feasible edges of the face f with respect to e
 126         void feasibleEdges(UpwardPlanRep &UPR,
 127                                                 face f, // current face
 128                                                 adjEntry adj, // current adjEntry, right face muss be f
 129                                                 EdgeArray<bool> &locked, // we compute the dyn. locked edges on the fly with respect to e
 130                                                 List<adjEntry> feasible // the list of feasible edges in f with respect to e
 131                                                 );
 132
 133         //! return true if current insertion path is contraint feasible
 134         bool isConstraintFeasible(UpwardPlanRep &UPR,
 135                                                         const List<edge> &orig_edges,
 136                                                         edge e_orig,
 137                                                         adjEntry adj, // the last adjEntry of the insertion path
 138                                                         EdgeArray<adjEntry> &predAdj //Array to reconstruction the insertion path
 139                                                         );
 140
 141
 142         //! return true if current insertion path is contraint feasible
 143         bool isConstraintFeasible(UpwardPlanRep &UPR,
 144                                                         List<edge> &origEdges,
 145                                                         edge e_orig,
 146                                                         SList<adjEntry> &path);
 147
 148 };
 149
 150
 151 } // end namespace ogdf
 152
 153 #endif