Open
Graph Drawing
Framework

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

Loading...
Searching...
No Matches
Public Types | Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes | List of all members
ogdf::MaximumCPlanarSubgraph Class Reference
Graph Algorithms » Cluster-Planarity and Planarization

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 class  ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , Error }
 The return type of a module. More...
 

Public Member Functions

 MaximumCPlanarSubgraph ()
 Construction.
 
 ~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.
 
double getHeurTime ()
 
double getLPSolverTime ()
 
double getLPTime ()
 
int getNumBCs ()
 Returns number of generated LPs.
 
int getNumCCons ()
 Returns number of connectivity constraints added during computation.
 
int getNumKCons ()
 Returns number of Kuratowski constraints added during computation.
 
int getNumLPs ()
 Returns number of optimized LPs (only LP-relaxations)
 
int getNumSubSelected ()
 Returns number of subproblems selected by ABACUS.
 
int getNumVars ()
 Returns number of global variables. Todo: Real number from ABACUS.
 
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.
 
void writeFeasible (const char *filename, MaxCPlanarMaster &master, abacus::Master::STATUS &status)
 Writes feasible solutions as a file in PORTA format.
 
- Public Member Functions inherited from ogdf::CPlanarSubgraphModule
 CPlanarSubgraphModule ()
 Constructs a cplanar subgraph module.
 
virtual ~CPlanarSubgraphModule ()
 Destruction.
 
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.
 
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.
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module.
 
virtual ~Module ()
 
- Public Member Functions inherited from ogdf::Timeouter
 Timeouter ()
 timeout is turned of by default
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second)
 
 Timeouter (const Timeouter &t)
 
 Timeouter (double t)
 timeout is set to the given value (seconds)
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not
 
Timeouter & operator= (const Timeouter &t)
 
double timeLimit () const
 returns the current time limit for the call
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds)
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit.
 

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.
 
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.
 
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.
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit).
 

Detailed Description

Exact computation of a maximum c-planar subgraph.

Definition at line 51 of file MaximumCPlanarSubgraph.h.

Member Typedef Documentation

◆ MaxCPlanarMaster

using ogdf::MaximumCPlanarSubgraph::MaxCPlanarMaster = cluster_planarity::MaxCPlanarMaster

Definition at line 54 of file MaximumCPlanarSubgraph.h.

◆ NodePairs

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

Definition at line 53 of file MaximumCPlanarSubgraph.h.

Constructor & Destructor Documentation

◆ MaximumCPlanarSubgraph()

ogdf::MaximumCPlanarSubgraph::MaximumCPlanarSubgraph ( )
inline

Construction.

Definition at line 57 of file MaximumCPlanarSubgraph.h.

◆ ~MaximumCPlanarSubgraph()

ogdf::MaximumCPlanarSubgraph::~MaximumCPlanarSubgraph ( )
inline

Definition at line 96 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 112 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 217 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 229 of file MaximumCPlanarSubgraph.h.

◆ getHeurTime()

double ogdf::MaximumCPlanarSubgraph::getHeurTime ( )
inline

Definition at line 176 of file MaximumCPlanarSubgraph.h.

◆ getIeqFileName()

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

Definition at line 256 of file MaximumCPlanarSubgraph.h.

◆ getLPSolverTime()

double ogdf::MaximumCPlanarSubgraph::getLPSolverTime ( )
inline

Definition at line 180 of file MaximumCPlanarSubgraph.h.

◆ getLPTime()

double ogdf::MaximumCPlanarSubgraph::getLPTime ( )
inline

Definition at line 178 of file MaximumCPlanarSubgraph.h.

◆ getNumBCs()

int ogdf::MaximumCPlanarSubgraph::getNumBCs ( )
inline

Returns number of generated LPs.

Definition at line 196 of file MaximumCPlanarSubgraph.h.

◆ getNumCCons()

int ogdf::MaximumCPlanarSubgraph::getNumCCons ( )
inline

Returns number of connectivity constraints added during computation.

Definition at line 187 of file MaximumCPlanarSubgraph.h.

◆ getNumKCons()

int ogdf::MaximumCPlanarSubgraph::getNumKCons ( )
inline

Returns number of Kuratowski constraints added during computation.

Definition at line 190 of file MaximumCPlanarSubgraph.h.

◆ getNumLPs()

int ogdf::MaximumCPlanarSubgraph::getNumLPs ( )
inline

Returns number of optimized LPs (only LP-relaxations)

Definition at line 193 of file MaximumCPlanarSubgraph.h.

◆ getNumSubSelected()

int ogdf::MaximumCPlanarSubgraph::getNumSubSelected ( )
inline

Returns number of subproblems selected by ABACUS.

Definition at line 199 of file MaximumCPlanarSubgraph.h.

◆ getNumVars()

int ogdf::MaximumCPlanarSubgraph::getNumVars ( )
inline

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

Definition at line 202 of file MaximumCPlanarSubgraph.h.

◆ getPortaFileName()

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

Definition at line 254 of file MaximumCPlanarSubgraph.h.

◆ getSeparationTime()

double ogdf::MaximumCPlanarSubgraph::getSeparationTime ( )
inline

Definition at line 182 of file MaximumCPlanarSubgraph.h.

◆ getTotalTime()

double ogdf::MaximumCPlanarSubgraph::getTotalTime ( )
inline

Definition at line 174 of file MaximumCPlanarSubgraph.h.

◆ getTotalWTime()

double ogdf::MaximumCPlanarSubgraph::getTotalWTime ( )
inline

Definition at line 184 of file MaximumCPlanarSubgraph.h.

◆ maxConLength()

int ogdf::MaximumCPlanarSubgraph::maxConLength ( )
inlineprivate

Definition at line 258 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 138 of file MaximumCPlanarSubgraph.h.

◆ setCheckCPlanar()

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

Definition at line 161 of file MaximumCPlanarSubgraph.h.

◆ setHeuristicBound()

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

Definition at line 122 of file MaximumCPlanarSubgraph.h.

◆ setHeuristicLevel()

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

Definition at line 118 of file MaximumCPlanarSubgraph.h.

◆ setHeuristicRuns()

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

Definition at line 120 of file MaximumCPlanarSubgraph.h.

◆ setLowerRounding()

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

Definition at line 134 of file MaximumCPlanarSubgraph.h.

◆ setNumAddVariables()

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

Definition at line 163 of file MaximumCPlanarSubgraph.h.

◆ setNumberOfKuraIterations()

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

Definition at line 126 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 128 of file MaximumCPlanarSubgraph.h.

◆ setNumberOfSupportGraphs()

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

Definition at line 130 of file MaximumCPlanarSubgraph.h.

◆ setPerturbation()

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

Definition at line 136 of file MaximumCPlanarSubgraph.h.

◆ setPortaOutput()

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

Definition at line 157 of file MaximumCPlanarSubgraph.h.

◆ setPricing()

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

Definition at line 159 of file MaximumCPlanarSubgraph.h.

◆ setStrongConstraintViolation()

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

Definition at line 165 of file MaximumCPlanarSubgraph.h.

◆ setStrongVariableViolation()

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

Definition at line 167 of file MaximumCPlanarSubgraph.h.

◆ setTimeLimit() [1/2]

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

Definition at line 142 of file MaximumCPlanarSubgraph.h.

◆ setTimeLimit() [2/2]

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

Definition at line 140 of file MaximumCPlanarSubgraph.h.

◆ setUpperRounding()

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

Definition at line 132 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 171 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 246 of file MaximumCPlanarSubgraph.h.

◆ m_checkCPlanar

bool ogdf::MaximumCPlanarSubgraph::m_checkCPlanar
private

Definition at line 249 of file MaximumCPlanarSubgraph.h.

◆ m_defaultCutPool

bool ogdf::MaximumCPlanarSubgraph::m_defaultCutPool
private

Definition at line 278 of file MaximumCPlanarSubgraph.h.

◆ m_heuristicLevel

int ogdf::MaximumCPlanarSubgraph::m_heuristicLevel
private

Definition at line 240 of file MaximumCPlanarSubgraph.h.

◆ m_heuristicNPermLists

int ogdf::MaximumCPlanarSubgraph::m_heuristicNPermLists
private

Definition at line 242 of file MaximumCPlanarSubgraph.h.

◆ m_heuristicOEdgeBound

double ogdf::MaximumCPlanarSubgraph::m_heuristicOEdgeBound
private

Definition at line 241 of file MaximumCPlanarSubgraph.h.

◆ m_heuristicRuns

int ogdf::MaximumCPlanarSubgraph::m_heuristicRuns
private

Definition at line 240 of file MaximumCPlanarSubgraph.h.

◆ m_heurTime

double ogdf::MaximumCPlanarSubgraph::m_heurTime
private

Definition at line 266 of file MaximumCPlanarSubgraph.h.

◆ m_kSupportGraphs

int ogdf::MaximumCPlanarSubgraph::m_kSupportGraphs
private

Definition at line 243 of file MaximumCPlanarSubgraph.h.

◆ m_kuratowskiHigh

double ogdf::MaximumCPlanarSubgraph::m_kuratowskiHigh
private

Definition at line 244 of file MaximumCPlanarSubgraph.h.

◆ m_kuratowskiIterations

int ogdf::MaximumCPlanarSubgraph::m_kuratowskiIterations
private

Definition at line 242 of file MaximumCPlanarSubgraph.h.

◆ m_kuratowskiLow

double ogdf::MaximumCPlanarSubgraph::m_kuratowskiLow
private

Definition at line 244 of file MaximumCPlanarSubgraph.h.

◆ m_lpSolverTime

double ogdf::MaximumCPlanarSubgraph::m_lpSolverTime
private

Definition at line 268 of file MaximumCPlanarSubgraph.h.

◆ m_lpTime

double ogdf::MaximumCPlanarSubgraph::m_lpTime
private

Definition at line 267 of file MaximumCPlanarSubgraph.h.

◆ m_numAddVariables

int ogdf::MaximumCPlanarSubgraph::m_numAddVariables
private

Definition at line 250 of file MaximumCPlanarSubgraph.h.

◆ m_numBCs

int ogdf::MaximumCPlanarSubgraph::m_numBCs
private

Definition at line 274 of file MaximumCPlanarSubgraph.h.

◆ m_numCCons

int ogdf::MaximumCPlanarSubgraph::m_numCCons
private

Definition at line 271 of file MaximumCPlanarSubgraph.h.

◆ m_numKCons

int ogdf::MaximumCPlanarSubgraph::m_numKCons
private

Definition at line 272 of file MaximumCPlanarSubgraph.h.

◆ m_numLPs

int ogdf::MaximumCPlanarSubgraph::m_numLPs
private

Definition at line 273 of file MaximumCPlanarSubgraph.h.

◆ m_numSubSelected

int ogdf::MaximumCPlanarSubgraph::m_numSubSelected
private

Definition at line 275 of file MaximumCPlanarSubgraph.h.

◆ m_numVars

int ogdf::MaximumCPlanarSubgraph::m_numVars
private

Definition at line 276 of file MaximumCPlanarSubgraph.h.

◆ m_perturbation

bool ogdf::MaximumCPlanarSubgraph::m_perturbation
private

Definition at line 245 of file MaximumCPlanarSubgraph.h.

◆ m_portaOutput

bool ogdf::MaximumCPlanarSubgraph::m_portaOutput
private

Definition at line 277 of file MaximumCPlanarSubgraph.h.

◆ m_pricing

bool ogdf::MaximumCPlanarSubgraph::m_pricing
private

Definition at line 248 of file MaximumCPlanarSubgraph.h.

◆ m_sepTime

double ogdf::MaximumCPlanarSubgraph::m_sepTime
private

Definition at line 269 of file MaximumCPlanarSubgraph.h.

◆ m_strongConstraintViolation

double ogdf::MaximumCPlanarSubgraph::m_strongConstraintViolation
private

Definition at line 251 of file MaximumCPlanarSubgraph.h.

◆ m_strongVariableViolation

double ogdf::MaximumCPlanarSubgraph::m_strongVariableViolation
private

Definition at line 252 of file MaximumCPlanarSubgraph.h.

◆ m_subdivisions

int ogdf::MaximumCPlanarSubgraph::m_subdivisions
private

Definition at line 243 of file MaximumCPlanarSubgraph.h.

◆ m_time

string ogdf::MaximumCPlanarSubgraph::m_time
private

Definition at line 247 of file MaximumCPlanarSubgraph.h.

◆ m_totalTime

double ogdf::MaximumCPlanarSubgraph::m_totalTime
private

Definition at line 265 of file MaximumCPlanarSubgraph.h.

◆ m_totalWTime

double ogdf::MaximumCPlanarSubgraph::m_totalWTime
private

Definition at line 270 of file MaximumCPlanarSubgraph.h.

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