Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MaximumCPlanarSubgraph Class Reference

Exact computation of a maximum c-planar subgraph. More...

#include <ogdf/cluster/MaximumCPlanarSubgraph.h>

+ Inheritance diagram for ogdf::MaximumCPlanarSubgraph:

Public Types

using MaxCPlanarMaster = cluster_planarity::MaxCPlanarMaster
 
using NodePairs = List< NodePair >
 
- Public Types inherited from ogdf::Module
enum  ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::Error }
 The return type of a module. More...
 

Public Member Functions

 MaximumCPlanarSubgraph ()
 Construction. More...
 
 ~MaximumCPlanarSubgraph ()
 
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 returns a set of edges that augments the subgraph to be completely connected. For pure c-planarity testing, the computation can be sped up by setting setCheckCPlanar(2). Then, in case G is not c-planar, the list of deleted edges does not need to correspond to a valid solution, it just indicates the result. More...
 
double getHeurTime ()
 
double getLPSolverTime ()
 
double getLPTime ()
 
int getNumBCs ()
 Returns number of generated LPs. More...
 
int getNumCCons ()
 Returns number of connectivity constraints added during computation. More...
 
int getNumKCons ()
 Returns number of Kuratowski constraints added during computation. More...
 
int getNumLPs ()
 Returns number of optimized LPs (only LP-relaxations) More...
 
int getNumSubSelected ()
 Returns number of subproblems selected by ABACUS. More...
 
int getNumVars ()
 Returns number of global variables. Todo: Real number from ABACUS. More...
 
double getSeparationTime ()
 
double getTotalTime ()
 
double getTotalWTime ()
 
void setBranchingGap (double d)
 
void setCheckCPlanar (bool b)
 
void setHeuristicBound (double d)
 
void setHeuristicLevel (int i)
 
void setHeuristicRuns (int i)
 
void setLowerRounding (double d)
 
void setNumAddVariables (int n)
 
void setNumberOfKuraIterations (int i)
 
void setNumberOfPermutations (int i)
 
void setNumberOfSubDivisions (int i)
 
void setNumberOfSupportGraphs (int i)
 
void setPerturbation (bool b)
 
void setPortaOutput (bool b)
 
void setPricing (bool b)
 
void setStrongConstraintViolation (double d)
 
void setStrongVariableViolation (double d)
 
void setTimeLimit (std::chrono::milliseconds milliSec)
 
void setTimeLimit (string s)
 
void setUpperRounding (double d)
 
bool & useDefaultCutPool ()
 Use default abacus master cut pool or dedicated connectivity and kuratowski cut pools. More...
 
void writeFeasible (const char *filename, MaxCPlanarMaster &master, abacus::Master::STATUS &status)
 Writes feasible solutions as a file in PORTA format. More...
 
- Public Member Functions inherited from ogdf::CPlanarSubgraphModule
 CPlanarSubgraphModule ()
 Constructs a cplanar subgraph module. More...
 
virtual ~CPlanarSubgraphModule ()
 Destruction. More...
 
ReturnType call (const ClusterGraph &G, const EdgeArray< double > *pCost, List< edge > &delEdges)
 Computes set of edges delEdges, which have to be deleted in order to get a c-planar subgraph. More...
 
ReturnType call (const ClusterGraph &G, List< edge > &delEdges)
 Computes set of edges delEdges, which have to be deleted in order to get a c-planar subgraph. More...
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 
- Public Member Functions inherited from ogdf::Timeouter
 Timeouter ()
 timeout is turned of by default More...
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second) More...
 
 Timeouter (const Timeouter &t)
 
 Timeouter (double t)
 timeout is set to the given value (seconds) More...
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not More...
 
Timeouteroperator= (const Timeouter &t)
 
double timeLimit () const
 returns the current time limit for the call More...
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds) More...
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit. More...
 

Protected Member Functions

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 delEdges is empty on return, the clustered graph G is c-planar. More...
 
virtual ReturnType doCall (const ClusterGraph &G, const EdgeArray< double > *pCost, List< edge > &delEdges, NodePairs &addedEdges)
 
void getBottomUpClusterList (const cluster c, List< cluster > &theList)
 Stores clusters in subtree at c in bottom up order in theList. More...
 
double getDoubleTime (const Stopwatch &act)
 

Private Member Functions

const char * getIeqFileName ()
 
const char * getPortaFileName ()
 
int maxConLength ()
 
void outputCons (std::ofstream &os, abacus::StandardPool< abacus::Constraint, abacus::Variable > *connCon, abacus::StandardPool< abacus::Variable, abacus::Constraint > *stdVar)
 

Private Attributes

double m_branchingGap
 
bool m_checkCPlanar
 
bool m_defaultCutPool
 
int m_heuristicLevel
 
int m_heuristicNPermLists
 
double m_heuristicOEdgeBound
 
int m_heuristicRuns
 
double m_heurTime
 
int m_kSupportGraphs
 
double m_kuratowskiHigh
 
int m_kuratowskiIterations
 
double m_kuratowskiLow
 
double m_lpSolverTime
 
double m_lpTime
 
int m_numAddVariables
 
int m_numBCs
 
int m_numCCons
 
int m_numKCons
 
int m_numLPs
 
int m_numSubSelected
 
int m_numVars
 
bool m_perturbation
 
bool m_portaOutput
 
bool m_pricing
 
double m_sepTime
 
double m_strongConstraintViolation
 
double m_strongVariableViolation
 
int m_subdivisions
 
string m_time
 
double m_totalTime
 
double m_totalWTime
 

Additional Inherited Members

- Static Public Member Functions inherited from ogdf::Module
static bool isSolution (ReturnType ret)
 Returns true iff ret indicates that the module returned a feasible solution. More...
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit). More...
 

Detailed Description

Exact computation of a maximum c-planar subgraph.

Definition at line 53 of file MaximumCPlanarSubgraph.h.

Member Typedef Documentation

◆ MaxCPlanarMaster

◆ NodePairs

Constructor & Destructor Documentation

◆ MaximumCPlanarSubgraph()

ogdf::MaximumCPlanarSubgraph::MaximumCPlanarSubgraph ( )
inline

Construction.

Definition at line 60 of file MaximumCPlanarSubgraph.h.

◆ ~MaximumCPlanarSubgraph()

ogdf::MaximumCPlanarSubgraph::~MaximumCPlanarSubgraph ( )
inline

Definition at line 97 of file MaximumCPlanarSubgraph.h.

Member Function Documentation

◆ callAndConnect()

ReturnType ogdf::MaximumCPlanarSubgraph::callAndConnect ( const ClusterGraph G,
const EdgeArray< double > *  pCost,
List< edge > &  delEdges,
NodePairs addedEdges 
)
inline

Computes set of edges delEdges, which have to be deleted in order to get a c-planar subgraph and also returns a set of edges that augments the subgraph to be completely connected. For pure c-planarity testing, the computation can be sped up by setting setCheckCPlanar(2). Then, in case G is not c-planar, the list of deleted edges does not need to correspond to a valid solution, it just indicates the result.

Definition at line 113 of file MaximumCPlanarSubgraph.h.

◆ doCall() [1/2]

virtual ReturnType ogdf::MaximumCPlanarSubgraph::doCall ( const ClusterGraph G,
const EdgeArray< double > *  pCost,
List< edge > &  delEdges 
)
inlineoverrideprotectedvirtual

Computes a maximum c-planar subgraph, returns the set of edges that have to be deleted in delEdges if delEdges is empty on return, the clustered graph G is c-planar.

Implements ogdf::CPlanarSubgraphModule.

Definition at line 190 of file MaximumCPlanarSubgraph.h.

◆ doCall() [2/2]

virtual ReturnType ogdf::MaximumCPlanarSubgraph::doCall ( const ClusterGraph G,
const EdgeArray< double > *  pCost,
List< edge > &  delEdges,
NodePairs addedEdges 
)
protectedvirtual

◆ getBottomUpClusterList()

void ogdf::MaximumCPlanarSubgraph::getBottomUpClusterList ( const cluster  c,
List< cluster > &  theList 
)
protected

Stores clusters in subtree at c in bottom up order in theList.

◆ getDoubleTime()

double ogdf::MaximumCPlanarSubgraph::getDoubleTime ( const Stopwatch act)
inlineprotected

Definition at line 208 of file MaximumCPlanarSubgraph.h.

◆ getHeurTime()

double ogdf::MaximumCPlanarSubgraph::getHeurTime ( )
inline

Definition at line 159 of file MaximumCPlanarSubgraph.h.

◆ getIeqFileName()

const char* ogdf::MaximumCPlanarSubgraph::getIeqFileName ( )
inlineprivate

Definition at line 237 of file MaximumCPlanarSubgraph.h.

◆ getLPSolverTime()

double ogdf::MaximumCPlanarSubgraph::getLPSolverTime ( )
inline

Definition at line 161 of file MaximumCPlanarSubgraph.h.

◆ getLPTime()

double ogdf::MaximumCPlanarSubgraph::getLPTime ( )
inline

Definition at line 160 of file MaximumCPlanarSubgraph.h.

◆ getNumBCs()

int ogdf::MaximumCPlanarSubgraph::getNumBCs ( )
inline

Returns number of generated LPs.

Definition at line 171 of file MaximumCPlanarSubgraph.h.

◆ getNumCCons()

int ogdf::MaximumCPlanarSubgraph::getNumCCons ( )
inline

Returns number of connectivity constraints added during computation.

Definition at line 165 of file MaximumCPlanarSubgraph.h.

◆ getNumKCons()

int ogdf::MaximumCPlanarSubgraph::getNumKCons ( )
inline

Returns number of Kuratowski constraints added during computation.

Definition at line 167 of file MaximumCPlanarSubgraph.h.

◆ getNumLPs()

int ogdf::MaximumCPlanarSubgraph::getNumLPs ( )
inline

Returns number of optimized LPs (only LP-relaxations)

Definition at line 169 of file MaximumCPlanarSubgraph.h.

◆ getNumSubSelected()

int ogdf::MaximumCPlanarSubgraph::getNumSubSelected ( )
inline

Returns number of subproblems selected by ABACUS.

Definition at line 173 of file MaximumCPlanarSubgraph.h.

◆ getNumVars()

int ogdf::MaximumCPlanarSubgraph::getNumVars ( )
inline

Returns number of global variables. Todo: Real number from ABACUS.

Definition at line 175 of file MaximumCPlanarSubgraph.h.

◆ getPortaFileName()

const char* ogdf::MaximumCPlanarSubgraph::getPortaFileName ( )
inlineprivate

Definition at line 233 of file MaximumCPlanarSubgraph.h.

◆ getSeparationTime()

double ogdf::MaximumCPlanarSubgraph::getSeparationTime ( )
inline

Definition at line 162 of file MaximumCPlanarSubgraph.h.

◆ getTotalTime()

double ogdf::MaximumCPlanarSubgraph::getTotalTime ( )
inline

Definition at line 158 of file MaximumCPlanarSubgraph.h.

◆ getTotalWTime()

double ogdf::MaximumCPlanarSubgraph::getTotalWTime ( )
inline

Definition at line 163 of file MaximumCPlanarSubgraph.h.

◆ maxConLength()

int ogdf::MaximumCPlanarSubgraph::maxConLength ( )
inlineprivate

Definition at line 241 of file MaximumCPlanarSubgraph.h.

◆ outputCons()

void ogdf::MaximumCPlanarSubgraph::outputCons ( std::ofstream &  os,
abacus::StandardPool< abacus::Constraint, abacus::Variable > *  connCon,
abacus::StandardPool< abacus::Variable, abacus::Constraint > *  stdVar 
)
private

◆ setBranchingGap()

void ogdf::MaximumCPlanarSubgraph::setBranchingGap ( double  d)
inline

Definition at line 131 of file MaximumCPlanarSubgraph.h.

◆ setCheckCPlanar()

void ogdf::MaximumCPlanarSubgraph::setCheckCPlanar ( bool  b)
inline

Definition at line 149 of file MaximumCPlanarSubgraph.h.

◆ setHeuristicBound()

void ogdf::MaximumCPlanarSubgraph::setHeuristicBound ( double  d)
inline

Definition at line 123 of file MaximumCPlanarSubgraph.h.

◆ setHeuristicLevel()

void ogdf::MaximumCPlanarSubgraph::setHeuristicLevel ( int  i)
inline

Definition at line 121 of file MaximumCPlanarSubgraph.h.

◆ setHeuristicRuns()

void ogdf::MaximumCPlanarSubgraph::setHeuristicRuns ( int  i)
inline

Definition at line 122 of file MaximumCPlanarSubgraph.h.

◆ setLowerRounding()

void ogdf::MaximumCPlanarSubgraph::setLowerRounding ( double  d)
inline

Definition at line 129 of file MaximumCPlanarSubgraph.h.

◆ setNumAddVariables()

void ogdf::MaximumCPlanarSubgraph::setNumAddVariables ( int  n)
inline

Definition at line 150 of file MaximumCPlanarSubgraph.h.

◆ setNumberOfKuraIterations()

void ogdf::MaximumCPlanarSubgraph::setNumberOfKuraIterations ( int  i)
inline

Definition at line 125 of file MaximumCPlanarSubgraph.h.

◆ setNumberOfPermutations()

void ogdf::MaximumCPlanarSubgraph::setNumberOfPermutations ( int  i)
inline

Definition at line 124 of file MaximumCPlanarSubgraph.h.

◆ setNumberOfSubDivisions()

void ogdf::MaximumCPlanarSubgraph::setNumberOfSubDivisions ( int  i)
inline

Definition at line 126 of file MaximumCPlanarSubgraph.h.

◆ setNumberOfSupportGraphs()

void ogdf::MaximumCPlanarSubgraph::setNumberOfSupportGraphs ( int  i)
inline

Definition at line 127 of file MaximumCPlanarSubgraph.h.

◆ setPerturbation()

void ogdf::MaximumCPlanarSubgraph::setPerturbation ( bool  b)
inline

Definition at line 130 of file MaximumCPlanarSubgraph.h.

◆ setPortaOutput()

void ogdf::MaximumCPlanarSubgraph::setPortaOutput ( bool  b)
inline

Definition at line 147 of file MaximumCPlanarSubgraph.h.

◆ setPricing()

void ogdf::MaximumCPlanarSubgraph::setPricing ( bool  b)
inline

Definition at line 148 of file MaximumCPlanarSubgraph.h.

◆ setStrongConstraintViolation()

void ogdf::MaximumCPlanarSubgraph::setStrongConstraintViolation ( double  d)
inline

Definition at line 151 of file MaximumCPlanarSubgraph.h.

◆ setStrongVariableViolation()

void ogdf::MaximumCPlanarSubgraph::setStrongVariableViolation ( double  d)
inline

Definition at line 152 of file MaximumCPlanarSubgraph.h.

◆ setTimeLimit() [1/2]

void ogdf::MaximumCPlanarSubgraph::setTimeLimit ( std::chrono::milliseconds  milliSec)
inline

Definition at line 133 of file MaximumCPlanarSubgraph.h.

◆ setTimeLimit() [2/2]

void ogdf::MaximumCPlanarSubgraph::setTimeLimit ( string  s)
inline

Definition at line 132 of file MaximumCPlanarSubgraph.h.

◆ setUpperRounding()

void ogdf::MaximumCPlanarSubgraph::setUpperRounding ( double  d)
inline

Definition at line 128 of file MaximumCPlanarSubgraph.h.

◆ useDefaultCutPool()

bool& ogdf::MaximumCPlanarSubgraph::useDefaultCutPool ( )
inline

Use default abacus master cut pool or dedicated connectivity and kuratowski cut pools.

Definition at line 155 of file MaximumCPlanarSubgraph.h.

◆ writeFeasible()

void ogdf::MaximumCPlanarSubgraph::writeFeasible ( const char *  filename,
MaxCPlanarMaster master,
abacus::Master::STATUS status 
)

Writes feasible solutions as a file in PORTA format.

Member Data Documentation

◆ m_branchingGap

double ogdf::MaximumCPlanarSubgraph::m_branchingGap
private

Definition at line 225 of file MaximumCPlanarSubgraph.h.

◆ m_checkCPlanar

bool ogdf::MaximumCPlanarSubgraph::m_checkCPlanar
private

Definition at line 228 of file MaximumCPlanarSubgraph.h.

◆ m_defaultCutPool

bool ogdf::MaximumCPlanarSubgraph::m_defaultCutPool
private

Definition at line 263 of file MaximumCPlanarSubgraph.h.

◆ m_heuristicLevel

int ogdf::MaximumCPlanarSubgraph::m_heuristicLevel
private

Definition at line 219 of file MaximumCPlanarSubgraph.h.

◆ m_heuristicNPermLists

int ogdf::MaximumCPlanarSubgraph::m_heuristicNPermLists
private

Definition at line 221 of file MaximumCPlanarSubgraph.h.

◆ m_heuristicOEdgeBound

double ogdf::MaximumCPlanarSubgraph::m_heuristicOEdgeBound
private

Definition at line 220 of file MaximumCPlanarSubgraph.h.

◆ m_heuristicRuns

int ogdf::MaximumCPlanarSubgraph::m_heuristicRuns
private

Definition at line 219 of file MaximumCPlanarSubgraph.h.

◆ m_heurTime

double ogdf::MaximumCPlanarSubgraph::m_heurTime
private

Definition at line 251 of file MaximumCPlanarSubgraph.h.

◆ m_kSupportGraphs

int ogdf::MaximumCPlanarSubgraph::m_kSupportGraphs
private

Definition at line 222 of file MaximumCPlanarSubgraph.h.

◆ m_kuratowskiHigh

double ogdf::MaximumCPlanarSubgraph::m_kuratowskiHigh
private

Definition at line 223 of file MaximumCPlanarSubgraph.h.

◆ m_kuratowskiIterations

int ogdf::MaximumCPlanarSubgraph::m_kuratowskiIterations
private

Definition at line 221 of file MaximumCPlanarSubgraph.h.

◆ m_kuratowskiLow

double ogdf::MaximumCPlanarSubgraph::m_kuratowskiLow
private

Definition at line 223 of file MaximumCPlanarSubgraph.h.

◆ m_lpSolverTime

double ogdf::MaximumCPlanarSubgraph::m_lpSolverTime
private

Definition at line 253 of file MaximumCPlanarSubgraph.h.

◆ m_lpTime

double ogdf::MaximumCPlanarSubgraph::m_lpTime
private

Definition at line 252 of file MaximumCPlanarSubgraph.h.

◆ m_numAddVariables

int ogdf::MaximumCPlanarSubgraph::m_numAddVariables
private

Definition at line 229 of file MaximumCPlanarSubgraph.h.

◆ m_numBCs

int ogdf::MaximumCPlanarSubgraph::m_numBCs
private

Definition at line 259 of file MaximumCPlanarSubgraph.h.

◆ m_numCCons

int ogdf::MaximumCPlanarSubgraph::m_numCCons
private

Definition at line 256 of file MaximumCPlanarSubgraph.h.

◆ m_numKCons

int ogdf::MaximumCPlanarSubgraph::m_numKCons
private

Definition at line 257 of file MaximumCPlanarSubgraph.h.

◆ m_numLPs

int ogdf::MaximumCPlanarSubgraph::m_numLPs
private

Definition at line 258 of file MaximumCPlanarSubgraph.h.

◆ m_numSubSelected

int ogdf::MaximumCPlanarSubgraph::m_numSubSelected
private

Definition at line 260 of file MaximumCPlanarSubgraph.h.

◆ m_numVars

int ogdf::MaximumCPlanarSubgraph::m_numVars
private

Definition at line 261 of file MaximumCPlanarSubgraph.h.

◆ m_perturbation

bool ogdf::MaximumCPlanarSubgraph::m_perturbation
private

Definition at line 224 of file MaximumCPlanarSubgraph.h.

◆ m_portaOutput

bool ogdf::MaximumCPlanarSubgraph::m_portaOutput
private

Definition at line 262 of file MaximumCPlanarSubgraph.h.

◆ m_pricing

bool ogdf::MaximumCPlanarSubgraph::m_pricing
private

Definition at line 227 of file MaximumCPlanarSubgraph.h.

◆ m_sepTime

double ogdf::MaximumCPlanarSubgraph::m_sepTime
private

Definition at line 254 of file MaximumCPlanarSubgraph.h.

◆ m_strongConstraintViolation

double ogdf::MaximumCPlanarSubgraph::m_strongConstraintViolation
private

Definition at line 230 of file MaximumCPlanarSubgraph.h.

◆ m_strongVariableViolation

double ogdf::MaximumCPlanarSubgraph::m_strongVariableViolation
private

Definition at line 231 of file MaximumCPlanarSubgraph.h.

◆ m_subdivisions

int ogdf::MaximumCPlanarSubgraph::m_subdivisions
private

Definition at line 222 of file MaximumCPlanarSubgraph.h.

◆ m_time

string ogdf::MaximumCPlanarSubgraph::m_time
private

Definition at line 226 of file MaximumCPlanarSubgraph.h.

◆ m_totalTime

double ogdf::MaximumCPlanarSubgraph::m_totalTime
private

Definition at line 250 of file MaximumCPlanarSubgraph.h.

◆ m_totalWTime

double ogdf::MaximumCPlanarSubgraph::m_totalWTime
private

Definition at line 255 of file MaximumCPlanarSubgraph.h.


The documentation for this class was generated from the following file: