Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

SubgraphUpwardPlanarizer.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <memory>
36 #include <ogdf/upward/FUPSModule.h>
40 #include <ogdf/upward/FUPSSimple.h>
44 
45 namespace ogdf {
46 
67 {
68 
69 public:
72  {
73  m_runs = 1;
74  //set default module
75  m_subgraph.reset(new FUPSSimple());
76  m_inserter.reset(new FixedEmbeddingUpwardEdgeInserter());
77  m_acyclicMod.reset(new GreedyCycleRemoval());
78  }
79 
81  void setSubgraph(FUPSModule *FUPS) {
82  m_subgraph.reset(FUPS);
83  }
84 
87  m_inserter.reset(pInserter);
88  }
89 
92  m_acyclicMod.reset(acyclicMod);
93  }
94 
95  int runs() {return m_runs;}
96  void runs(int n) {m_runs = n;}
97 
98 protected:
99 
100  virtual ReturnType doCall(UpwardPlanRep &UPR,
101  const EdgeArray<int> &cost,
102  const EdgeArray<bool> &forbid) override;
103 
104  std::unique_ptr<FUPSModule> m_subgraph;
105  std::unique_ptr<UpwardEdgeInserterModule> m_inserter;
106  std::unique_ptr<AcyclicSubgraphModule> m_acyclicMod;
107  int m_runs;
108 
109 private:
110 
111  void constructComponentGraphs(BCTree &BC, NodeArray<GraphCopy> &biComps);
112 
114  void dfsMerge(const GraphCopy &GC,
115  BCTree &BC,
116  NodeArray<GraphCopy> &biComps,
118  UpwardPlanRep &UPR_res,
119  node parent_BC,
120  node current_BC,
121  NodeArray<bool> &nodesDone);
122 
123 
125  void merge(const GraphCopy &GC,
126  UpwardPlanRep &UPR_res,
127  const GraphCopy &block,
128  UpwardPlanRep &UPR);
129 };
130 
131 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
GreedyCycleRemoval.h
Declaration of class GeedyCycleRemoval.
ogdf::BCTree
Static BC-trees.
Definition: BCTree.h:55
ogdf::SubgraphUpwardPlanarizer::m_inserter
std::unique_ptr< UpwardEdgeInserterModule > m_inserter
The edge insertion module.
Definition: SubgraphUpwardPlanarizer.h:105
FixedEmbeddingUpwardEdgeInserter.h
declaration of class FixedEmbeddingInserterOld
ogdf::SubgraphUpwardPlanarizer
Takes an acyclic connected non-upward-planar graph and planarizes it, i.e., we obtain an upward-plana...
Definition: SubgraphUpwardPlanarizer.h:66
ogdf::GreedyCycleRemoval
Greedy algorithm for computing a maximal acyclic subgraph.
Definition: GreedyCycleRemoval.h:44
ogdf::SubgraphUpwardPlanarizer::setAcyclicSubgraphModule
void setAcyclicSubgraphModule(AcyclicSubgraphModule *acyclicMod)
Sets the module option for acyclic subgraph module.
Definition: SubgraphUpwardPlanarizer.h:91
UpwardEdgeInserterModule.h
Declaration of interface for edge insertion algorithms.
UpwardPlanRep.h
Declaration of a base class for planar representations of graphs and cluster graphs.
ogdf::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:255
ogdf::SubgraphUpwardPlanarizer::runs
int runs()
Definition: SubgraphUpwardPlanarizer.h:95
ogdf::FixedEmbeddingUpwardEdgeInserter
Edge insertion module that inserts each edge optimally into a fixed embedding.
Definition: FixedEmbeddingUpwardEdgeInserter.h:41
FUPSSimple.h
Declaration of the FUPSSimple.
ogdf::SubgraphUpwardPlanarizer::m_runs
int m_runs
Definition: SubgraphUpwardPlanarizer.h:107
ogdf::SubgraphUpwardPlanarizer::setSubgraph
void setSubgraph(FUPSModule *FUPS)
Sets the module option for the computation of the feasible upward planar subgraph.
Definition: SubgraphUpwardPlanarizer.h:81
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::SubgraphUpwardPlanarizer::setInserter
void setInserter(UpwardEdgeInserterModule *pInserter)
Sets the module option for the edge insertion module.
Definition: SubgraphUpwardPlanarizer.h:86
ogdf::EdgeArray< int >
AcyclicSubgraphModule.h
Declaration of interface for acyclic subgraph algorithms.
BCTree.h
Declaration of class BCTree.
ogdf::UpwardEdgeInserterModule
Definition: UpwardEdgeInserterModule.h:39
ogdf::FUPSSimple
Definition: FUPSSimple.h:39
ogdf::SubgraphUpwardPlanarizer::m_acyclicMod
std::unique_ptr< AcyclicSubgraphModule > m_acyclicMod
The acyclic subgraph module.
Definition: SubgraphUpwardPlanarizer.h:106
ogdf::SubgraphUpwardPlanarizer::runs
void runs(int n)
Definition: SubgraphUpwardPlanarizer.h:96
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
FUPSModule.h
Declaration of Feasible Upward Planar Subgraph (FUPS) Module, an interface for subgraph computation.
ogdf::AcyclicSubgraphModule
Base class of algorithms for computing a maximal acyclic subgraph.
Definition: AcyclicSubgraphModule.h:43
ogdf::SubgraphUpwardPlanarizer::SubgraphUpwardPlanarizer
SubgraphUpwardPlanarizer()
Creates an instance of subgraph planarizer.
Definition: SubgraphUpwardPlanarizer.h:71
UpwardPlanarizerModule.h
Declaration of UpwardPlanarizer Module, an interface for upward planarization algorithms.
ogdf::FUPSModule
Interface for feasible upward planar subgraph algorithms.
Definition: FUPSModule.h:43
ogdf::UpwardPlanarizerModule
Interface for upward planarization algorithms.
Definition: UpwardPlanarizerModule.h:44
ogdf::UpwardPlanRep
Upward planarized representations (of a connected component) of a graph.
Definition: UpwardPlanRep.h:51
ogdf::SubgraphUpwardPlanarizer::m_subgraph
std::unique_ptr< FUPSModule > m_subgraph
The upward planar subgraph algorithm.
Definition: SubgraphUpwardPlanarizer.h:104
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169