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

Public Member Functions
	ClusterPlanarity ()
	Construction.
	~ClusterPlanarity ()
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.
abacus::Master::STATUS	getOptStatus ()
double	getSeparationTime ()
double	getTotalTime ()
double	getTotalWTime ()
virtual bool	isClusterPlanar (const ClusterGraph &CG) override
	Returns c-planarity status of CG.
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.
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.
void	writeFeasible (const char *filename, CP_MasterBase &master, abacus::Master::STATUS &status)
	Writes feasible solutions as a file in PORTA format.
Public Member Functions inherited from ogdf::ClusterPlanarModule
	ClusterPlanarModule ()
virtual	~ClusterPlanarModule ()
Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.
virtual	~Module ()

Protected Member Functions
virtual bool	doTest (const ClusterGraph &CG) override
	Performs a c-planarity test on CG.
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.
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.
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.

Detailed Description

C-planarity testing via completely connected graph extension.

Definition at line 48 of file ClusterPlanarity.h.

Member Typedef Documentation

CP_MasterBase

using ogdf::ClusterPlanarity::CP_MasterBase = cluster_planarity::CP_MasterBase

Definition at line 51 of file ClusterPlanarity.h.

NodePairs

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

Definition at line 50 of file ClusterPlanarity.h.

Member Enumeration Documentation

solmeth

enum class ogdf::ClusterPlanarity::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 56 of file ClusterPlanarity.h.

Constructor & Destructor Documentation

ClusterPlanarity()

ogdf::ClusterPlanarity::ClusterPlanarity ( )

inline

Construction.

Definition at line 59 of file ClusterPlanarity.h.

~ClusterPlanarity()

ogdf::ClusterPlanarity::~ClusterPlanarity ( )

inline

Definition at line 99 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 202 of file ClusterPlanarity.h.

getHeurTime()

double ogdf::ClusterPlanarity::getHeurTime ( )

inline

Definition at line 152 of file ClusterPlanarity.h.

getIeqFileName()

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

inlineprivate

Definition at line 230 of file ClusterPlanarity.h.

getLPSolverTime()

double ogdf::ClusterPlanarity::getLPSolverTime ( )

inline

Definition at line 156 of file ClusterPlanarity.h.

getLPTime()

double ogdf::ClusterPlanarity::getLPTime ( )

inline

Definition at line 154 of file ClusterPlanarity.h.

getNumBCs()

int ogdf::ClusterPlanarity::getNumBCs ( )

inline

Returns number of generated LPs.

Definition at line 172 of file ClusterPlanarity.h.

getNumCCons()

int ogdf::ClusterPlanarity::getNumCCons ( )

inline

Returns number of connectivity constraints added during computation.

Definition at line 163 of file ClusterPlanarity.h.

getNumKCons()

int ogdf::ClusterPlanarity::getNumKCons ( )

inline

Returns number of Kuratowski constraints added during computation.

Definition at line 166 of file ClusterPlanarity.h.

getNumLPs()

int ogdf::ClusterPlanarity::getNumLPs ( )

inline

Returns number of optimized LPs (only LP-relaxations)

Definition at line 169 of file ClusterPlanarity.h.

getNumSubSelected()

int ogdf::ClusterPlanarity::getNumSubSelected ( )

inline

Returns number of subproblems selected by ABACUS.

Definition at line 175 of file ClusterPlanarity.h.

getNumVars()

int ogdf::ClusterPlanarity::getNumVars ( )

inline

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

Definition at line 178 of file ClusterPlanarity.h.

getOptStatus()

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

inline

Definition at line 148 of file ClusterPlanarity.h.

getPortaFileName()

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

inlineprivate

Definition at line 228 of file ClusterPlanarity.h.

getSeparationTime()

double ogdf::ClusterPlanarity::getSeparationTime ( )

inline

Definition at line 158 of file ClusterPlanarity.h.

getTotalTime()

double ogdf::ClusterPlanarity::getTotalTime ( )

inline

Definition at line 150 of file ClusterPlanarity.h.

getTotalWTime()

double ogdf::ClusterPlanarity::getTotalWTime ( )

inline

Definition at line 160 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 232 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 129 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 109 of file ClusterPlanarity.h.

setHeuristicRuns()

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

inline

Definition at line 111 of file ClusterPlanarity.h.

setLowerRounding()

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

inline

Definition at line 125 of file ClusterPlanarity.h.

setNumAddVariables()

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

inline

Definition at line 137 of file ClusterPlanarity.h.

setNumberOfKuraIterations()

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

inline

Definition at line 117 of file ClusterPlanarity.h.

setNumberOfPermutations()

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

inline

Definition at line 115 of file ClusterPlanarity.h.

setNumberOfSubDivisions()

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

inline

Definition at line 119 of file ClusterPlanarity.h.

setNumberOfSupportGraphs()

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

inline

Definition at line 121 of file ClusterPlanarity.h.

setPerturbation()

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

inline

Definition at line 127 of file ClusterPlanarity.h.

setPortaOutput()

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

inline

Definition at line 133 of file ClusterPlanarity.h.

setPricing()

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

inline

Definition at line 135 of file ClusterPlanarity.h.

setStrongConstraintViolation()

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

inline

Definition at line 139 of file ClusterPlanarity.h.

setStrongVariableViolation()

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

inline

Definition at line 141 of file ClusterPlanarity.h.

setTimeLimit()

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

inline

Definition at line 131 of file ClusterPlanarity.h.

setUpperRounding()

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

inline

Definition at line 123 of file ClusterPlanarity.h.

solutionMethod()

solmeth & ogdf::ClusterPlanarity::solutionMethod ( )

inline

Definition at line 186 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 145 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 219 of file ClusterPlanarity.h.

m_defaultCutPool

bool ogdf::ClusterPlanarity::m_defaultCutPool

private

Definition at line 253 of file ClusterPlanarity.h.

m_heuristicLevel

int ogdf::ClusterPlanarity::m_heuristicLevel

private

Definition at line 213 of file ClusterPlanarity.h.

m_heuristicNPermLists

int ogdf::ClusterPlanarity::m_heuristicNPermLists

private

Definition at line 215 of file ClusterPlanarity.h.

m_heuristicOEdgeBound

double ogdf::ClusterPlanarity::m_heuristicOEdgeBound

private

Definition at line 214 of file ClusterPlanarity.h.

m_heuristicRuns

int ogdf::ClusterPlanarity::m_heuristicRuns

private

Definition at line 213 of file ClusterPlanarity.h.

m_heurTime

double ogdf::ClusterPlanarity::m_heurTime

private

Definition at line 241 of file ClusterPlanarity.h.

m_kSupportGraphs

int ogdf::ClusterPlanarity::m_kSupportGraphs

private

Definition at line 216 of file ClusterPlanarity.h.

m_kuratowskiHigh

double ogdf::ClusterPlanarity::m_kuratowskiHigh

private

Definition at line 217 of file ClusterPlanarity.h.

m_kuratowskiIterations

int ogdf::ClusterPlanarity::m_kuratowskiIterations

private

Definition at line 215 of file ClusterPlanarity.h.

m_kuratowskiLow

double ogdf::ClusterPlanarity::m_kuratowskiLow

private

Definition at line 217 of file ClusterPlanarity.h.

m_lpSolverTime

double ogdf::ClusterPlanarity::m_lpSolverTime

private

Definition at line 243 of file ClusterPlanarity.h.

m_lpTime

double ogdf::ClusterPlanarity::m_lpTime

private

Definition at line 242 of file ClusterPlanarity.h.

m_numAddVariables

int ogdf::ClusterPlanarity::m_numAddVariables

private

Definition at line 222 of file ClusterPlanarity.h.

m_numBCs

int ogdf::ClusterPlanarity::m_numBCs

private

Definition at line 249 of file ClusterPlanarity.h.

m_numCCons

int ogdf::ClusterPlanarity::m_numCCons

private

Definition at line 246 of file ClusterPlanarity.h.

m_numKCons

int ogdf::ClusterPlanarity::m_numKCons

private

Definition at line 247 of file ClusterPlanarity.h.

m_numLPs

int ogdf::ClusterPlanarity::m_numLPs

private

Definition at line 248 of file ClusterPlanarity.h.

m_numSubSelected

int ogdf::ClusterPlanarity::m_numSubSelected

private

Definition at line 250 of file ClusterPlanarity.h.

m_numVars

int ogdf::ClusterPlanarity::m_numVars

private

Definition at line 251 of file ClusterPlanarity.h.

m_optStatus

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

private

Definition at line 239 of file ClusterPlanarity.h.

m_perturbation

bool ogdf::ClusterPlanarity::m_perturbation

private

Definition at line 218 of file ClusterPlanarity.h.

m_portaOutput

bool ogdf::ClusterPlanarity::m_portaOutput

private

Definition at line 252 of file ClusterPlanarity.h.

m_pricing

bool ogdf::ClusterPlanarity::m_pricing

private

Definition at line 221 of file ClusterPlanarity.h.

m_sepTime

double ogdf::ClusterPlanarity::m_sepTime

private

Definition at line 244 of file ClusterPlanarity.h.

m_solmeth

solmeth ogdf::ClusterPlanarity::m_solmeth

private

Solution method, see description of solmeth.

Definition at line 226 of file ClusterPlanarity.h.

m_strongConstraintViolation

double ogdf::ClusterPlanarity::m_strongConstraintViolation

private

Definition at line 223 of file ClusterPlanarity.h.

m_strongVariableViolation

double ogdf::ClusterPlanarity::m_strongVariableViolation

private

Definition at line 224 of file ClusterPlanarity.h.

m_subdivisions

int ogdf::ClusterPlanarity::m_subdivisions

private

Definition at line 216 of file ClusterPlanarity.h.

m_time

string ogdf::ClusterPlanarity::m_time

private

Definition at line 220 of file ClusterPlanarity.h.

m_totalTime

double ogdf::ClusterPlanarity::m_totalTime

private

Definition at line 240 of file ClusterPlanarity.h.

m_totalWTime

double ogdf::ClusterPlanarity::m_totalWTime

private

Definition at line 245 of file ClusterPlanarity.h.

---

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

• include/ogdf/cluster/ClusterPlanarity.h