Open
Graph Drawing
Framework

 v.2012.05
 

FixedEmbeddingUpwardEdgeInserter.h
Go to the documentation of this file.
00001 /*
00002  * $Revision: 2299 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
00007  ***************************************************************/
00008 
00040 #ifdef _MSC_VER
00041 #pragma once
00042 #endif
00043 
00044 #ifndef OGDF_FIXED_EMBEDDING_UPWARD_EDGE_INSERTER_H
00045 #define OGDF_FIXED_EMBEDDING_UPWARD_EDGE_INSERTER_H
00046 
00047 
00048 
00049 #include <ogdf/module/UpwardEdgeInserterModule.h>
00050 #include <ogdf/basic/CombinatorialEmbedding.h>
00051 #include <ogdf/upward/UpwardPlanarModule.h>
00052 
00053 
00054 
00055 
00056 namespace ogdf {
00057 
00058 
00059 
00061 class OGDF_EXPORT FixedEmbeddingUpwardEdgeInserter : public UpwardEdgeInserterModule
00062 {
00063 public:
00065     FixedEmbeddingUpwardEdgeInserter() {}
00066 
00067     ~FixedEmbeddingUpwardEdgeInserter() { } 
00068     
00069 
00070 private:
00071 
00072     bool isUpwardPlanar(Graph &G) 
00073     {
00074         UpwardPlanarModule upMod;
00075         return upMod.upwardPlanarityTest(G);    
00076     }
00077 
00087     virtual ReturnType doCall(UpwardPlanRep &UPR,
00088         const List<edge> &origEdges,        
00089         const EdgeArray<int>  *costOrig = 0,
00090         const EdgeArray<bool> *forbiddenEdgeOrig = 0
00091         ); 
00092 
00093 
00094     ReturnType insertAll(UpwardPlanRep &UPR,
00095                         List<edge> &toInsert,       
00096                         EdgeArray<int>  &cost);
00097 
00098 
00100     void staticLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, const List<edge> &origEdges, edge e_orig);
00101 
00103     void dynamicLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, face f, adjEntry e_cur);
00104 
00105     void nextFeasibleEdges(UpwardPlanRep &UPR, List<adjEntry> &nextEdges, face f, adjEntry e_cur, EdgeArray<bool> &locked, bool heuristic); 
00106     
00108     void minFIP(UpwardPlanRep &UPR,
00109                 List<edge> &origEdges,
00110                 EdgeArray<int> &cost, 
00111                 edge e_orig,
00112                 SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, false); }
00113 
00114 
00115 
00117     void constraintFIP(UpwardPlanRep &UPR,
00118                 List<edge> &origEdges,
00119                 EdgeArray<int> &cost, 
00120                 edge e_orig,
00121                 SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, true); }
00122 
00124     void getPath(UpwardPlanRep &UPR,
00125                 List<edge> &origEdges,
00126                 EdgeArray<int> &cost, 
00127                 edge e_orig, 
00128                 SList<adjEntry> &path,
00129                 bool heuristic);
00130 
00131 
00133     void markUp(const Graph &G, node v, EdgeArray<bool> &markedEdges);
00134 
00135 
00137     void markDown(const Graph &G, node v, EdgeArray<bool> &markedEdges);
00138     
00140     void feasibleEdges(UpwardPlanRep &UPR,
00141                         face f, // current face
00142                         adjEntry adj, // current adjEntry, right face muss be f
00143                         EdgeArray<bool> &locked, // we compute the dyn. locked edges on the fly with respect to e
00144                         List<adjEntry> &feasible, // the list of feasible edges in f with respect to e
00145                         bool heuristic);
00146 
00148     bool isConstraintFeasible(UpwardPlanRep &UPR,
00149                             const List<edge> &orig_edges,
00150                             edge e_orig,
00151                             adjEntry adjCurrent, 
00152                             adjEntry adjNext, // the next adjEntry of the current insertion path
00153                             EdgeArray<adjEntry> &predAdj //Array to reconstruction the insertion path
00154                             );
00155 
00156 
00158     bool isConstraintFeasible(UpwardPlanRep &UPR,
00159                             List<edge> &origEdges,  
00160                             edge e_orig,
00161                             SList<adjEntry> &path); 
00162     
00163 
00164 };
00165 
00166 } // end namespace ogdf
00167 
00168 #endif