Open
Graph Drawing
Framework

 v.2012.07
 

FixedEmbeddingUpwardEdgeInserter.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2524 $
3  *
4  * last checkin:
5  * $Author: gutwenger $
6  * $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012) $
7  ***************************************************************/
8 
43 #ifdef _MSC_VER
44 #pragma once
45 #endif
46 
47 #ifndef OGDF_FIXED_EMBEDDING_UPWARD_EDGE_INSERTER_H
48 #define OGDF_FIXED_EMBEDDING_UPWARD_EDGE_INSERTER_H
49 
50 
51 
55 
56 
57 
58 
59 namespace ogdf {
60 
61 
62 
65 {
66 public:
69 
71 
72 
73 private:
74 
75  bool isUpwardPlanar(Graph &G)
76  {
77  UpwardPlanarModule upMod;
78  return upMod.upwardPlanarityTest(G);
79  }
80 
90  virtual ReturnType doCall(UpwardPlanRep &UPR,
91  const List<edge> &origEdges,
92  const EdgeArray<int> *costOrig = 0,
93  const EdgeArray<bool> *forbiddenEdgeOrig = 0
94  );
95 
96 
97  ReturnType insertAll(UpwardPlanRep &UPR,
98  List<edge> &toInsert,
99  EdgeArray<int> &cost);
100 
101 
103  void staticLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, const List<edge> &origEdges, edge e_orig);
104 
106  void dynamicLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, face f, adjEntry e_cur);
107 
108  void nextFeasibleEdges(UpwardPlanRep &UPR, List<adjEntry> &nextEdges, face f, adjEntry e_cur, EdgeArray<bool> &locked, bool heuristic);
109 
111  void minFIP(UpwardPlanRep &UPR,
112  List<edge> &origEdges,
113  EdgeArray<int> &cost,
114  edge e_orig,
115  SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, false); }
116 
117 
118 
120  void constraintFIP(UpwardPlanRep &UPR,
121  List<edge> &origEdges,
122  EdgeArray<int> &cost,
123  edge e_orig,
124  SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, true); }
125 
127  void getPath(UpwardPlanRep &UPR,
128  List<edge> &origEdges,
129  EdgeArray<int> &cost,
130  edge e_orig,
131  SList<adjEntry> &path,
132  bool heuristic);
133 
134 
136  void markUp(const Graph &G, node v, EdgeArray<bool> &markedEdges);
137 
138 
140  void markDown(const Graph &G, node v, EdgeArray<bool> &markedEdges);
141 
143  void feasibleEdges(UpwardPlanRep &UPR,
144  face f, // current face
145  adjEntry adj, // current adjEntry, right face muss be f
146  EdgeArray<bool> &locked, // we compute the dyn. locked edges on the fly with respect to e
147  List<adjEntry> &feasible, // the list of feasible edges in f with respect to e
148  bool heuristic);
149 
151  bool isConstraintFeasible(UpwardPlanRep &UPR,
152  const List<edge> &orig_edges,
153  edge e_orig,
154  adjEntry adjCurrent,
155  adjEntry adjNext, // the next adjEntry of the current insertion path
156  EdgeArray<adjEntry> &predAdj //Array to reconstruction the insertion path
157  );
158 
159 
161  bool isConstraintFeasible(UpwardPlanRep &UPR,
162  List<edge> &origEdges,
163  edge e_orig,
164  SList<adjEntry> &path);
165 
166 
167 };
168 
169 } // end namespace ogdf
170 
171 #endif