Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ClusterPlanarity.h
Go to the documentation of this file.
1
33#pragma once
34
35#include <ogdf/basic/Module.h>
41
42namespace ogdf {
43
45
49public:
52
56 enum class solmeth { Fallback, New };
57
60 : m_heuristicLevel(1)
61 , m_heuristicRuns(1)
62 , m_heuristicOEdgeBound(0.4)
63 , m_heuristicNPermLists(5)
64 , m_kuratowskiIterations(10)
65 , m_subdivisions(10)
66 , m_kSupportGraphs(10)
67 , m_kuratowskiHigh(0.8)
68 , m_kuratowskiLow(0.8)
69 , m_perturbation(false)
70 , m_branchingGap(0.4)
71 , m_time("00:20:00")
72 , m_pricing(false)
73 , m_numAddVariables(15)
74 , m_strongConstraintViolation(0.3)
75 , m_strongVariableViolation(0.3)
76 , m_solmeth(solmeth::New)
77 , m_optStatus(abacus::Master::STATUS::Unprocessed)
78 , m_totalTime(-1.0)
79 , m_heurTime(-1.0)
80 , m_lpTime(-1.0)
81 , m_lpSolverTime(-1.0)
82 , m_sepTime(-1.0)
83 , m_totalWTime(-1.0)
84 , m_numCCons(-1)
85 , m_numKCons(-1)
86 , m_numLPs(-1)
87 , m_numBCs(-1)
88 , m_numSubSelected(-1)
89 , m_numVars(-1)
90 , m_portaOutput(false)
91 , m_defaultCutPool(true)
94#endif
95 {
96 }
97
98 //destruction
100
104
106 virtual bool isClusterPlanar(const ClusterGraph& CG) override;
107
108 //setter methods for the module parameters
109 void setHeuristicLevel(int i) { m_heuristicLevel = i; }
110
111 void setHeuristicRuns(int i) { m_heuristicRuns = i; }
112
113 void setHeuristicBound(double d) { m_heuristicOEdgeBound = d; }
114
115 void setNumberOfPermutations(int i) { m_heuristicNPermLists = i; }
116
117 void setNumberOfKuraIterations(int i) { m_kuratowskiIterations = i; }
118
119 void setNumberOfSubDivisions(int i) { m_subdivisions = i; }
120
121 void setNumberOfSupportGraphs(int i) { m_kSupportGraphs = i; }
122
123 void setUpperRounding(double d) { m_kuratowskiHigh = d; }
124
125 void setLowerRounding(double d) { m_kuratowskiLow = d; }
126
127 void setPerturbation(bool b) { m_perturbation = b; }
128
129 void setBranchingGap(double d) { m_branchingGap = d; }
130
131 void setTimeLimit(string s) { m_time = s.c_str(); }
132
133 void setPortaOutput(bool b) { m_portaOutput = b; }
134
135 void setPricing(bool b) { m_pricing = b; }
136
137 void setNumAddVariables(int n) { m_numAddVariables = n; }
138
139 void setStrongConstraintViolation(double d) { m_strongConstraintViolation = d; }
140
141 void setStrongVariableViolation(double d) { m_strongVariableViolation = d; }
142
145 bool& useDefaultCutPool() { return m_defaultCutPool; }
146
147 //getter methods for results
148 abacus::Master::STATUS getOptStatus() { return m_optStatus; }
149
150 double getTotalTime() { return m_totalTime; }
151
152 double getHeurTime() { return m_heurTime; }
153
154 double getLPTime() { return m_lpTime; }
155
156 double getLPSolverTime() { return m_lpSolverTime; }
157
158 double getSeparationTime() { return m_sepTime; }
159
160 double getTotalWTime() { return m_totalWTime; }
161
163 int getNumCCons() { return m_numCCons; }
164
166 int getNumKCons() { return m_numKCons; }
167
169 int getNumLPs() { return m_numLPs; }
170
172 int getNumBCs() { return m_numBCs; }
173
175 int getNumSubSelected() { return m_numSubSelected; }
176
178 int getNumVars() { return m_numVars; }
179
181 void writeFeasible(const char* filename, CP_MasterBase& master, abacus::Master::STATUS& status);
182#ifdef OGDF_DEBUG
183 bool getSolByHeuristic() { return m_solByHeuristic; }
184#endif
185
186 solmeth& solutionMethod() { return m_solmeth; }
187
188protected:
189 // Performs a c-planarity test on CG.
190 virtual bool doTest(const ClusterGraph& CG) override;
191
192 //as above, on success also returns the set of edges that were
193 //added to construct a completely connected planar graph.
194 virtual bool doTest(const ClusterGraph& G, NodePairs& addedEdges);
195
196 // Performs a c-planarity test using only a reduced set
197 // of allowed extension edges, returns c-planarity status
198#if 0
199 virtual bool doFastTest(const ClusterGraph &G);
200#endif
201
202 double getDoubleTime(const Stopwatch& act) {
203 int64_t tempo = act.centiSeconds() + 100 * act.seconds() + 6000 * act.minutes()
204 + 360000 * act.hours();
205 return ((double)tempo) / 100.0;
206 }
207
210
211private:
212 //Abacus Master class settings in order of appearance
213 int m_heuristicLevel, m_heuristicRuns;
215 int m_heuristicNPermLists, m_kuratowskiIterations;
216 int m_subdivisions, m_kSupportGraphs;
217 double m_kuratowskiHigh, m_kuratowskiLow;
220 string m_time;
221 bool m_pricing; //<! Decides if pricing is used
225
227
228 const char* getPortaFileName() { return "porta.poi"; }
229
230 const char* getIeqFileName() { return "porta.ieq"; }
231
232 int maxConLength() { return 1024; }
233
234 void outputCons(std::ofstream& os,
237
238 //results
239 abacus::Master::STATUS m_optStatus; //<! Status of optimization, returned from abacus
240 double m_totalTime; //<! Total computation time, returned from abacus
241 double m_heurTime; //<! Time spent in heuristic, returned from abacus
242 double m_lpTime; //<! Cpu time spent in members of the LP-interface, returned from abacus
243 double m_lpSolverTime; //<! Cpu time required by the LP solver, returned from abacus
244 double m_sepTime; //<! Cpu time spent in the separation of cutting planes, returned from abacus
245 double m_totalWTime; //<! Total wall clock time, returned from abacus
246 int m_numCCons; //<! Number of added connectivity constraints
247 int m_numKCons; //<! Number of added kuratowski constraints
248 int m_numLPs; //<! The number of optimized linear programs (LP-relax.).
249 int m_numBCs; //<! The number of generated subproblems.
250 int m_numSubSelected; //<! The number of subproblems selected by ABACUS.
251 int m_numVars; //<! The number of global variables.
252 bool m_portaOutput; //<! If set to true, output for PORTA in ieq format is generated.
253 bool m_defaultCutPool; //<! Passed through to master
254#ifdef OGDF_DEBUG
255 bool m_solByHeuristic;
256#endif
257};
258
259}
Declaration of the CPlanarityMaster class for the Branch&Cut algorithm for c-planarity testing via an...
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
Declaration of ClusterPlanarModule which implements a c-planarity test.
Declares base class for all module types.
Declares base class for modules with timeout functionality.
Includes Abacus.
STATUS
The various statuses of the optimization process.
Definition master.h:77
Standard pools.
Representation of clusters in a clustered graph.
Representation of clustered graphs.
C-planarity testing via completely connected graph extension.
void writeFeasible(const char *filename, CP_MasterBase &master, abacus::Master::STATUS &status)
Writes feasible solutions as a file in PORTA format.
int getNumSubSelected()
Returns number of subproblems selected by ABACUS.
virtual bool doTest(const ClusterGraph &G, NodePairs &addedEdges)
abacus::Master::STATUS m_optStatus
void setUpperRounding(double d)
void setNumberOfKuraIterations(int i)
int getNumKCons()
Returns number of Kuratowski constraints added during computation.
void setNumberOfSupportGraphs(int i)
void setNumberOfSubDivisions(int i)
bool & useDefaultCutPool()
Use default abacus master cut pool or dedicated connectivity and kuratowski cut pools.
void setNumberOfPermutations(int i)
void setHeuristicBound(double d)
double getDoubleTime(const Stopwatch &act)
void outputCons(std::ofstream &os, abacus::StandardPool< abacus::Constraint, abacus::Variable > *connCon, abacus::StandardPool< abacus::Variable, abacus::Constraint > *stdVar)
ClusterPlanarity()
Construction.
void setStrongConstraintViolation(double d)
void getBottomUpClusterList(const cluster c, List< cluster > &theList)
Stores clusters in subtree at c in bottom up order in theList.
virtual bool isClusterPlanar(const ClusterGraph &CG) override
Returns c-planarity status of CG.
void setBranchingGap(double d)
int getNumVars()
Returns number of global variables. Todo: Real number from ABACUS.
const char * getPortaFileName()
void setLowerRounding(double d)
const char * getIeqFileName()
int getNumCCons()
Returns number of connectivity constraints added during computation.
bool isClusterPlanar(const ClusterGraph &CG, NodePairs &addedEdges)
Computes a set of edges that augments the subgraph to be completely connected and returns c-planarity...
void setStrongVariableViolation(double d)
solmeth
Solution method, fallback to old version (allowing all extension edges, based on c-planar subgraph co...
solmeth m_solmeth
Solution method, see description of solmeth.
int getNumLPs()
Returns number of optimized LPs (only LP-relaxations)
int getNumBCs()
Returns number of generated LPs.
abacus::Master::STATUS getOptStatus()
virtual bool doTest(const ClusterGraph &CG) override
Performs a c-planarity test on CG.
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Realizes a stopwatch for measuring elapsed time.
Definition Stopwatch.h:42
int64_t hours() const
Returns the currently elapsed time in hours.
Definition Stopwatch.h:123
int64_t centiSeconds() const
Returns the currently elapsed time in 1/100-seconds.
Definition Stopwatch.h:102
int64_t seconds() const
Returns the currently elapsed time in seconds.
Definition Stopwatch.h:109
int64_t minutes() const
Returns the currently elapsed time in minutes.
Definition Stopwatch.h:116
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.