Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ClusterPlanarity Class Reference

C-planarity testing via completely connected graph extension. More...

#include <ogdf/cluster/ClusterPlanarity.h>

+ Inheritance diagram for ogdf::ClusterPlanarity:

Public Types

using CP_MasterBase = cluster_planarity::CP_MasterBase
 
using NodePairs = List< NodePair >
 
enum  solmeth { solmeth::Fallback, solmeth::New }
 Solution method, fallback to old version (allowing all extension edges, based on c-planar subgraph computation) or new direct version (allowing only a reduced set of extension edges for complete connectivity). More...
 
- 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

 ClusterPlanarity ()
 Construction. More...
 
 ~ClusterPlanarity ()
 
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...
 
abacus::Master::STATUS getOptStatus ()
 
double getSeparationTime ()
 
double getTotalTime ()
 
double getTotalWTime ()
 
virtual bool isClusterPlanar (const ClusterGraph &CG) override
 Returns c-planarity status of CG. More...
 
bool isClusterPlanar (const ClusterGraph &CG, NodePairs &addedEdges)
 Computes a set of edges that augments the subgraph to be completely connected and returns c-planarity status and edge set. More...
 
void setBranchingGap (double d)
 
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 (string s)
 
void setUpperRounding (double d)
 
solmethsolutionMethod ()
 
bool & useDefaultCutPool ()
 Use default abacus master cut pool or dedicated connectivity and kuratowski cut pools. More...
 
void writeFeasible (const char *filename, CP_MasterBase &master, abacus::Master::STATUS &status)
 Writes feasible solutions as a file in PORTA format. More...
 
- Public Member Functions inherited from ogdf::ClusterPlanarModule
 ClusterPlanarModule ()
 
virtual ~ClusterPlanarModule ()
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 

Protected Member Functions

virtual bool doTest (const ClusterGraph &CG) override
 Performs a c-planarity test on CG. More...
 
virtual bool doTest (const ClusterGraph &G, 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_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
 
abacus::Master::STATUS m_optStatus
 
bool m_perturbation
 
bool m_portaOutput
 
bool m_pricing
 
double m_sepTime
 
solmeth m_solmeth
 Solution method, see description of solmeth. More...
 
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...
 

Detailed Description

C-planarity testing via completely connected graph extension.

Definition at line 50 of file ClusterPlanarity.h.

Member Typedef Documentation

◆ CP_MasterBase

◆ NodePairs

Member Enumeration Documentation

◆ solmeth

Solution method, fallback to old version (allowing all extension edges, based on c-planar subgraph computation) or new direct version (allowing only a reduced set of extension edges for complete connectivity).

Enumerator
Fallback 
New 

Definition at line 59 of file ClusterPlanarity.h.

Constructor & Destructor Documentation

◆ ClusterPlanarity()

ogdf::ClusterPlanarity::ClusterPlanarity ( )
inline

Construction.

Definition at line 62 of file ClusterPlanarity.h.

◆ ~ClusterPlanarity()

ogdf::ClusterPlanarity::~ClusterPlanarity ( )
inline

Definition at line 101 of file ClusterPlanarity.h.

Member Function Documentation

◆ doTest() [1/2]

virtual bool ogdf::ClusterPlanarity::doTest ( const ClusterGraph CG)
overrideprotectedvirtual

Performs a c-planarity test on CG.

Implements ogdf::ClusterPlanarModule.

◆ doTest() [2/2]

virtual bool ogdf::ClusterPlanarity::doTest ( const ClusterGraph G,
NodePairs addedEdges 
)
protectedvirtual

◆ getBottomUpClusterList()

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

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

◆ getDoubleTime()

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

Definition at line 177 of file ClusterPlanarity.h.

◆ getHeurTime()

double ogdf::ClusterPlanarity::getHeurTime ( )
inline

Definition at line 135 of file ClusterPlanarity.h.

◆ getIeqFileName()

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

Definition at line 207 of file ClusterPlanarity.h.

◆ getLPSolverTime()

double ogdf::ClusterPlanarity::getLPSolverTime ( )
inline

Definition at line 137 of file ClusterPlanarity.h.

◆ getLPTime()

double ogdf::ClusterPlanarity::getLPTime ( )
inline

Definition at line 136 of file ClusterPlanarity.h.

◆ getNumBCs()

int ogdf::ClusterPlanarity::getNumBCs ( )
inline

Returns number of generated LPs.

Definition at line 147 of file ClusterPlanarity.h.

◆ getNumCCons()

int ogdf::ClusterPlanarity::getNumCCons ( )
inline

Returns number of connectivity constraints added during computation.

Definition at line 141 of file ClusterPlanarity.h.

◆ getNumKCons()

int ogdf::ClusterPlanarity::getNumKCons ( )
inline

Returns number of Kuratowski constraints added during computation.

Definition at line 143 of file ClusterPlanarity.h.

◆ getNumLPs()

int ogdf::ClusterPlanarity::getNumLPs ( )
inline

Returns number of optimized LPs (only LP-relaxations)

Definition at line 145 of file ClusterPlanarity.h.

◆ getNumSubSelected()

int ogdf::ClusterPlanarity::getNumSubSelected ( )
inline

Returns number of subproblems selected by ABACUS.

Definition at line 149 of file ClusterPlanarity.h.

◆ getNumVars()

int ogdf::ClusterPlanarity::getNumVars ( )
inline

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

Definition at line 151 of file ClusterPlanarity.h.

◆ getOptStatus()

abacus::Master::STATUS ogdf::ClusterPlanarity::getOptStatus ( )
inline

Definition at line 133 of file ClusterPlanarity.h.

◆ getPortaFileName()

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

Definition at line 203 of file ClusterPlanarity.h.

◆ getSeparationTime()

double ogdf::ClusterPlanarity::getSeparationTime ( )
inline

Definition at line 138 of file ClusterPlanarity.h.

◆ getTotalTime()

double ogdf::ClusterPlanarity::getTotalTime ( )
inline

Definition at line 134 of file ClusterPlanarity.h.

◆ getTotalWTime()

double ogdf::ClusterPlanarity::getTotalWTime ( )
inline

Definition at line 139 of file ClusterPlanarity.h.

◆ isClusterPlanar() [1/2]

virtual bool ogdf::ClusterPlanarity::isClusterPlanar ( const ClusterGraph CG)
overridevirtual

Returns c-planarity status of CG.

Reimplemented from ogdf::ClusterPlanarModule.

◆ isClusterPlanar() [2/2]

bool ogdf::ClusterPlanarity::isClusterPlanar ( const ClusterGraph CG,
NodePairs addedEdges 
)

Computes a set of edges that augments the subgraph to be completely connected and returns c-planarity status and edge set.

◆ maxConLength()

int ogdf::ClusterPlanarity::maxConLength ( )
inlineprivate

Definition at line 211 of file ClusterPlanarity.h.

◆ outputCons()

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

◆ setBranchingGap()

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

Definition at line 121 of file ClusterPlanarity.h.

◆ setHeuristicBound()

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

Definition at line 113 of file ClusterPlanarity.h.

◆ setHeuristicLevel()

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

Definition at line 111 of file ClusterPlanarity.h.

◆ setHeuristicRuns()

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

Definition at line 112 of file ClusterPlanarity.h.

◆ setLowerRounding()

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

Definition at line 119 of file ClusterPlanarity.h.

◆ setNumAddVariables()

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

Definition at line 125 of file ClusterPlanarity.h.

◆ setNumberOfKuraIterations()

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

Definition at line 115 of file ClusterPlanarity.h.

◆ setNumberOfPermutations()

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

Definition at line 114 of file ClusterPlanarity.h.

◆ setNumberOfSubDivisions()

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

Definition at line 116 of file ClusterPlanarity.h.

◆ setNumberOfSupportGraphs()

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

Definition at line 117 of file ClusterPlanarity.h.

◆ setPerturbation()

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

Definition at line 120 of file ClusterPlanarity.h.

◆ setPortaOutput()

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

Definition at line 123 of file ClusterPlanarity.h.

◆ setPricing()

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

Definition at line 124 of file ClusterPlanarity.h.

◆ setStrongConstraintViolation()

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

Definition at line 126 of file ClusterPlanarity.h.

◆ setStrongVariableViolation()

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

Definition at line 127 of file ClusterPlanarity.h.

◆ setTimeLimit()

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

Definition at line 122 of file ClusterPlanarity.h.

◆ setUpperRounding()

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

Definition at line 118 of file ClusterPlanarity.h.

◆ solutionMethod()

solmeth& ogdf::ClusterPlanarity::solutionMethod ( )
inline

Definition at line 160 of file ClusterPlanarity.h.

◆ useDefaultCutPool()

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

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

Definition at line 130 of file ClusterPlanarity.h.

◆ writeFeasible()

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

Writes feasible solutions as a file in PORTA format.

Member Data Documentation

◆ m_branchingGap

double ogdf::ClusterPlanarity::m_branchingGap
private

Definition at line 194 of file ClusterPlanarity.h.

◆ m_defaultCutPool

bool ogdf::ClusterPlanarity::m_defaultCutPool
private

Definition at line 234 of file ClusterPlanarity.h.

◆ m_heuristicLevel

int ogdf::ClusterPlanarity::m_heuristicLevel
private

Definition at line 188 of file ClusterPlanarity.h.

◆ m_heuristicNPermLists

int ogdf::ClusterPlanarity::m_heuristicNPermLists
private

Definition at line 190 of file ClusterPlanarity.h.

◆ m_heuristicOEdgeBound

double ogdf::ClusterPlanarity::m_heuristicOEdgeBound
private

Definition at line 189 of file ClusterPlanarity.h.

◆ m_heuristicRuns

int ogdf::ClusterPlanarity::m_heuristicRuns
private

Definition at line 188 of file ClusterPlanarity.h.

◆ m_heurTime

double ogdf::ClusterPlanarity::m_heurTime
private

Definition at line 222 of file ClusterPlanarity.h.

◆ m_kSupportGraphs

int ogdf::ClusterPlanarity::m_kSupportGraphs
private

Definition at line 191 of file ClusterPlanarity.h.

◆ m_kuratowskiHigh

double ogdf::ClusterPlanarity::m_kuratowskiHigh
private

Definition at line 192 of file ClusterPlanarity.h.

◆ m_kuratowskiIterations

int ogdf::ClusterPlanarity::m_kuratowskiIterations
private

Definition at line 190 of file ClusterPlanarity.h.

◆ m_kuratowskiLow

double ogdf::ClusterPlanarity::m_kuratowskiLow
private

Definition at line 192 of file ClusterPlanarity.h.

◆ m_lpSolverTime

double ogdf::ClusterPlanarity::m_lpSolverTime
private

Definition at line 224 of file ClusterPlanarity.h.

◆ m_lpTime

double ogdf::ClusterPlanarity::m_lpTime
private

Definition at line 223 of file ClusterPlanarity.h.

◆ m_numAddVariables

int ogdf::ClusterPlanarity::m_numAddVariables
private

Definition at line 197 of file ClusterPlanarity.h.

◆ m_numBCs

int ogdf::ClusterPlanarity::m_numBCs
private

Definition at line 230 of file ClusterPlanarity.h.

◆ m_numCCons

int ogdf::ClusterPlanarity::m_numCCons
private

Definition at line 227 of file ClusterPlanarity.h.

◆ m_numKCons

int ogdf::ClusterPlanarity::m_numKCons
private

Definition at line 228 of file ClusterPlanarity.h.

◆ m_numLPs

int ogdf::ClusterPlanarity::m_numLPs
private

Definition at line 229 of file ClusterPlanarity.h.

◆ m_numSubSelected

int ogdf::ClusterPlanarity::m_numSubSelected
private

Definition at line 231 of file ClusterPlanarity.h.

◆ m_numVars

int ogdf::ClusterPlanarity::m_numVars
private

Definition at line 232 of file ClusterPlanarity.h.

◆ m_optStatus

abacus::Master::STATUS ogdf::ClusterPlanarity::m_optStatus
private

Definition at line 220 of file ClusterPlanarity.h.

◆ m_perturbation

bool ogdf::ClusterPlanarity::m_perturbation
private

Definition at line 193 of file ClusterPlanarity.h.

◆ m_portaOutput

bool ogdf::ClusterPlanarity::m_portaOutput
private

Definition at line 233 of file ClusterPlanarity.h.

◆ m_pricing

bool ogdf::ClusterPlanarity::m_pricing
private

Definition at line 196 of file ClusterPlanarity.h.

◆ m_sepTime

double ogdf::ClusterPlanarity::m_sepTime
private

Definition at line 225 of file ClusterPlanarity.h.

◆ m_solmeth

solmeth ogdf::ClusterPlanarity::m_solmeth
private

Solution method, see description of solmeth.

Definition at line 201 of file ClusterPlanarity.h.

◆ m_strongConstraintViolation

double ogdf::ClusterPlanarity::m_strongConstraintViolation
private

Definition at line 198 of file ClusterPlanarity.h.

◆ m_strongVariableViolation

double ogdf::ClusterPlanarity::m_strongVariableViolation
private

Definition at line 199 of file ClusterPlanarity.h.

◆ m_subdivisions

int ogdf::ClusterPlanarity::m_subdivisions
private

Definition at line 191 of file ClusterPlanarity.h.

◆ m_time

string ogdf::ClusterPlanarity::m_time
private

Definition at line 195 of file ClusterPlanarity.h.

◆ m_totalTime

double ogdf::ClusterPlanarity::m_totalTime
private

Definition at line 221 of file ClusterPlanarity.h.

◆ m_totalWTime

double ogdf::ClusterPlanarity::m_totalWTime
private

Definition at line 226 of file ClusterPlanarity.h.


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