Open
Graph Drawing
Framework

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

SubgraphUpwardPlanarizer.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 #ifndef OGDF_SUBGRAPH_UPWARD_PLANARIZER_H
44 #define OGDF_SUBGRAPH_UPWARD_PLANARIZER_H
45 
46 
47 #include <ogdf/basic/ModuleOption.h>
48 #include <ogdf/module/AcyclicSubgraphModule.h>
49 #include <ogdf/module/FUPSModule.h>
50 #include <ogdf/module/UpwardEdgeInserterModule.h>
51 #include <ogdf/module/UpwardPlanarizerModule.h>
52 #include <ogdf/upward/UpwardPlanRep.h>
53 #include <ogdf/upward/FUPSSimple.h>
54 #include <ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h>
55 #include <ogdf/decomposition/BCTree.h>
56 #include <ogdf/module/AcyclicSubgraphModule.h>
57 #include <ogdf/layered/GreedyCycleRemoval.h>
58 
59 
60 namespace ogdf
61 {
62 
63 
64 class OGDF_EXPORT SubgraphUpwardPlanarizer : public UpwardPlanarizerModule
65 {
66 
67 public:
69  SubgraphUpwardPlanarizer()
70  {
71  m_runs = 1;
72  //set default module
73  m_subgraph.set(new FUPSSimple());
74  m_inserter.set(new FixedEmbeddingUpwardEdgeInserter());
75  m_acyclicMod.set(new GreedyCycleRemoval());
76  }
77 
79  void setSubgraph(FUPSModule *FUPS) {
80  m_subgraph.set(FUPS);
81  }
82 
84  void setInserter(UpwardEdgeInserterModule *pInserter) {
85  m_inserter.set(pInserter);
86  }
87 
89  void setAcyclicSubgraphModule(AcyclicSubgraphModule *acyclicMod) {
90  m_acyclicMod.set(acyclicMod);
91  }
92 
93  int runs() {return m_runs;}
94  void runs(int n) {m_runs = n;}
95 
96 protected:
97 
98  virtual ReturnType doCall(UpwardPlanRep &UPR,
99  const EdgeArray<int> &cost,
100  const EdgeArray<bool> &forbid);
101 
102  ModuleOption<FUPSModule> m_subgraph;
103  ModuleOption<UpwardEdgeInserterModule> m_inserter;
104  ModuleOption<AcyclicSubgraphModule> m_acyclicMod;
105  int m_runs;
106 
107 private:
108 
109  void constructComponentGraphs(BCTree &BC, NodeArray<GraphCopy> &biComps);
110 
112  void dfsMerge(const GraphCopy &GC,
113  BCTree &BC,
114  NodeArray<GraphCopy> &biComps,
115  NodeArray<UpwardPlanRep> &uprs,
116  UpwardPlanRep &UPR_res,
117  node parent_BC,
118  node current_BC,
119  NodeArray<bool> &nodesDone);
120 
121 
123  void merge(const GraphCopy &GC,
124  UpwardPlanRep &UPR_res,
125  const GraphCopy &block,
126  UpwardPlanRep &UPR
127  );
128 };
129 
130 }
131 
132 #endif