Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MaximumCPlanarSubgraph.h
Go to the documentation of this file.
1
33#pragma once
34
35#include <ogdf/basic/Module.h>
41
42#include <chrono>
43#include <sstream>
44
45namespace ogdf {
46
48
52public:
55
58 : m_heuristicLevel(1)
59 , m_heuristicRuns(1)
60 , m_heuristicOEdgeBound(0.4)
61 , m_heuristicNPermLists(5)
62 , m_kuratowskiIterations(10)
63 , m_subdivisions(10)
64 , m_kSupportGraphs(10)
65 , m_kuratowskiHigh(0.8)
66 , m_kuratowskiLow(0.8)
67 , m_perturbation(false)
68 , m_branchingGap(0.4)
69 , m_time("00:20:00")
70 , m_pricing(false)
71 , m_checkCPlanar(false)
72 , m_numAddVariables(15)
73 , m_strongConstraintViolation(0.3)
74 , m_strongVariableViolation(0.3)
75 , m_totalTime(-1.0)
76 , m_heurTime(-1.0)
77 , m_lpTime(-1.0)
78 , m_lpSolverTime(-1.0)
79 , m_sepTime(-1.0)
80 , m_totalWTime(-1.0)
81 , m_numCCons(-1)
82 , m_numKCons(-1)
83 , m_numLPs(-1)
84 , m_numBCs(-1)
85 , m_numSubSelected(-1)
86 , m_numVars(-1)
87 , m_portaOutput(false)
88 , m_defaultCutPool(true)
91#endif
92 {
93 }
94
95 //destruction
97
106 /*
107 * @param ClusterGraph the graph that we want to compute a subgraph of
108 * @param pCost the cost of each edge or \c nullptr if edges should have uniform cost
109 * @param delEdges contains all deleted edges after the call
110 * @param addedEdges the set of edges that makes the subgraph connected
111 */
113 List<edge>& delEdges, NodePairs& addedEdges) {
114 return doCall(G, pCost, delEdges, addedEdges);
115 }
116
117 //setter methods for the module parameters
118 void setHeuristicLevel(int i) { m_heuristicLevel = i; }
119
120 void setHeuristicRuns(int i) { m_heuristicRuns = i; }
121
122 void setHeuristicBound(double d) { m_heuristicOEdgeBound = d; }
123
124 void setNumberOfPermutations(int i) { m_heuristicNPermLists = i; }
125
126 void setNumberOfKuraIterations(int i) { m_kuratowskiIterations = i; }
127
128 void setNumberOfSubDivisions(int i) { m_subdivisions = i; }
129
130 void setNumberOfSupportGraphs(int i) { m_kSupportGraphs = i; }
131
132 void setUpperRounding(double d) { m_kuratowskiHigh = d; }
133
134 void setLowerRounding(double d) { m_kuratowskiLow = d; }
135
136 void setPerturbation(bool b) { m_perturbation = b; }
137
138 void setBranchingGap(double d) { m_branchingGap = d; }
139
140 void setTimeLimit(string s) { m_time = s.c_str(); }
141
142 void setTimeLimit(std::chrono::milliseconds milliSec) {
143 // format string only supports seconds
144 OGDF_ASSERT(milliSec.count() >= 1000);
145 // transform to format string
146 std::chrono::milliseconds remaining(milliSec);
147 auto h = std::chrono::duration_cast<std::chrono::hours>(remaining);
148 remaining -= h;
149 auto m = std::chrono::duration_cast<std::chrono::minutes>(remaining);
150 remaining -= m;
151 auto s = std::chrono::duration_cast<std::chrono::seconds>(remaining);
152 std::stringstream ss;
153 ss << h.count() << ":" << m.count() << ":" << s.count();
154 setTimeLimit(ss.str());
155 }
156
157 void setPortaOutput(bool b) { m_portaOutput = b; }
158
159 void setPricing(bool b) { m_pricing = b; }
160
161 void setCheckCPlanar(bool b) { m_checkCPlanar = b; }
162
163 void setNumAddVariables(int n) { m_numAddVariables = n; }
164
165 void setStrongConstraintViolation(double d) { m_strongConstraintViolation = d; }
166
167 void setStrongVariableViolation(double d) { m_strongVariableViolation = d; }
168
171 bool& useDefaultCutPool() { return m_defaultCutPool; }
172
173 //getter methods for results
174 double getTotalTime() { return m_totalTime; }
175
176 double getHeurTime() { return m_heurTime; }
177
178 double getLPTime() { return m_lpTime; }
179
180 double getLPSolverTime() { return m_lpSolverTime; }
181
182 double getSeparationTime() { return m_sepTime; }
183
184 double getTotalWTime() { return m_totalWTime; }
185
187 int getNumCCons() { return m_numCCons; }
188
190 int getNumKCons() { return m_numKCons; }
191
193 int getNumLPs() { return m_numLPs; }
194
196 int getNumBCs() { return m_numBCs; }
197
199 int getNumSubSelected() { return m_numSubSelected; }
200
202 int getNumVars() { return m_numVars; }
203
205 void writeFeasible(const char* filename, MaxCPlanarMaster& master,
206 abacus::Master::STATUS& status);
207#ifdef OGDF_DEBUG
208 bool getSolByHeuristic() { return m_solByHeuristic; }
209#endif
210
211
212protected:
218 List<edge>& delEdges) override {
220 return doCall(G, pCost, delEdges, addEdges);
221 }
222
223 //as above, also returns the set of edges that were
224 //added to construct a completely connected planar
225 //graph that contains the computed c-planar subgraph
227 List<edge>& delEdges, NodePairs& addedEdges);
228
229 double getDoubleTime(const Stopwatch& act) {
230 int64_t tempo = act.centiSeconds() + 100 * act.seconds() + 6000 * act.minutes()
231 + 360000 * act.hours();
232 return ((double)tempo) / 100.0;
233 }
234
237
238private:
239 //Abacus Master class settings in order of appearance
240 int m_heuristicLevel, m_heuristicRuns;
242 int m_heuristicNPermLists, m_kuratowskiIterations;
243 int m_subdivisions, m_kSupportGraphs;
244 double m_kuratowskiHigh, m_kuratowskiLow;
247 string m_time;
248 bool m_pricing; //<! Decides if pricing is used
249 bool m_checkCPlanar; //<! If set to true, only c-planarity is checked
253
254 const char* getPortaFileName() { return "porta.poi"; }
255
256 const char* getIeqFileName() { return "porta.ieq"; }
257
258 int maxConLength() { return 1024; }
259
260 void outputCons(std::ofstream& os,
263
264 //results
265 double m_totalTime; //<! Total computation time, returned from abacus
266 double m_heurTime; //<! Time spent in heuristic, returned from abacus
267 double m_lpTime; //<! Cpu time spent in members of the LP-interface, returned from abacus
268 double m_lpSolverTime; //<! Cpu time required by the LP solver, returned from abacus
269 double m_sepTime; //<! Cpu time spent in the separation of cutting planes, returned from abacus
270 double m_totalWTime; //<! Total wall clock time, returned from abacus
271 int m_numCCons; //<! Number of added connectivity constraints
272 int m_numKCons; //<! Number of added kuratowski constraints
273 int m_numLPs; //<! The number of optimized linear programs (LP-relax.).
274 int m_numBCs; //<! The number of generated subproblems.
275 int m_numSubSelected; //<! The number of subproblems selected by ABACUS.
276 int m_numVars; //<! The number of global variables.
277 bool m_portaOutput; //<! If set to true, output for PORTA in ieq format is generated.
278 bool m_defaultCutPool; //<! Passed through to master
279#ifdef OGDF_DEBUG
280 bool m_solByHeuristic;
281#endif
282};
283
284}
Declaration of an interface for c-planar subgraph algorithms.
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
Declaration of the master class for the Branch&Cut algorithm for the Maximum C-Planar SubGraph proble...
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.
Interface of algorithms for the computation of c-planar subgraphs.
Representation of clusters in a clustered graph.
Representation of clustered graphs.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Exact computation of a maximum c-planar subgraph.
int getNumSubSelected()
Returns number of subproblems selected by ABACUS.
bool & useDefaultCutPool()
Use default abacus master cut pool or dedicated connectivity and kuratowski cut pools.
int getNumBCs()
Returns number of generated LPs.
virtual ReturnType doCall(const ClusterGraph &G, const EdgeArray< double > *pCost, List< edge > &delEdges, NodePairs &addedEdges)
ReturnType callAndConnect(const ClusterGraph &G, const EdgeArray< double > *pCost, List< edge > &delEdges, NodePairs &addedEdges)
Computes set of edges delEdges, which have to be deleted in order to get a c-planar subgraph and also...
int getNumLPs()
Returns number of optimized LPs (only LP-relaxations)
void getBottomUpClusterList(const cluster c, List< cluster > &theList)
Stores clusters in subtree at c in bottom up order in theList.
int getNumVars()
Returns number of global variables. Todo: Real number from ABACUS.
void outputCons(std::ofstream &os, abacus::StandardPool< abacus::Constraint, abacus::Variable > *connCon, abacus::StandardPool< abacus::Variable, abacus::Constraint > *stdVar)
int getNumKCons()
Returns number of Kuratowski constraints added during computation.
void writeFeasible(const char *filename, MaxCPlanarMaster &master, abacus::Master::STATUS &status)
Writes feasible solutions as a file in PORTA format.
void setTimeLimit(std::chrono::milliseconds milliSec)
double getDoubleTime(const Stopwatch &act)
int getNumCCons()
Returns number of connectivity constraints added during computation.
virtual ReturnType doCall(const ClusterGraph &G, const EdgeArray< double > *pCost, List< edge > &delEdges) override
Computes a maximum c-planar subgraph, returns the set of edges that have to be deleted in delEdges if...
ReturnType
The return type of a module.
Definition Module.h:50
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
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.