Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Types | Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes | List of all members
ogdf::ILPClusterPlanarity Class Reference
Graph Algorithms » Cluster-Planarity and Planarization

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

#include <ogdf/cluster/ILPClusterPlanarity.h>

+ Inheritance diagram for ogdf::ILPClusterPlanarity:

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

 ILPClusterPlanarity ()
 Construction. More...
 
 ~ILPClusterPlanarity ()
 
bool clusterPlanarEmbedClusterPlanarGraph (ClusterGraph &CG, Graph &G) override
 Constructs a cluster-planar embedding of CG. CG has to be cluster-planar! 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...
 
abacus::Master::STATUS getOptStatus ()
 
double getSeparationTime ()
 
bool getSolByHeuristic ()
 
double getTotalTime ()
 
double getTotalWTime ()
 
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...
 
bool isClusterPlanarDestructive (ClusterGraph &CG, Graph &G) override
 Returns true, if CG is cluster-planar, false otherwise. In it is non-cluster-planar, the (Cluster)Graph may be arbitrarily changed after the call. 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)
 
solmeth & solutionMethod ()
 
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::ClusterPlanarityModule
 ClusterPlanarityModule ()=default
 
virtual ~ClusterPlanarityModule ()=default
 
virtual bool clusterPlanarEmbed (ClusterGraph &CG, Graph &G)
 Returns true, if CG is cluster-planar, false otherwise. If true, CG contains a cluster-planar embedding. More...
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 

Protected Member Functions

bool doTest (const ClusterGraph &CG)
 
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)
 
- Protected Member Functions inherited from ogdf::ClusterPlanarityModule
virtual void copyBackEmbedding (ClusterGraph &CG, Graph &G, const ClusterGraph &CGcopy, const Graph &Gcopy, const ClusterArray< cluster > &copyC, const NodeArray< node > &copyN, const EdgeArray< edge > &copyE, const EdgeArray< edge > &origE) const
 

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
 
bool m_solByHeuristic
 
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 49 of file ILPClusterPlanarity.h.

Member Typedef Documentation

◆ CP_MasterBase

using ogdf::ILPClusterPlanarity::CP_MasterBase = cluster_planarity::CP_MasterBase

Definition at line 52 of file ILPClusterPlanarity.h.

◆ NodePairs

using ogdf::ILPClusterPlanarity::NodePairs = List<NodePair>

Definition at line 51 of file ILPClusterPlanarity.h.

Member Enumeration Documentation

◆ solmeth

enum ogdf::ILPClusterPlanarity::solmeth
strong

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 57 of file ILPClusterPlanarity.h.

Constructor & Destructor Documentation

◆ ILPClusterPlanarity()

ogdf::ILPClusterPlanarity::ILPClusterPlanarity ( )
inline

Construction.

Definition at line 60 of file ILPClusterPlanarity.h.

◆ ~ILPClusterPlanarity()

ogdf::ILPClusterPlanarity::~ILPClusterPlanarity ( )
inline

Definition at line 100 of file ILPClusterPlanarity.h.

Member Function Documentation

◆ clusterPlanarEmbedClusterPlanarGraph()

bool ogdf::ILPClusterPlanarity::clusterPlanarEmbedClusterPlanarGraph ( ClusterGraph &  CG,
Graph &  G 
)
overridevirtual

Constructs a cluster-planar embedding of CG. CG has to be cluster-planar!

Returns true if the embedding was successful. Returns false if the given graph was non-cluster-planar (and leaves the (Cluster)Graph in an at least partially invalidated state).

This routine may be slightly faster than clusterPlanarEmbed, but requires CG to be cluster-planar. If CG is not cluster-planar, the (Cluster)Graph will be (partially) destroyed while trying to embed it!

Reimplemented from ogdf::ClusterPlanarityModule.

◆ doTest() [1/2]

bool ogdf::ILPClusterPlanarity::doTest ( const ClusterGraph &  CG)
protected

◆ doTest() [2/2]

bool ogdf::ILPClusterPlanarity::doTest ( const ClusterGraph &  G,
NodePairs &  addedEdges 
)
protected

◆ getBottomUpClusterList()

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

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

◆ getDoubleTime()

double ogdf::ILPClusterPlanarity::getDoubleTime ( const Stopwatch &  act)
inlineprotected

Definition at line 209 of file ILPClusterPlanarity.h.

◆ getHeurTime()

double ogdf::ILPClusterPlanarity::getHeurTime ( )
inline

Definition at line 159 of file ILPClusterPlanarity.h.

◆ getIeqFileName()

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

Definition at line 237 of file ILPClusterPlanarity.h.

◆ getLPSolverTime()

double ogdf::ILPClusterPlanarity::getLPSolverTime ( )
inline

Definition at line 163 of file ILPClusterPlanarity.h.

◆ getLPTime()

double ogdf::ILPClusterPlanarity::getLPTime ( )
inline

Definition at line 161 of file ILPClusterPlanarity.h.

◆ getNumBCs()

int ogdf::ILPClusterPlanarity::getNumBCs ( )
inline

Returns number of generated LPs.

Definition at line 179 of file ILPClusterPlanarity.h.

◆ getNumCCons()

int ogdf::ILPClusterPlanarity::getNumCCons ( )
inline

Returns number of connectivity constraints added during computation.

Definition at line 170 of file ILPClusterPlanarity.h.

◆ getNumKCons()

int ogdf::ILPClusterPlanarity::getNumKCons ( )
inline

Returns number of Kuratowski constraints added during computation.

Definition at line 173 of file ILPClusterPlanarity.h.

◆ getNumLPs()

int ogdf::ILPClusterPlanarity::getNumLPs ( )
inline

Returns number of optimized LPs (only LP-relaxations)

Definition at line 176 of file ILPClusterPlanarity.h.

◆ getNumSubSelected()

int ogdf::ILPClusterPlanarity::getNumSubSelected ( )
inline

Returns number of subproblems selected by ABACUS.

Definition at line 182 of file ILPClusterPlanarity.h.

◆ getNumVars()

int ogdf::ILPClusterPlanarity::getNumVars ( )
inline

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

Definition at line 185 of file ILPClusterPlanarity.h.

◆ getOptStatus()

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

Definition at line 155 of file ILPClusterPlanarity.h.

◆ getPortaFileName()

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

Definition at line 235 of file ILPClusterPlanarity.h.

◆ getSeparationTime()

double ogdf::ILPClusterPlanarity::getSeparationTime ( )
inline

Definition at line 165 of file ILPClusterPlanarity.h.

◆ getSolByHeuristic()

bool ogdf::ILPClusterPlanarity::getSolByHeuristic ( )
inline

Definition at line 190 of file ILPClusterPlanarity.h.

◆ getTotalTime()

double ogdf::ILPClusterPlanarity::getTotalTime ( )
inline

Definition at line 157 of file ILPClusterPlanarity.h.

◆ getTotalWTime()

double ogdf::ILPClusterPlanarity::getTotalWTime ( )
inline

Definition at line 167 of file ILPClusterPlanarity.h.

◆ isClusterPlanar() [1/2]

bool ogdf::ILPClusterPlanarity::isClusterPlanar ( const ClusterGraph &  CG)
overridevirtual

Returns c-planarity status of CG.

Reimplemented from ogdf::ClusterPlanarityModule.

◆ isClusterPlanar() [2/2]

bool ogdf::ILPClusterPlanarity::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.

◆ isClusterPlanarDestructive()

bool ogdf::ILPClusterPlanarity::isClusterPlanarDestructive ( ClusterGraph &  CG,
Graph &  G 
)
inlineoverridevirtual

Returns true, if CG is cluster-planar, false otherwise. In it is non-cluster-planar, the (Cluster)Graph may be arbitrarily changed after the call.

This variant may be slightly faster than the default isClusterPlanar

Implements ogdf::ClusterPlanarityModule.

Definition at line 109 of file ILPClusterPlanarity.h.

◆ maxConLength()

int ogdf::ILPClusterPlanarity::maxConLength ( )
inlineprivate

Definition at line 239 of file ILPClusterPlanarity.h.

◆ outputCons()

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

◆ setBranchingGap()

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

Definition at line 136 of file ILPClusterPlanarity.h.

◆ setHeuristicBound()

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

Definition at line 120 of file ILPClusterPlanarity.h.

◆ setHeuristicLevel()

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

Definition at line 116 of file ILPClusterPlanarity.h.

◆ setHeuristicRuns()

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

Definition at line 118 of file ILPClusterPlanarity.h.

◆ setLowerRounding()

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

Definition at line 132 of file ILPClusterPlanarity.h.

◆ setNumAddVariables()

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

Definition at line 144 of file ILPClusterPlanarity.h.

◆ setNumberOfKuraIterations()

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

Definition at line 124 of file ILPClusterPlanarity.h.

◆ setNumberOfPermutations()

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

Definition at line 122 of file ILPClusterPlanarity.h.

◆ setNumberOfSubDivisions()

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

Definition at line 126 of file ILPClusterPlanarity.h.

◆ setNumberOfSupportGraphs()

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

Definition at line 128 of file ILPClusterPlanarity.h.

◆ setPerturbation()

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

Definition at line 134 of file ILPClusterPlanarity.h.

◆ setPortaOutput()

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

Definition at line 140 of file ILPClusterPlanarity.h.

◆ setPricing()

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

Definition at line 142 of file ILPClusterPlanarity.h.

◆ setStrongConstraintViolation()

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

Definition at line 146 of file ILPClusterPlanarity.h.

◆ setStrongVariableViolation()

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

Definition at line 148 of file ILPClusterPlanarity.h.

◆ setTimeLimit()

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

Definition at line 138 of file ILPClusterPlanarity.h.

◆ setUpperRounding()

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

Definition at line 130 of file ILPClusterPlanarity.h.

◆ solutionMethod()

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

Definition at line 193 of file ILPClusterPlanarity.h.

◆ useDefaultCutPool()

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

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

Definition at line 152 of file ILPClusterPlanarity.h.

◆ writeFeasible()

void ogdf::ILPClusterPlanarity::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::ILPClusterPlanarity::m_branchingGap
private

Definition at line 226 of file ILPClusterPlanarity.h.

◆ m_defaultCutPool

bool ogdf::ILPClusterPlanarity::m_defaultCutPool
private

Definition at line 260 of file ILPClusterPlanarity.h.

◆ m_heuristicLevel

int ogdf::ILPClusterPlanarity::m_heuristicLevel
private

Definition at line 220 of file ILPClusterPlanarity.h.

◆ m_heuristicNPermLists

int ogdf::ILPClusterPlanarity::m_heuristicNPermLists
private

Definition at line 222 of file ILPClusterPlanarity.h.

◆ m_heuristicOEdgeBound

double ogdf::ILPClusterPlanarity::m_heuristicOEdgeBound
private

Definition at line 221 of file ILPClusterPlanarity.h.

◆ m_heuristicRuns

int ogdf::ILPClusterPlanarity::m_heuristicRuns
private

Definition at line 220 of file ILPClusterPlanarity.h.

◆ m_heurTime

double ogdf::ILPClusterPlanarity::m_heurTime
private

Definition at line 248 of file ILPClusterPlanarity.h.

◆ m_kSupportGraphs

int ogdf::ILPClusterPlanarity::m_kSupportGraphs
private

Definition at line 223 of file ILPClusterPlanarity.h.

◆ m_kuratowskiHigh

double ogdf::ILPClusterPlanarity::m_kuratowskiHigh
private

Definition at line 224 of file ILPClusterPlanarity.h.

◆ m_kuratowskiIterations

int ogdf::ILPClusterPlanarity::m_kuratowskiIterations
private

Definition at line 222 of file ILPClusterPlanarity.h.

◆ m_kuratowskiLow

double ogdf::ILPClusterPlanarity::m_kuratowskiLow
private

Definition at line 224 of file ILPClusterPlanarity.h.

◆ m_lpSolverTime

double ogdf::ILPClusterPlanarity::m_lpSolverTime
private

Definition at line 250 of file ILPClusterPlanarity.h.

◆ m_lpTime

double ogdf::ILPClusterPlanarity::m_lpTime
private

Definition at line 249 of file ILPClusterPlanarity.h.

◆ m_numAddVariables

int ogdf::ILPClusterPlanarity::m_numAddVariables
private

Definition at line 229 of file ILPClusterPlanarity.h.

◆ m_numBCs

int ogdf::ILPClusterPlanarity::m_numBCs
private

Definition at line 256 of file ILPClusterPlanarity.h.

◆ m_numCCons

int ogdf::ILPClusterPlanarity::m_numCCons
private

Definition at line 253 of file ILPClusterPlanarity.h.

◆ m_numKCons

int ogdf::ILPClusterPlanarity::m_numKCons
private

Definition at line 254 of file ILPClusterPlanarity.h.

◆ m_numLPs

int ogdf::ILPClusterPlanarity::m_numLPs
private

Definition at line 255 of file ILPClusterPlanarity.h.

◆ m_numSubSelected

int ogdf::ILPClusterPlanarity::m_numSubSelected
private

Definition at line 257 of file ILPClusterPlanarity.h.

◆ m_numVars

int ogdf::ILPClusterPlanarity::m_numVars
private

Definition at line 258 of file ILPClusterPlanarity.h.

◆ m_optStatus

abacus::Master::STATUS ogdf::ILPClusterPlanarity::m_optStatus
private

Definition at line 246 of file ILPClusterPlanarity.h.

◆ m_perturbation

bool ogdf::ILPClusterPlanarity::m_perturbation
private

Definition at line 225 of file ILPClusterPlanarity.h.

◆ m_portaOutput

bool ogdf::ILPClusterPlanarity::m_portaOutput
private

Definition at line 259 of file ILPClusterPlanarity.h.

◆ m_pricing

bool ogdf::ILPClusterPlanarity::m_pricing
private

Definition at line 228 of file ILPClusterPlanarity.h.

◆ m_sepTime

double ogdf::ILPClusterPlanarity::m_sepTime
private

Definition at line 251 of file ILPClusterPlanarity.h.

◆ m_solByHeuristic

bool ogdf::ILPClusterPlanarity::m_solByHeuristic
private

Definition at line 262 of file ILPClusterPlanarity.h.

◆ m_solmeth

solmeth ogdf::ILPClusterPlanarity::m_solmeth
private

Solution method, see description of solmeth.

Definition at line 233 of file ILPClusterPlanarity.h.

◆ m_strongConstraintViolation

double ogdf::ILPClusterPlanarity::m_strongConstraintViolation
private

Definition at line 230 of file ILPClusterPlanarity.h.

◆ m_strongVariableViolation

double ogdf::ILPClusterPlanarity::m_strongVariableViolation
private

Definition at line 231 of file ILPClusterPlanarity.h.

◆ m_subdivisions

int ogdf::ILPClusterPlanarity::m_subdivisions
private

Definition at line 223 of file ILPClusterPlanarity.h.

◆ m_time

string ogdf::ILPClusterPlanarity::m_time
private

Definition at line 227 of file ILPClusterPlanarity.h.

◆ m_totalTime

double ogdf::ILPClusterPlanarity::m_totalTime
private

Definition at line 247 of file ILPClusterPlanarity.h.

◆ m_totalWTime

double ogdf::ILPClusterPlanarity::m_totalWTime
private

Definition at line 252 of file ILPClusterPlanarity.h.

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