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 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
	ILPClusterPlanarity ()
	Construction.

	~ILPClusterPlanarity ()

bool	clusterPlanarEmbedClusterPlanarGraph (ClusterGraph &CG, Graph &G) override
	Constructs a cluster-planar embedding of `CG`. `CG` has to be cluster-planar!

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 ()

bool	getSolByHeuristic ()

double	getTotalTime ()

double	getTotalWTime ()

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.

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.

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::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.

Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.

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.

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.

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

Member Typedef Documentation

◆ CP_MasterBase

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

Definition at line 64 of file ILPClusterPlanarity.h.

◆ NodePairs

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

Definition at line 63 of file ILPClusterPlanarity.h.

Member Enumeration Documentation

◆ solmeth

enum class 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 69 of file ILPClusterPlanarity.h.

Constructor & Destructor Documentation

◆ ILPClusterPlanarity()

ogdf::ILPClusterPlanarity::ILPClusterPlanarity ( )

inline

Construction.

Definition at line 72 of file ILPClusterPlanarity.h.

◆ ~ILPClusterPlanarity()

ogdf::ILPClusterPlanarity::~ILPClusterPlanarity ( )

inline

Definition at line 112 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 221 of file ILPClusterPlanarity.h.

◆ getHeurTime()

double ogdf::ILPClusterPlanarity::getHeurTime ( )

inline

Definition at line 171 of file ILPClusterPlanarity.h.

◆ getIeqFileName()

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

inlineprivate

Definition at line 249 of file ILPClusterPlanarity.h.

◆ getLPSolverTime()

double ogdf::ILPClusterPlanarity::getLPSolverTime ( )

inline

Definition at line 175 of file ILPClusterPlanarity.h.

◆ getLPTime()

double ogdf::ILPClusterPlanarity::getLPTime ( )

inline

Definition at line 173 of file ILPClusterPlanarity.h.

◆ getNumBCs()

int ogdf::ILPClusterPlanarity::getNumBCs ( )

inline

Returns number of generated LPs.

Definition at line 191 of file ILPClusterPlanarity.h.

◆ getNumCCons()

int ogdf::ILPClusterPlanarity::getNumCCons ( )

inline

Returns number of connectivity constraints added during computation.

Definition at line 182 of file ILPClusterPlanarity.h.

◆ getNumKCons()

int ogdf::ILPClusterPlanarity::getNumKCons ( )

inline

Returns number of Kuratowski constraints added during computation.

Definition at line 185 of file ILPClusterPlanarity.h.

◆ getNumLPs()

int ogdf::ILPClusterPlanarity::getNumLPs ( )

inline

Returns number of optimized LPs (only LP-relaxations)

Definition at line 188 of file ILPClusterPlanarity.h.

◆ getNumSubSelected()

int ogdf::ILPClusterPlanarity::getNumSubSelected ( )

inline

Returns number of subproblems selected by ABACUS.

Definition at line 194 of file ILPClusterPlanarity.h.

◆ getNumVars()

int ogdf::ILPClusterPlanarity::getNumVars ( )

inline

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

Definition at line 197 of file ILPClusterPlanarity.h.

◆ getOptStatus()

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

inline

Definition at line 167 of file ILPClusterPlanarity.h.

◆ getPortaFileName()

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

inlineprivate

Definition at line 247 of file ILPClusterPlanarity.h.

◆ getSeparationTime()

double ogdf::ILPClusterPlanarity::getSeparationTime ( )

inline

Definition at line 177 of file ILPClusterPlanarity.h.

◆ getSolByHeuristic()

bool ogdf::ILPClusterPlanarity::getSolByHeuristic ( )

inline

Definition at line 202 of file ILPClusterPlanarity.h.

◆ getTotalTime()

double ogdf::ILPClusterPlanarity::getTotalTime ( )

inline

Definition at line 169 of file ILPClusterPlanarity.h.

◆ getTotalWTime()

double ogdf::ILPClusterPlanarity::getTotalWTime ( )

inline

Definition at line 179 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 121 of file ILPClusterPlanarity.h.

◆ maxConLength()

int ogdf::ILPClusterPlanarity::maxConLength ( )

inlineprivate

Definition at line 251 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 148 of file ILPClusterPlanarity.h.

◆ setHeuristicBound()

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

inline

Definition at line 132 of file ILPClusterPlanarity.h.

◆ setHeuristicLevel()

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

inline

Definition at line 128 of file ILPClusterPlanarity.h.

◆ setHeuristicRuns()

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

inline

Definition at line 130 of file ILPClusterPlanarity.h.

◆ setLowerRounding()

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

inline

Definition at line 144 of file ILPClusterPlanarity.h.

◆ setNumAddVariables()

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

inline

Definition at line 156 of file ILPClusterPlanarity.h.

◆ setNumberOfKuraIterations()

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

inline

Definition at line 136 of file ILPClusterPlanarity.h.

◆ setNumberOfPermutations()

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

inline

Definition at line 134 of file ILPClusterPlanarity.h.

◆ setNumberOfSubDivisions()

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

inline

Definition at line 138 of file ILPClusterPlanarity.h.

◆ setNumberOfSupportGraphs()

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

inline

Definition at line 140 of file ILPClusterPlanarity.h.

◆ setPerturbation()

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

inline

Definition at line 146 of file ILPClusterPlanarity.h.

◆ setPortaOutput()

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

inline

Definition at line 152 of file ILPClusterPlanarity.h.

◆ setPricing()

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

inline

Definition at line 154 of file ILPClusterPlanarity.h.

◆ setStrongConstraintViolation()

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

inline

Definition at line 158 of file ILPClusterPlanarity.h.

◆ setStrongVariableViolation()

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

inline

Definition at line 160 of file ILPClusterPlanarity.h.

◆ setTimeLimit()

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

inline

Definition at line 150 of file ILPClusterPlanarity.h.

◆ setUpperRounding()

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

inline

Definition at line 142 of file ILPClusterPlanarity.h.

◆ solutionMethod()

solmeth & ogdf::ILPClusterPlanarity::solutionMethod ( )

inline

Definition at line 205 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 164 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 238 of file ILPClusterPlanarity.h.

◆ m_defaultCutPool

bool ogdf::ILPClusterPlanarity::m_defaultCutPool

private

Definition at line 272 of file ILPClusterPlanarity.h.

◆ m_heuristicLevel

int ogdf::ILPClusterPlanarity::m_heuristicLevel

private

Definition at line 232 of file ILPClusterPlanarity.h.

◆ m_heuristicNPermLists

int ogdf::ILPClusterPlanarity::m_heuristicNPermLists

private

Definition at line 234 of file ILPClusterPlanarity.h.

◆ m_heuristicOEdgeBound

double ogdf::ILPClusterPlanarity::m_heuristicOEdgeBound

private

Definition at line 233 of file ILPClusterPlanarity.h.

◆ m_heuristicRuns

int ogdf::ILPClusterPlanarity::m_heuristicRuns

private

Definition at line 232 of file ILPClusterPlanarity.h.

◆ m_heurTime

double ogdf::ILPClusterPlanarity::m_heurTime

private

Definition at line 260 of file ILPClusterPlanarity.h.

◆ m_kSupportGraphs

int ogdf::ILPClusterPlanarity::m_kSupportGraphs

private

Definition at line 235 of file ILPClusterPlanarity.h.

◆ m_kuratowskiHigh

double ogdf::ILPClusterPlanarity::m_kuratowskiHigh

private

Definition at line 236 of file ILPClusterPlanarity.h.

◆ m_kuratowskiIterations

int ogdf::ILPClusterPlanarity::m_kuratowskiIterations

private

Definition at line 234 of file ILPClusterPlanarity.h.

◆ m_kuratowskiLow

double ogdf::ILPClusterPlanarity::m_kuratowskiLow

private

Definition at line 236 of file ILPClusterPlanarity.h.

◆ m_lpSolverTime

double ogdf::ILPClusterPlanarity::m_lpSolverTime

private

Definition at line 262 of file ILPClusterPlanarity.h.

◆ m_lpTime

double ogdf::ILPClusterPlanarity::m_lpTime

private

Definition at line 261 of file ILPClusterPlanarity.h.

◆ m_numAddVariables

int ogdf::ILPClusterPlanarity::m_numAddVariables

private

Definition at line 241 of file ILPClusterPlanarity.h.

◆ m_numBCs

int ogdf::ILPClusterPlanarity::m_numBCs

private

Definition at line 268 of file ILPClusterPlanarity.h.

◆ m_numCCons

int ogdf::ILPClusterPlanarity::m_numCCons

private

Definition at line 265 of file ILPClusterPlanarity.h.

◆ m_numKCons

int ogdf::ILPClusterPlanarity::m_numKCons

private

Definition at line 266 of file ILPClusterPlanarity.h.

◆ m_numLPs

int ogdf::ILPClusterPlanarity::m_numLPs

private

Definition at line 267 of file ILPClusterPlanarity.h.

◆ m_numSubSelected

int ogdf::ILPClusterPlanarity::m_numSubSelected

private

Definition at line 269 of file ILPClusterPlanarity.h.

◆ m_numVars

int ogdf::ILPClusterPlanarity::m_numVars

private

Definition at line 270 of file ILPClusterPlanarity.h.

◆ m_optStatus

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

private

Definition at line 258 of file ILPClusterPlanarity.h.

◆ m_perturbation

bool ogdf::ILPClusterPlanarity::m_perturbation

private

Definition at line 237 of file ILPClusterPlanarity.h.

◆ m_portaOutput

bool ogdf::ILPClusterPlanarity::m_portaOutput

private

Definition at line 271 of file ILPClusterPlanarity.h.

◆ m_pricing

bool ogdf::ILPClusterPlanarity::m_pricing

private

Definition at line 240 of file ILPClusterPlanarity.h.

◆ m_sepTime

double ogdf::ILPClusterPlanarity::m_sepTime

private

Definition at line 263 of file ILPClusterPlanarity.h.

◆ m_solByHeuristic

bool ogdf::ILPClusterPlanarity::m_solByHeuristic

private

Definition at line 274 of file ILPClusterPlanarity.h.

◆ m_solmeth

solmeth ogdf::ILPClusterPlanarity::m_solmeth

private

Solution method, see description of solmeth.

Definition at line 245 of file ILPClusterPlanarity.h.

◆ m_strongConstraintViolation

double ogdf::ILPClusterPlanarity::m_strongConstraintViolation

private

Definition at line 242 of file ILPClusterPlanarity.h.

◆ m_strongVariableViolation

double ogdf::ILPClusterPlanarity::m_strongVariableViolation

private

Definition at line 243 of file ILPClusterPlanarity.h.

◆ m_subdivisions

int ogdf::ILPClusterPlanarity::m_subdivisions

private

Definition at line 235 of file ILPClusterPlanarity.h.

◆ m_time

string ogdf::ILPClusterPlanarity::m_time

private

Definition at line 239 of file ILPClusterPlanarity.h.

◆ m_totalTime

double ogdf::ILPClusterPlanarity::m_totalTime

private

Definition at line 259 of file ILPClusterPlanarity.h.

◆ m_totalWTime

double ogdf::ILPClusterPlanarity::m_totalWTime

private

Definition at line 264 of file ILPClusterPlanarity.h.

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

include/ogdf/cluster/ILPClusterPlanarity.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ CP_MasterBase

◆ NodePairs

Member Enumeration Documentation

◆ solmeth

Constructor & Destructor Documentation

◆ ILPClusterPlanarity()

◆ ~ILPClusterPlanarity()

Member Function Documentation

◆ clusterPlanarEmbedClusterPlanarGraph()

◆ doTest() [1/2]

◆ doTest() [2/2]

◆ getBottomUpClusterList()

◆ getDoubleTime()

◆ getHeurTime()

◆ getIeqFileName()

◆ getLPSolverTime()

◆ getLPTime()

◆ getNumBCs()

◆ getNumCCons()

◆ getNumKCons()

◆ getNumLPs()

◆ getNumSubSelected()

◆ getNumVars()

◆ getOptStatus()

◆ getPortaFileName()

◆ getSeparationTime()

◆ getSolByHeuristic()

◆ getTotalTime()

◆ getTotalWTime()

◆ isClusterPlanar() [1/2]

◆ isClusterPlanar() [2/2]

◆ isClusterPlanarDestructive()

◆ maxConLength()

◆ outputCons()

◆ setBranchingGap()

◆ setHeuristicBound()

◆ setHeuristicLevel()

◆ setHeuristicRuns()

◆ setLowerRounding()

◆ setNumAddVariables()

◆ setNumberOfKuraIterations()

◆ setNumberOfPermutations()

◆ setNumberOfSubDivisions()

◆ setNumberOfSupportGraphs()

◆ setPerturbation()

◆ setPortaOutput()

◆ setPricing()

◆ setStrongConstraintViolation()

◆ setStrongVariableViolation()

◆ setTimeLimit()

◆ setUpperRounding()

◆ solutionMethod()

◆ useDefaultCutPool()

◆ writeFeasible()

Member Data Documentation

◆ m_branchingGap

◆ m_defaultCutPool

◆ m_heuristicLevel

◆ m_heuristicNPermLists

◆ m_heuristicOEdgeBound

◆ m_heuristicRuns

◆ m_heurTime

◆ m_kSupportGraphs

◆ m_kuratowskiHigh

◆ m_kuratowskiIterations

◆ m_kuratowskiLow

◆ m_lpSolverTime

◆ m_lpTime

◆ m_numAddVariables

◆ m_numBCs

◆ m_numCCons

Open
Graph Drawing
Framework