Open
Graph Drawing
Framework

  v.2012.07
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

MMVariableEmbeddingInserter.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2583 $
3  *
4  * last checkin:
5  * $Author: gutwenger $
6  * $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
7  ***************************************************************/
8 
43 #ifdef _MSC_VER
44 #pragma once
45 #endif
46 
47 #ifndef OGDF_MM_VARIABLE_EMBEDDING_INSERTER_H
48 #define OGDF_MM_VARIABLE_EMBEDDING_INSERTER_H
49 
50 
51 
52 #include <ogdf/module/MMEdgeInsertionModule.h>
53 #include <ogdf/basic/CombinatorialEmbedding.h>
54 #include <ogdf/basic/FaceArray.h>
55 #include <ogdf/basic/tuples.h>
56 
57 
58 
59 namespace ogdf {
60 
61 class OGDF_EXPORT NodeSet;
62 class OGDF_EXPORT StaticPlanarSPQRTree;
63 
64 
66 class OGDF_EXPORT MMVariableEmbeddingInserter : public MMEdgeInsertionModule
67 {
68 public:
70  MMVariableEmbeddingInserter();
71 
72  // destruction
73  virtual ~MMVariableEmbeddingInserter() { }
74 
75 
77  void removeReinsert(RemoveReinsertType rrOption) {
78  m_rrOption = rrOption;
79  }
80 
82  RemoveReinsertType removeReinsert() const {
83  return m_rrOption;
84  }
85 
86 
88 
93  void percentMostCrossed(double percent) {
94  m_percentMostCrossed = percent;
95  }
96 
98  double percentMostCrossed() const {
99  return m_percentMostCrossed;
100  }
101 
102 
103 private:
104  class Block;
105  class ExpandedSkeleton;
106 
107  typedef PlanRepExpansion::Crossing Crossing;
108 
109  struct AnchorNodeInfo {
110  AnchorNodeInfo() { m_adj_1 = m_adj_2 = 0; }
111  AnchorNodeInfo(adjEntry adj) {
112  m_adj_1 = adj;
113  m_adj_2 = 0;
114  }
115  AnchorNodeInfo(adjEntry adj_1, adjEntry adj_2) {
116  m_adj_1 = adj_1;
117  m_adj_2 = adj_2;
118  }
119 
120  adjEntry m_adj_1;
121  adjEntry m_adj_2;
122  };
123 
124  enum PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 };
125 
126  struct Paths {
127  Paths() :
128  m_addPartLeft(3), m_addPartRight(3),
129  m_paths(3),
130  m_src(0,2,0), m_tgt(0,2,0),
131  m_pred(0,2,0)
132  { }
133 
134  Array<SList<adjEntry> > m_addPartLeft;
135  Array<SList<adjEntry> > m_addPartRight;
136  Array<List<Crossing> > m_paths;
137  Array<AnchorNodeInfo> m_src;
138  Array<AnchorNodeInfo> m_tgt;
139  Array<int> m_pred;
140  };
141 
151  ReturnType doCall(
152  PlanRepExpansion &PG,
153  const List<edge> &origEdges,
154  const EdgeArray<bool> *forbiddenEdgeOrig);
155 
164  void collectAnchorNodes(
165  node v,
166  NodeSet &nodes,
167  const PlanRepExpansion::NodeSplit *nsParent) const;
168 
177  void findSourcesAndTargets(
178  node src, node tgt,
179  NodeSet &sources,
180  NodeSet &targets) const;
181 
188  void anchorNodes(
189  node vOrig,
190  NodeSet &nodes) const;
191 
192  static node commonDummy(
193  NodeSet &sources,
194  NodeSet &targets);
195 
205  void insert(List<Crossing> &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd);
206 
207  node prepareAnchorNode(
208  const AnchorNodeInfo &anchor,
209  node vOrig,
210  bool isSrc,
211  edge &eExtra);
212 
213  void preprocessInsertionPath(
214  const AnchorNodeInfo &srcInfo,
215  const AnchorNodeInfo &tgtInfo,
216  node srcOrig,
217  node tgtOrig,
218  node &src,
219  node &tgt,
220  edge &eSrc,
221  edge &eTgt);
222 
223  node preparePath(
224  node vAnchor,
225  adjEntry adjPath,
226  bool bOrigEdge,
227  node vOrig);
228 
229  void findPseudos(
230  node vDummy,
231  adjEntry adjSrc,
232  AnchorNodeInfo &infoSrc,
233  SListPure<node> &pseudos);
234 
235  void insertWithCommonDummy(
236  edge eOrig,
237  node vDummy,
238  node &src,
239  node &tgt);
240 
250  bool dfsVertex(node v,
251  int parent,
252  List<Crossing> &eip,
253  AnchorNodeInfo &vStart,
254  AnchorNodeInfo &vEnd);
255 
266  bool dfsBlock(int i,
267  node parent,
268  node &repS,
269  List<Crossing> &eip,
270  AnchorNodeInfo &vStart,
271  AnchorNodeInfo &vEnd);
272 
273  bool pathSearch(node v, edge parent, const Block &BC, List<edge> &path);
274 
283  void blockInsert(
284  Block &BC,
285  List<Crossing> &L,
286  AnchorNodeInfo &srcInfo,
287  AnchorNodeInfo &tgtInfo);
288 
289  void buildSubpath(
290  node v,
291  edge eIn,
292  edge eOut,
293  Paths &paths,
294  bool &bPathToEdge,
295  bool &bPathToSrc,
296  bool &bPathToTgt,
297  ExpandedSkeleton &Exp);
298 
299  void contractSplitIfReq(node u);
300  void convertDummy(
301  node u,
302  node vOrig,
303  PlanRepExpansion::nodeSplit ns_0);
304 
305  void writeEip(const List<Crossing> &eip);
306 
307  RemoveReinsertType m_rrOption;
308  double m_percentMostCrossed;
309 
310  PlanRepExpansion *m_pPG;
311 
312  NodeSet *m_pSources;
313  NodeSet *m_pTargets;
314 
315  NodeArray<SList<int> > m_compV;
316  Array<SList<node> > m_nodeB;
317  Array<SList<edge> > m_edgeB;
318  NodeArray<node> m_GtoBC;
319 
320  bool m_conFinished;
321  const EdgeArray<bool> *m_forbiddenEdgeOrig;
322 };
323 
324 } // end namespace ogdf
325 
326 #endif