#include <ogdf/cluster/internal/CPlanarityMaster.h>

Inheritance diagram for ogdf::cluster_planarity::CPlanarityMaster:

Public Member Functions
	CPlanarityMaster (const ClusterGraph &C, int heuristicLevel=0, int heuristicRuns=2, double heuristicOEdgeBound=0.3, int heuristicNPermLists=5, int kuratowskiIterations=3, int subdivisions=10, int kSupportGraphs=3, double kuratowskiHigh=0.75, double kuratowskiLow=0.3, bool perturbation=false, double branchingGap=0.4, const char *time="00:20:00")

virtual	~CPlanarityMaster ()
	Destruction. More...

double	branchingOEdgeSelectGap () const

virtual abacus::Sub *	firstSub () override
	Should return a pointer to the first subproblem of the optimization, i.e., the root node of the enumeration tree. More...

const ClusterGraph *	getClusterGraph () const

const List< node > &	getClusterNodes (cluster c) const
	Returns reference to cluster nodes member list for `c`. More...

void	getClusterNodes (cluster c, List< node > &nodeList) const
	Copies cluster nodes from member list to parameter list. Should be used if node list needs to be altered. More...

void	getConnectionOptimalSolutionEdges (List< NodePair > &egdes) const override
	Returns nodePairs of connecting optimal solution edges in list `edges`. More...

const Graph *	getGraph () const

double	getHeuristicFractionalBound () const

int	getHeuristicLevel () const

int	getHeuristicRuns () const

double	getKBoundHigh () const

double	getKBoundLow () const

int	getKIterations () const

bool	getMPHeuristic () const

int	getNKuratowskiSupportGraphs () const

int	getNSubdivisions () const

int	getNumAddVariables () const

int	getNumInactiveVars ()

const char *	getStdConstraintsFileName ()
	The name of the file that contains the standard, i.e., non-cut, constraints (may be deleted by ABACUS and shouldn't be stored twice) More...

double	getStrongConstraintViolation () const

double	getStrongVariableViolation () const

void	heuristicLevel (int level)

int	nMaxVars () const

int	numberOfHeuristicPermutationLists () const

bool	perturbation () const

void	printGraph (const Graph &G)
	Simple output function to print the given graph to the console. Used for debugging only. More...

const GraphCopy *	searchSpaceGraph () const

void	setHeuristicFractionalBound (double b)

void	setHeuristicPermutationLists (int n)

void	setHeuristicRuns (int n)

void	setKBoundHigh (double n)

void	setKBoundLow (double n)

void	setKIterations (int n)

void	setMPHeuristic (bool b)
	Switches use of lower bound heuristic. More...

void	setNHeuristicRuns (int n)

void	setNKuratowskiSupportGraphs (int n)

void	setNSubdivisions (int n)

void	setNumAddVariables (int i)

void	setPertubation (bool b)

void	setSearchSpaceShrinking (bool b)
	Toggles reduction of search space (using only some bag/satchel connections) on/off. More...

void	setStrongConstraintViolation (double d)

void	setStrongVariableViolation (double d)

Graph *	solutionInducedGraph () override
	Returns the optimal solution induced Clustergraph. More...

void	updateBestSubGraph (List< NodePair > &connection) override
	Updates the "best" Subgraph m_solutionGraph found so far and fills `connection` with. More...

Public Member Functions inherited from ogdf::cluster_planarity::CP_MasterBase
	CP_MasterBase (const ClusterGraph &C, int heuristicLevel=1, int heuristicRuns=2, double heuristicOEdgeBound=0.3, int heuristicNPermLists=5, int kuratowskiIterations=3, int subdivisions=10, int kSupportGraphs=3, double kuratowskiHigh=0.7, double kuratowskiLow=0.3, bool perturbation=false, double branchingGap=0.4, const char *time="00:05:00")
	Construction and default values. More...

virtual	~CP_MasterBase ()
	Destruction. More...

int	addedCConstraints () const

int	addedKConstraints () const

double	epsilon () const
	Returns the objective function coefficient of C-edges. More...

const ClusterGraph *	getClusterGraph () const
	Returns a pointer to the given Clustergraph. More...

abacus::StandardPool< abacus::Constraint, abacus::Variable > *	getCutConnPool ()
	Returns cut pool for connectivity. More...

abacus::StandardPool< abacus::Constraint, abacus::Variable > *	getCutKuraPool ()
	Returns cut pool for planarity. More...

double	getDualBound ()

const Graph *	getGraph () const
	Returns a pointer to the underlying Graph. More...

double	getHeuristicFractionalBound () const

int	getHeuristicLevel () const

int	getHeuristicRuns () const

double	getKBoundHigh () const

double	getKBoundLow () const

int	getKIterations () const

bool	getMPHeuristic () const

int	getNKuratowskiSupportGraphs () const

int	getNSubdivisions () const

int	getNumAddVariables () const

int	getNumInactiveVars ()

double	getPrimalBound ()

const char *	getStdConstraintsFileName ()
	The name of the file that contains the standard, i.e., non-cut, constraints (may be deleted by ABACUS and shouldn't be stored twice) More...

double	getStrongConstraintViolation () const

double	getStrongVariableViolation () const

void	heuristicLevel (int level)

double	intGap ()
	Returns a value that allows to distinguish result values when connection edges (tiny negative cost) are added. More...

int	nMaxVars () const
	Returns the number of variables. More...

int	numberOfHeuristicPermutationLists () const

bool	perturbation () const

void	printGraph (const Graph &G)

void	setHeuristicFractionalBound (double b)

void	setHeuristicPermutationLists (int n)

void	setHeuristicRuns (int n)

void	setKBoundHigh (double n)

void	setKBoundLow (double n)

void	setKIterations (int n)

void	setMPHeuristic (bool b)
	Switches use of lower bound heuristic. More...

void	setNHeuristicRuns (int n)

void	setNKuratowskiSupportGraphs (int n)

void	setNSubdivisions (int n)

void	setNumAddVariables (int i)

void	setPertubation (bool b)

void	setPortaFile (bool b)
	If set to true, PORTA output is written in a file. More...

void	setStrongConstraintViolation (double d)

void	setStrongVariableViolation (double d)

void	setTimeLimit (const char *s)

void	updateAddedCCons (int n)

void	updateAddedKCons (int n)

bool &	useDefaultCutPool ()
	Returns true if default cut pool is used. Otherwise, separate connectivity and Kuratowski pools are generated and used. More...

Public Member Functions inherited from abacus::Master
	Master (const char *problemName, bool cutting, bool pricing, OptSense::SENSE optSense=OptSense::Unknown, double eps=1.0e-4, double machineEps=1.0e-7, double infinity=1.0e30, bool readParamFromFile=false)
	The constructor. More...

virtual	~Master ()
	The destructor. More...

BRANCHINGSTRAT	branchingStrategy () const
	Returns the branching strategy. More...

void	branchingStrategy (BRANCHINGSTRAT strat)
	Changes the branching strategy to strat. More...

const ogdf::StopwatchCPU *	branchingTime () const
	Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching rules. More...

bool	check () const
	Can be used to control the correctness of the optimization if the value of the optimum solution has been loaded. More...

int	conElimAge () const
	Returns the age for the elimination of constraints. More...

void	conElimAge (int age)
	Changes the age for the elimination of constraints to age. More...

double	conElimEps () const
	Returns the zero tolerance for the elimination of constraints by the slack criterion. More...

void	conElimEps (double eps)
	Changes the tolerance for the elimination of constraints by the slack criterion to eps. More...

CONELIMMODE	conElimMode () const
	Returns the mode for the elimination of constraints. More...

void	conElimMode (CONELIMMODE mode)
	Changes the constraint elimination mode to mode. More...

StandardPool< Constraint, Variable > *	conPool () const
	Returns a pointer to the default pool storing the constraints of the problem formulation. More...

StandardPool< Constraint, Variable > *	cutPool () const
	Returns a pointer to the default pool for the generated cutting planes. More...

bool	cutting () const

int	dbThreshold () const
	Returns the number of optimizations of a subproblem until sons are created. More...

void	dbThreshold (int threshold)
	Sets the number of optimizations of a subproblem until sons are created in Sub::branching(). More...

OSISOLVER	defaultLpSolver () const
	returns the Lp Solver. More...

void	defaultLpSolver (OSISOLVER osiSolver)
	Changes the default Lp solver to osiSolver. More...

bool	delayedBranching (int nOpt) const
	Returns true if the number of optimizations nOpt of a subproblem exceeds the delayed branching threshold, false otherwise. More...

bool	eliminateFixedSet () const

void	eliminateFixedSet (bool turnOn)
	Turns the elimination of fixed and set variables on or off. More...

ENUMSTRAT	enumerationStrategy () const
	Returns the enumeration strategy. More...

virtual int	enumerationStrategy (const Sub s1, const Sub s2)
	Analyzes the enumeration strategy set in the parameter file `.abacus` and calls the corresponding comparison function for the subproblems s1 and s2. More...

void	enumerationStrategy (ENUMSTRAT strat)
	Changes the enumeration strategy to strat. More...

bool	fixSetByRedCost () const

void	fixSetByRedCost (bool on)
	Turns fixing and setting variables by reduced cost on or off. More...

double	guarantee () const
	Can be used to access the guarantee which can be given for the best known feasible solution. More...

bool	guaranteed () const
	Can be used to check if the guarantee requirements are fulfilled. More...

int	highestLevel () const
	Returns the highest level in the tree which has been reached during the implicit enumeration. More...

History *	history () const
	Returns a pointer to the object storing the solution history of this branch and cut problem. More...

const ogdf::StopwatchCPU *	improveTime () const
	Returns a pointer to the timer measuring the cpu time spent in the heuristics for the computation of feasible solutions. More...

bool	knownOptimum (double &optVal) const
	Opens the file specified with the parameter `OptimumFileName` in the configuration file `.abacus` and tries to find a line with the name of the problem instance (as specified in the constructor of Master) as first string. More...

LpMasterOsi *	lpMasterOsi () const

const ogdf::StopwatchCPU *	lpSolverTime () const
	Return a pointer to the timer measuring the cpu time required by the LP solver. More...

const ogdf::StopwatchCPU *	lpTime () const
	Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface. More...

int	maxConAdd () const
	Returns the maximal number of constraints which should be added in every iteration of the cutting plane algorithm. More...

void	maxConAdd (int max)
	Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm. More...

int	maxConBuffered () const
	Returns the size of the buffer for generated constraints in the cutting plane algorithm. More...

void	maxConBuffered (int max)
	Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm. More...

int64_t	maxCowTime () const
	Returns the maximal wall-clock time (in seconds) which can be used by the optimization. More...

void	maxCowTime (const string &t)
	Sets the maximally allowed wall-clock time for the optimization to t. More...

void	maxCowTime (int64_t seconds)
	Sets the maximally allowed wall-clock time to seconds. More...

string	maxCowTimeAsString () const
	Returns the maximal wall-clock time (as string `hh:mm:ss`) which can be used by the optimization. More...

int64_t	maxCpuTime () const
	Returns the maximal cpu time (in seconds) which can be used by the optimization. More...

void	maxCpuTime (const string &t)
	Sets the maximally allowed cpu time for the optimization to t. More...

void	maxCpuTime (int hour, int min, int sec)
	Sets the maximally allowed cpu time for the optimization to hour, min, sec. More...

void	maxCpuTime (int64_t seconds)
	Sets the maximally allowed cpu time to seconds. More...

string	maxCpuTimeAsString () const
	Returns the maximal cpu time (as string `hh:mm:ss`) which can be used by the optimization. More...

int	maxIterations () const
	Returns the maximal number of iterations per subproblem optimization (-1 means no iteration limit). More...

void	maxIterations (int max)
	Changes the default value for the maximal number of iterations of the optimization of a subproblem. More...

int	maxLevel () const
	Returns the maximal depth up to which the enumeration should be performed. More...

void	maxLevel (int ml)
	This version of the function maxLevel() changes the maximal enumeration depth. More...

int	maxNSub () const
	Returns the maximal number of subproblems to be processed. More...

void	maxNSub (int ml)
	Changes the maximal number of subproblems to ml. More...

int	maxVarAdd () const
	Returns the maximal number of variables which should be added in the column generation algorithm. More...

void	maxVarAdd (int max)
	Changes the maximal number of variables that are added in an iteration of the subproblem optimization. More...

int	maxVarBuffered () const
	Returns the size of the buffer for the variables generated in the column generation algorithm. More...

void	maxVarBuffered (int max)
	Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization. More...

int	minDormantRounds () const
	Returns the maximal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant. More...

void	minDormantRounds (int nRounds)
	Sets the number of rounds a subproblem should stay dormant to nRounds. More...

int	nBranchingVariableCandidates () const
	Returns the number of variables that should be tested for the selection of the branching variable. More...

void	nBranchingVariableCandidates (int n)
	Sets the number of tested branching variable candidates to n. More...

bool	newRootReOptimize () const

void	newRootReOptimize (bool on)
	Turns the reoptimization of new root nodes of the remaining branch and bound tree on or off. More...

int	nLp () const
	Returns the number of optimized linear programs (only LP-relaxations). More...

int	nNewRoot () const
	Returns the number of root changes of the remaining branch-and-cut tree. More...

int	nStrongBranchingIterations () const
	The number of simplex iterations that are performed when testing candidates for branching variables within strong branching. More...

void	nStrongBranchingIterations (int n)
	Sets the number of simplex iterations that are performed when testing candidates for branching variables within strong branching. More...

int	nSub () const
	returns the number of generated subproblems. More...

int	nSubSelected () const
	Returns the number of subproblems which have already been selected from the set of open subproblems. More...

bool	objInteger () const
	If true then we assume that all feasible solutions have integral objective function values. More...

void	objInteger (bool b)
	Sets the assumption that the objective function values of all feasible solutions are integer. More...

OpenSub *	openSub () const
	Returns a pointer to the set of open subproblems. More...

STATUS	optimize ()
	Performs the optimization by branch-and-bound. More...

const string &	optimumFileName () const
	Returns the name of the file that stores the optimum solutions. More...

void	optimumFileName (const char *name)
	Changes the name of the file in which the value of the optimum solution is searched. More...

const OptSense *	optSense () const
	Returns a pointer to the object holding the optimization sense of the problem. More...

virtual void	output () const
	Does nothing but can be redefined in derived classes for output before the timing statistics. More...

PRIMALBOUNDMODE	pbMode () const
	Returns the mode of the primal bound initialization. More...

void	pbMode (PRIMALBOUNDMODE mode)
	Sets the mode of the primal bound initialization to mode. More...

bool	pricing () const

int	pricingFreq () const
	Returns the number of linear programs being solved between two additional pricing steps. More...

void	pricingFreq (int f)
	Sets the number of linear programs being solved between two additional pricing steps to f. More...

const ogdf::StopwatchCPU *	pricingTime () const
	Returns a pointer to the timer measuring the cpu time spent in pricing. More...

void	printGuarantee () const
	Writes the guarantee nicely formated on the output stream associated with this object. More...

bool	printLP () const

void	printLP (bool on)
	Turns the output of the linear program in every iteration on or off. More...

void	printParameters () const
	Writes all parameters of the class Master together with their values to the global output stream. More...

const string &	problemName () const
	Returns the name of the instance being optimized (as specified in the constructor of this class). More...

double	requiredGuarantee () const
	The guarantee specification for the optimization. More...

void	requiredGuarantee (double g)
	Changes the guarantee specification tp g. More...

Sub *	root () const
	Can be used to access the root node of the branch-and-bound tree. More...

Sub *	rRoot () const

const ogdf::StopwatchCPU *	separationTime () const
	Returns a pointer to the timer measuring the cpu time spent in the separation of cutting planes. More...

virtual bool	setSolverParameters (OsiSolverInterface *interface, bool solverIsApprox)
	Sets solver specific parameters. More...

bool	showAverageCutDistance () const

void	showAverageCutDistance (bool on)
	Turns the output of the average distance of the added cuts from the fractional solution on or off. More...

int	skipFactor () const
	Returns the frequency of subproblems in which constraints or variables should be generated. More...

void	skipFactor (int f)
	Sets the frequency for constraint and variable generation to f. More...

SKIPPINGMODE	skippingMode () const
	Returns the skipping strategy. More...

void	skippingMode (SKIPPINGMODE mode)
	Sets the skipping strategy to mode. More...

bool	solveApprox () const
	True, if an approximative solver should be used. More...

STATUS	status () const
	Returns the status of the Master. More...

int	tailOffNLp () const
	Returns the number of linear programs considered in the tailing off analysis. More...

void	tailOffNLp (int n)
	Sets the number of linear programs considered in the tailing off analysis to n. More...

double	tailOffPercent () const
	Returns the minimal change of the dual bound for the tailing off analysis in percent. More...

void	tailOffPercent (double p)
	Sets the minimal change of the dual bound for the tailing off analysis to p. More...

const ogdf::StopwatchWallClock *	totalCowTime () const
	Returns a pointer to the timer measuring the total wall clock time. More...

const ogdf::StopwatchCPU *	totalTime () const
	returns a pointer to the timer measuring the total cpu time for the optimization. More...

int	varElimAge () const
	Returns the age for the elimination of variables by the reduced cost criterion. More...

void	varElimAge (int age)
	Changes the age for the elimination of variables by the reduced cost criterion to age. More...

double	varElimEps () const
	Returns the zero tolerance for the elimination of variables by the reduced cost criterion. More...

void	varElimEps (double eps)
	Changes the tolerance for the elimination of variables by the reduced cost criterion to eps. More...

VARELIMMODE	varElimMode () const
	Returns the mode for the elimination of variables. More...

void	varElimMode (VARELIMMODE mode)
	Changes the variable elimination mode to mode. More...

StandardPool< Variable, Constraint > *	varPool () const
	Returns a pointer to the default pool storing the variables. More...

VBCMODE	vbcLog () const
	Returns the mode of output for the Vbc-Tool. More...

void	vbcLog (VBCMODE mode)
	Changes the mode of output for the Vbc-Tool to mode. More...

double	lowerBound () const
	Returns the value of the global lower bound. More...

double	upperBound () const
	Returns the value of the global upper bound. More...

double	primalBound () const
	Returns the value of the primal bound. More...

void	primalBound (double x)
	Sets the primal bound to x and makes a new entry in the solution history. More...

double	dualBound () const
	Returns the value of the dual bound. More...

void	dualBound (double x)
	Sets the dual bound to x and makes a new entry in the solution history. More...

bool	betterDual (double x) const
	Returns true if x is better than the best known dual bound; false otherwise. More...

bool	primalViolated (double x) const
	Can be used to compare a value with the one of the best known primal bound. More...

bool	betterPrimal (double x) const
	Can be used to check if a value is better than the best know primal bound. More...

double	rootDualBound () const
	Returns the dual bound at the root node. More...

bool	feasibleFound () const
	We use this function, e.g., to adapt the enumeration strategy in the DiveAndBest-Strategy. More...

Public Member Functions inherited from abacus::AbacusGlobal
	AbacusGlobal (double eps=1.0e-4, double machineEps=1.0e-7, double infinity=1.0e32)
	The constructor. More...

virtual	~AbacusGlobal ()
	The destructor. More...

void	assignParameter (bool &param, const char *name) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (bool &param, const char *name, bool defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (char &param, const char name, const char feasible, char defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (char &param, const char name, const char feasible=nullptr) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (double &param, const char *name, double minVal, double maxVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (double &param, const char *name, double minVal, double maxVal, double defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (int &param, const char *name, int minVal, int maxVal) const
	Searches for parameter name in the parameter table and returns its value in param. More...

void	assignParameter (int &param, const char *name, int minVal, int maxVal, int defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (string &param, const char name, unsigned nFeasible, const char feasible[], const char *defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (string &param, const char name, unsigned nFeasible=0, const char feasible[]=nullptr) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (unsigned &param, const char *name, unsigned minVal, unsigned maxVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (unsigned &param, const char *name, unsigned minVal, unsigned maxVal, unsigned defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

double	eps () const
	Returns the zero tolerance. More...

void	eps (double e)
	Sets the zero tolerance to e. More...

bool	equal (double x, double y) const
	Returns whether the absolute difference between x and y is less than the machine dependent zero tolerance. More...

int	findParameter (const char name, const char feasible) const
	See AbacusGlobal::findParameter(const char name, unsigned nFeasible, const int feasible) for description. More...

int	findParameter (const char name, unsigned nFeasible, const char feasible[]) const
	See AbacusGlobal::findParameter(const char name, unsigned nFeasible, const int feasible) for description. More...

int	findParameter (const char name, unsigned nFeasible, const int feasible) const
	Searches for parameter name in the parameter table. More...

int	getParameter (const char *name, bool &param) const

int	getParameter (const char *name, char &param) const

int	getParameter (const char *name, double &param) const

int	getParameter (const char *name, int &param) const
	Searches for parameter name in the parameter table and returns its value in param. More...

int	getParameter (const char *name, string &param) const

int	getParameter (const char *name, unsigned int &param) const

double	infinity () const
	Provides a floating point value of "infinite" size. More...

void	infinity (double x)
	Sets the "infinite value" to x. More...

void	insertParameter (const char name, const char value)
	Inserts parameter name with value value into the parameter table. More...

bool	isInfinity (double x) const
	Returns true if x is regarded as "infinite" large, false otherwise. More...

bool	isInteger (double x) const
	Returns whether the value x differs at most by the machine dependent zero tolerance from an integer value. More...

bool	isInteger (double x, double eps) const
	Returns whether the value x differs at most by eps from an integer value. More...

bool	isMinusInfinity (double x) const
	Returns true if x is regarded as infinite small, false otherwise. More...

double	machineEps () const
	Provides a machine dependent zero tolerance. More...

void	machineEps (double e)
	Sets the machine dependent zero tolerance to e. More...

void	readParameters (const string &fileName)
	Opens the parameter file fileName, reads all parameters, and inserts them in the parameter table. More...

Public Member Functions inherited from abacus::AbacusRoot
virtual	~AbacusRoot ()
	The destructor. More...

Protected Member Functions
void	addExternalConnections (cluster c, List< CPlanarEdgeVar * > &connectVars)
	Create variables for external cluster connections in case we search only in the bag-reduced search space. More...

void	addInnerConnections (cluster c, List< CPlanarEdgeVar * > &connectVars)
	Adds inner cluster connection variables in bag-reduced search space. More...

void	createInitialVariables (List< CPlanarEdgeVar * > &initVars) override
	All variables that have to be present at start of optimization are created here. Their number is returned. More...

bool	goodVar (node a, node b) override
	Node pair is potential candidate for new edge variable. More...

double	heuristicInitialLowerBound () override

virtual void	initializeOptimization () override
	The default implementation of initializeOptimization() does nothing. More...

bool	isCP () override
	Derives and returns c-planarity property either directly or indirectly from computation results. More...

virtual void	terminateOptimization () override
	Function that is invoked at the end of the optimization. Does nothing but output in CP_MasterBase. More...

Protected Member Functions inherited from ogdf::cluster_planarity::CP_MasterBase
void	clearActiveRepairs ()

double	getDoubleTime (const Stopwatch *act)

Protected Member Functions inherited from abacus::Master
virtual void	assignParameters ()
	Assigns the parameters that were read from a file to the member variables of the master. More...

int	bestFirstSearch (const Sub s1, const Sub s2) const
	Implements the best first search enumeration. More...

int	breadthFirstSearch (const Sub s1, const Sub s2) const
	Implements the breadth first search enumeration strategy, i.e., the subproblem with minimum level is selected. More...

int	depthFirstSearch (const Sub s1, const Sub s2) const
	Implements the depth first search enumeration strategy, i.e., the subproblem with maximum level is selected. More...

int	diveAndBestFirstSearch (const Sub s1, const Sub s2) const
	Performs depth-first search until a feasible solution is found, then the search process is continued with best-first search. More...

virtual int	equalSubCompare (const Sub s1, const Sub s2) const
	Is called from the function bestFirstSearch() and from the function depthFirstSearch() if the subproblems s1 and s2 have the same priority. More...

void	initializeOptSense (OptSense::SENSE sense)
	Can be used to initialize the sense of the optimization in derived classes, if this has not been already performed when the constructor of Master has been called. More...

virtual void	initializeParameters ()
	Is only a dummy. More...

virtual void	initializePools (ArrayBuffer< Constraint * > &constraints, ArrayBuffer< Constraint * > &cuts, ArrayBuffer< Variable * > &variables, int varPoolSize, int cutPoolSize, bool dynamicCutPool=false)
	Is overloaded such that also a first set of cutting planes can be inserted into the cutting plane pool. More...

virtual void	initializePools (ArrayBuffer< Constraint * > &constraints, ArrayBuffer< Variable * > &variables, int varPoolSize, int cutPoolSize, bool dynamicCutPool=false)
	Sets up the default pools for variables, constraints, and cutting planes. More...

Private Member Functions
double	clusterConnection (cluster c, GraphCopy &GC) override
	Is invoked by heuristicInitialLowerBound() More...

void	createCompConnVars (List< CPlanarEdgeVar * > &initVars) override
	Creates variables for complete connectivity. More...

virtual CPlanarEdgeVar *	createVariable (ListIterator< NodePair > &it) override
	Variable creation for nodePair. More...

virtual CPlanarEdgeVar *	createVariable (node a, node b) override
	Variable creation for pair of nodes which is not stored in m_inactiveVariables. More...

virtual CPlanarEdgeVar *	createVariable (node a, node b, double lbound)
	Variable creation for pair of nodes with lower bound. More...

virtual void	generateVariablesForFeasibility (const List< ChunkConnection * > &ccons, List< CPlanarEdgeVar * > &connectVars)

virtual void	getCoefficients (abacus::Constraint con, const List< CPlanarEdgeVar > &connect, List< double > &coeffs) override
	writes coefficients of all orig and connect variables in constraint con into emptied list coeffs More...

double	heuristicInitialUpperBound () override
	Computes a dual bound for the optimal solution. Tries to find as many edge-disjoint Kuratowski subdivisions as possible. If k edge-disjoint groups of subdivisions are found, the upper bound can be initialized with number of edges in underlying graph minus k. More...

virtual double	nextConnectCoeff () override
	Switch to minimization of additional edges, no delta necessary. More...

void	nodeDistances (node u, NodeArray< NodeArray< int >> &dist) override
	Computes the graphtheoretical distances of edges incident to node `u`. More...

Private Attributes
ClusterAnalysis *	m_ca
	Used to check if variables are truly needed wrt to search space reduction (Chimani/Klein) More...

ClusterArray< List< node > >	m_cNodes
	Static storage of cluster node lists to avoid repeated computation. More...

int	m_nSep
	Stores number of separation calls. More...

bool	m_shrink
	If set to true, search space reduction is performed. Reduction is only feasible when only a single independent bag exists, which has to be assured by external partitioning. More...

GraphCopy *	m_ssg
	Search space graph, input graph plus edges modelled by initial variables. More...

Friends
class	CPlanaritySub

Additional Inherited Members
Public Types inherited from ogdf::cluster_planarity::CP_MasterBase
enum	solutionState { solutionState::Undefined, solutionState::CPlanar, solutionState::NonCPlanar }

Public Types inherited from abacus::Master
enum	BRANCHINGSTRAT { CloseHalf, CloseHalfExpensive }
	This enumeration defines the two currently implemented branching variable selection strategies. More...

enum	CONELIMMODE { NoConElim, NonBinding, Basic }
	This enumeration defines the ways for automatic constraint elimination during the cutting plane phase. More...

enum	ENUMSTRAT { BestFirst, BreadthFirst, DepthFirst, DiveAndBest }
	The enumeration defining the different enumeration strategies for the branch and bound algorithm. More...

enum	OSISOLVER { Cbc, Clp, CPLEX, DyLP, FortMP, GLPK, MOSEK, OSL, SoPlex, SYMPHONY, XPRESS_MP, Gurobi, Csdp }
	This enumeration defines which solvers can be used to solve the LP-relaxations. More...

enum	PRIMALBOUNDMODE { NoPrimalBound, Optimum, OptimumOne }
	This enumeration provides various methods for the initialization of the primal bound. More...

enum	SKIPPINGMODE { SkipByNode, SkipByLevel }
	The way nodes are skipped for the generation of cuts. More...

enum	STATUS { Optimal, Error, OutOfMemory, Unprocessed, Processing, Guaranteed, MaxLevel, MaxCpuTime, MaxNSub, MaxCowTime, ExceptionFathom }
	The various statuses of the optimization process. More...

enum	VARELIMMODE { NoVarElim, ReducedCost }
	This enumeration defines the ways for automatic variable elimination during the column generation algorithm. More...

enum	VBCMODE { NoVbc, File, Pipe }
	This enumeration defines what kind of output can be generated for the VBCTOOL. More...

Static Public Member Functions inherited from abacus::AbacusRoot
static bool	ascii2bool (const string &str)
	Converts the string str to a boolean value. More...

static bool	endsWith (const string &str, const string &end)
	Returns true if str ends with end, false otherwise. More...

static double	fracPart (double x)
	Returns the absolute value of the fractional part of x. More...

static const char *	onOff (bool value)
	Converts a boolean variable to the strings "on" and "off". More...

Public Attributes inherited from ogdf::cluster_planarity::CP_MasterBase
bool	m_solByHeuristic

solutionState	m_solState

Static Public Attributes inherited from abacus::Master
static const char *	BRANCHINGSTRAT_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	CONELIMMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	ENUMSTRAT_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	OSISOLVER_ []
	Array for the literal values for possible Osi solvers. More...

static const char *	PRIMALBOUNDMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	SKIPPINGMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	STATUS_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	VARELIMMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	VBCMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

Protected Attributes inherited from ogdf::cluster_planarity::CP_MasterBase
double	globalDualBound

double	globalPrimalBound

int	m_activeRepairs

double	m_branchingGap

const ClusterGraph *	m_C
	Pointers to the given Clustergraph and underlying Graph are stored. More...

List< NodePair >	m_connectionOneEdges
	stores optimization success state More...

abacus::StandardPool< abacus::Constraint, abacus::Variable > *	m_cutConnPool
	Cut pools for connectivity and Kuratowski constraints. More...

abacus::StandardPool< abacus::Constraint, abacus::Variable > *	m_cutKuraPool
	Kuratowski Cuts. More...

const Graph *	m_G

double	m_heuristicFractionalBound

int	m_heuristicLevel

List< NodePair >	m_inactiveVariables

double	m_kuratowskiBoundHigh

double	m_kuratowskiBoundLow

string *	m_maxCpuTime
	Time threshold for optimization. More...

bool	m_mpHeuristic
	Indicates if simple max planar subgraph heuristic should be used to derive lower bound if only root cluster exists. More...

int	m_nCConsAdded

int	m_nHeuristicPermutationLists

int	m_nHeuristicRuns

int	m_nKConsAdded

int	m_nKuratowskiIterations

int	m_nKuratowskiSupportGraphs
	Keeps track of created variables. More...

int	m_nMaxVars

int	m_nSubdivisions

int	m_numAddVariables

ArrayBuffer< int >	m_repairStat

GraphCopy *	m_solutionGraph

int	m_solvesLP

double	m_strongConstraintViolation

double	m_strongVariableViolation

bool	m_usePerturbation

NodeArray< NodeArray< bool > >	m_varCreated
	Keeps track of variables that are currently inactive during optimization. More...

int	m_varsAdded

int	m_varsBranch

int	m_varsCut

int	m_varsInit

int	m_varsKura

int	m_varsMax

int	m_varsPotential

int	m_varsPrice

Detailed Description

Definition at line 62 of file CPlanarityMaster.h.

Constructor & Destructor Documentation

◆ CPlanarityMaster()

ogdf::cluster_planarity::CPlanarityMaster::CPlanarityMaster	(	const ClusterGraph &	C,
		int	heuristicLevel = `0`,
		int	heuristicRuns = `2`,
		double	heuristicOEdgeBound = `0.3`,
		int	heuristicNPermLists = `5`,
		int	kuratowskiIterations = `3`,
		int	subdivisions = `10`,
		int	kSupportGraphs = `3`,
		double	kuratowskiHigh = `0.75`,
		double	kuratowskiLow = `0.3`,
		bool	perturbation = `false`,
		double	branchingGap = `0.4`,
		const char *	time = `"00:20:00"`
	)

explicit

◆ ~CPlanarityMaster()

virtual ogdf::cluster_planarity::CPlanarityMaster::~CPlanarityMaster ( )

virtual

Destruction.

Member Function Documentation

◆ addExternalConnections()

void ogdf::cluster_planarity::CPlanarityMaster::addExternalConnections	(	cluster	c,
		List< CPlanarEdgeVar * > &	connectVars
	)

protected

Create variables for external cluster connections in case we search only in the bag-reduced search space.

◆ addInnerConnections()

void ogdf::cluster_planarity::CPlanarityMaster::addInnerConnections	(	cluster	c,
		List< CPlanarEdgeVar * > &	connectVars
	)

protected

Adds inner cluster connection variables in bag-reduced search space.

◆ branchingOEdgeSelectGap()

double ogdf::cluster_planarity::CPlanarityMaster::branchingOEdgeSelectGap ( ) const

inline

Definition at line 137 of file CPlanarityMaster.h.

◆ clusterConnection()

double ogdf::cluster_planarity::CPlanarityMaster::clusterConnection	(	cluster	c,
		GraphCopy &	GC
	)

overrideprivatevirtual

Is invoked by heuristicInitialLowerBound()

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ createCompConnVars()

void ogdf::cluster_planarity::CPlanarityMaster::createCompConnVars ( List< CPlanarEdgeVar * > & initVars )

overrideprivatevirtual

Creates variables for complete connectivity.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ createInitialVariables()

void ogdf::cluster_planarity::CPlanarityMaster::createInitialVariables ( List< CPlanarEdgeVar * > & initVars )

overrideprotectedvirtual

All variables that have to be present at start of optimization are created here. Their number is returned.

Implements ogdf::cluster_planarity::CP_MasterBase.

◆ createVariable() [1/3]

virtual CPlanarEdgeVar* ogdf::cluster_planarity::CPlanarityMaster::createVariable ( ListIterator< NodePair > & it )

inlineoverrideprivatevirtual

Variable creation for nodePair.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

Definition at line 364 of file CPlanarityMaster.h.

◆ createVariable() [2/3]

virtual CPlanarEdgeVar* ogdf::cluster_planarity::CPlanarityMaster::createVariable	(	node	a,
		node	b
	)

inlineoverrideprivatevirtual

Variable creation for pair of nodes which is not stored in m_inactiveVariables.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

Definition at line 386 of file CPlanarityMaster.h.

◆ createVariable() [3/3]

virtual CPlanarEdgeVar* ogdf::cluster_planarity::CPlanarityMaster::createVariable	(	node	a,
		node	b,
		double	lbound
	)

inlineprivatevirtual

Variable creation for pair of nodes with lower bound.

Definition at line 375 of file CPlanarityMaster.h.

◆ firstSub()

virtual abacus::Sub* ogdf::cluster_planarity::CPlanarityMaster::firstSub ( )

overridevirtual

Should return a pointer to the first subproblem of the optimization, i.e., the root node of the enumeration tree.

This is a pure virtual function since a pointer to a problem specific subproblem should be returned, which is derived from the class Sub.

Implements abacus::Master.

◆ generateVariablesForFeasibility()

virtual void ogdf::cluster_planarity::CPlanarityMaster::generateVariablesForFeasibility	(	const List< ChunkConnection * > &	ccons,
		List< CPlanarEdgeVar * > &	connectVars
	)

privatevirtual

◆ getClusterGraph()

const ClusterGraph* ogdf::cluster_planarity::CPlanarityMaster::getClusterGraph ( ) const

inline

Definition at line 101 of file CPlanarityMaster.h.

◆ getClusterNodes() [1/2]

const List<node>& ogdf::cluster_planarity::CPlanarityMaster::getClusterNodes ( cluster c ) const

inline

Returns reference to cluster nodes member list for c.

Definition at line 226 of file CPlanarityMaster.h.

◆ getClusterNodes() [2/2]

void ogdf::cluster_planarity::CPlanarityMaster::getClusterNodes	(	cluster	c,
		List< node > &	nodeList
	)		const

inline

Copies cluster nodes from member list to parameter list. Should be used if node list needs to be altered.

Definition at line 230 of file CPlanarityMaster.h.

◆ getCoefficients()

virtual void ogdf::cluster_planarity::CPlanarityMaster::getCoefficients	(	abacus::Constraint *	con,
		const List< CPlanarEdgeVar * > &	connect,
		List< double > &	coeffs
	)

overrideprivatevirtual

writes coefficients of all orig and connect variables in constraint con into emptied list coeffs

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ getConnectionOptimalSolutionEdges()

void ogdf::cluster_planarity::CPlanarityMaster::getConnectionOptimalSolutionEdges ( List< NodePair > & edges ) const

overridevirtual

Returns nodePairs of connecting optimal solution edges in list edges.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ getGraph()

const Graph* ogdf::cluster_planarity::CPlanarityMaster::getGraph ( ) const

inline

Definition at line 98 of file CPlanarityMaster.h.

◆ getHeuristicFractionalBound()

double ogdf::cluster_planarity::CPlanarityMaster::getHeuristicFractionalBound ( ) const

inline

Definition at line 139 of file CPlanarityMaster.h.

◆ getHeuristicLevel()

int ogdf::cluster_planarity::CPlanarityMaster::getHeuristicLevel ( ) const

inline

Definition at line 127 of file CPlanarityMaster.h.

◆ getHeuristicRuns()

int ogdf::cluster_planarity::CPlanarityMaster::getHeuristicRuns ( ) const

inline

Definition at line 129 of file CPlanarityMaster.h.

◆ getKBoundHigh()

double ogdf::cluster_planarity::CPlanarityMaster::getKBoundHigh ( ) const

inline

Definition at line 131 of file CPlanarityMaster.h.

◆ getKBoundLow()

double ogdf::cluster_planarity::CPlanarityMaster::getKBoundLow ( ) const

inline

Definition at line 133 of file CPlanarityMaster.h.

◆ getKIterations()

int ogdf::cluster_planarity::CPlanarityMaster::getKIterations ( ) const

inline

Definition at line 121 of file CPlanarityMaster.h.

◆ getMPHeuristic()

bool ogdf::cluster_planarity::CPlanarityMaster::getMPHeuristic ( ) const

inline

Definition at line 143 of file CPlanarityMaster.h.

◆ getNKuratowskiSupportGraphs()

int ogdf::cluster_planarity::CPlanarityMaster::getNKuratowskiSupportGraphs ( ) const

inline

Definition at line 125 of file CPlanarityMaster.h.

◆ getNSubdivisions()

int ogdf::cluster_planarity::CPlanarityMaster::getNSubdivisions ( ) const

inline

Definition at line 123 of file CPlanarityMaster.h.

◆ getNumAddVariables()

int ogdf::cluster_planarity::CPlanarityMaster::getNumAddVariables ( ) const

inline

Definition at line 145 of file CPlanarityMaster.h.

◆ getNumInactiveVars()

int ogdf::cluster_planarity::CPlanarityMaster::getNumInactiveVars ( )

inline

Definition at line 223 of file CPlanarityMaster.h.

◆ getStdConstraintsFileName()

const char* ogdf::cluster_planarity::CPlanarityMaster::getStdConstraintsFileName ( )

inline

The name of the file that contains the standard, i.e., non-cut, constraints (may be deleted by ABACUS and shouldn't be stored twice)

Definition at line 221 of file CPlanarityMaster.h.

◆ getStrongConstraintViolation()

double ogdf::cluster_planarity::CPlanarityMaster::getStrongConstraintViolation ( ) const

inline

Definition at line 147 of file CPlanarityMaster.h.

◆ getStrongVariableViolation()

double ogdf::cluster_planarity::CPlanarityMaster::getStrongVariableViolation ( ) const

inline

Definition at line 149 of file CPlanarityMaster.h.

◆ goodVar()

bool ogdf::cluster_planarity::CPlanarityMaster::goodVar	(	node	a,
		node	b
	)

overrideprotectedvirtual

Node pair is potential candidate for new edge variable.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ heuristicInitialLowerBound()

double ogdf::cluster_planarity::CPlanarityMaster::heuristicInitialLowerBound ( )

overrideprotectedvirtual

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ heuristicInitialUpperBound()

double ogdf::cluster_planarity::CPlanarityMaster::heuristicInitialUpperBound ( )

overrideprivatevirtual

Computes a dual bound for the optimal solution. Tries to find as many edge-disjoint Kuratowski subdivisions as possible. If k edge-disjoint groups of subdivisions are found, the upper bound can be initialized with number of edges in underlying graph minus k.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ heuristicLevel()

void ogdf::cluster_planarity::CPlanarityMaster::heuristicLevel ( int level )

inline

Definition at line 171 of file CPlanarityMaster.h.

◆ initializeOptimization()

virtual void ogdf::cluster_planarity::CPlanarityMaster::initializeOptimization ( )

overrideprotectedvirtual

The default implementation of initializeOptimization() does nothing.

This virtual function can be used as an entrance point to perform some initializations after optimize() is called.

Implements ogdf::cluster_planarity::CP_MasterBase.

◆ isCP()

bool ogdf::cluster_planarity::CPlanarityMaster::isCP ( )

inlineoverrideprotectedvirtual

Derives and returns c-planarity property either directly or indirectly from computation results.

Implements ogdf::cluster_planarity::CP_MasterBase.

Definition at line 258 of file CPlanarityMaster.h.

◆ nextConnectCoeff()

virtual double ogdf::cluster_planarity::CPlanarityMaster::nextConnectCoeff ( )

inlineoverrideprivatevirtual

Switch to minimization of additional edges, no delta necessary.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

Definition at line 359 of file CPlanarityMaster.h.

◆ nMaxVars()

int ogdf::cluster_planarity::CPlanarityMaster::nMaxVars ( ) const

inline

Definition at line 95 of file CPlanarityMaster.h.

◆ nodeDistances()

void ogdf::cluster_planarity::CPlanarityMaster::nodeDistances	(	node	u,
		NodeArray< NodeArray< int >> &	dist
	)

overrideprivatevirtual

Computes the graphtheoretical distances of edges incident to node u.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ numberOfHeuristicPermutationLists()

int ogdf::cluster_planarity::CPlanarityMaster::numberOfHeuristicPermutationLists ( ) const

inline

Definition at line 141 of file CPlanarityMaster.h.

◆ perturbation()

bool ogdf::cluster_planarity::CPlanarityMaster::perturbation ( ) const

inline

Definition at line 135 of file CPlanarityMaster.h.

◆ printGraph()

void ogdf::cluster_planarity::CPlanarityMaster::printGraph ( const Graph & G )

Simple output function to print the given graph to the console. Used for debugging only.

◆ searchSpaceGraph()

const GraphCopy* ogdf::cluster_planarity::CPlanarityMaster::searchSpaceGraph ( ) const

inline

Definition at line 108 of file CPlanarityMaster.h.

◆ setHeuristicFractionalBound()

void ogdf::cluster_planarity::CPlanarityMaster::setHeuristicFractionalBound ( double b )

inline

Definition at line 177 of file CPlanarityMaster.h.

◆ setHeuristicPermutationLists()

void ogdf::cluster_planarity::CPlanarityMaster::setHeuristicPermutationLists ( int n )

inline

Definition at line 179 of file CPlanarityMaster.h.

◆ setHeuristicRuns()

void ogdf::cluster_planarity::CPlanarityMaster::setHeuristicRuns ( int n )

inline

Definition at line 173 of file CPlanarityMaster.h.

◆ setKBoundHigh()

void ogdf::cluster_planarity::CPlanarityMaster::setKBoundHigh ( double n )

inline

Definition at line 167 of file CPlanarityMaster.h.

◆ setKBoundLow()

void ogdf::cluster_planarity::CPlanarityMaster::setKBoundLow ( double n )

inline

Definition at line 169 of file CPlanarityMaster.h.

◆ setKIterations()

void ogdf::cluster_planarity::CPlanarityMaster::setKIterations ( int n )

inline

Definition at line 159 of file CPlanarityMaster.h.

◆ setMPHeuristic()

void ogdf::cluster_planarity::CPlanarityMaster::setMPHeuristic ( bool b )

inline

Switches use of lower bound heuristic.

Definition at line 182 of file CPlanarityMaster.h.

◆ setNHeuristicRuns()

void ogdf::cluster_planarity::CPlanarityMaster::setNHeuristicRuns ( int n )

inline

Definition at line 165 of file CPlanarityMaster.h.

◆ setNKuratowskiSupportGraphs()

void ogdf::cluster_planarity::CPlanarityMaster::setNKuratowskiSupportGraphs ( int n )

inline

Definition at line 163 of file CPlanarityMaster.h.

◆ setNSubdivisions()

void ogdf::cluster_planarity::CPlanarityMaster::setNSubdivisions ( int n )

inline

Definition at line 161 of file CPlanarityMaster.h.

◆ setNumAddVariables()

void ogdf::cluster_planarity::CPlanarityMaster::setNumAddVariables ( int i )

inline

Definition at line 184 of file CPlanarityMaster.h.

◆ setPertubation()

void ogdf::cluster_planarity::CPlanarityMaster::setPertubation ( bool b )

inline

Definition at line 175 of file CPlanarityMaster.h.

◆ setSearchSpaceShrinking()

void ogdf::cluster_planarity::CPlanarityMaster::setSearchSpaceShrinking ( bool b )

inline

Toggles reduction of search space (using only some bag/satchel connections) on/off.

Definition at line 191 of file CPlanarityMaster.h.

◆ setStrongConstraintViolation()

void ogdf::cluster_planarity::CPlanarityMaster::setStrongConstraintViolation ( double d )

inline

Definition at line 186 of file CPlanarityMaster.h.

◆ setStrongVariableViolation()

void ogdf::cluster_planarity::CPlanarityMaster::setStrongVariableViolation ( double d )

inline

Definition at line 188 of file CPlanarityMaster.h.

◆ solutionInducedGraph()

Graph* ogdf::cluster_planarity::CPlanarityMaster::solutionInducedGraph ( )

inlineoverridevirtual

Returns the optimal solution induced Clustergraph.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

Definition at line 115 of file CPlanarityMaster.h.

◆ terminateOptimization()

virtual void ogdf::cluster_planarity::CPlanarityMaster::terminateOptimization ( )

overrideprotectedvirtual

Function that is invoked at the end of the optimization. Does nothing but output in CP_MasterBase.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

◆ updateBestSubGraph()

void ogdf::cluster_planarity::CPlanarityMaster::updateBestSubGraph ( List< NodePair > & connection )

overridevirtual

Updates the "best" Subgraph m_solutionGraph found so far and fills connection with.

Reimplemented from ogdf::cluster_planarity::CP_MasterBase.

Friends And Related Function Documentation

◆ CPlanaritySub

friend class CPlanaritySub

friend

Definition at line 63 of file CPlanarityMaster.h.

Member Data Documentation

◆ m_ca

ClusterAnalysis* ogdf::cluster_planarity::CPlanarityMaster::m_ca

private

Used to check if variables are truly needed wrt to search space reduction (Chimani/Klein)

Definition at line 416 of file CPlanarityMaster.h.

◆ m_cNodes

ClusterArray<List<node> > ogdf::cluster_planarity::CPlanarityMaster::m_cNodes

private

Static storage of cluster node lists to avoid repeated computation.

Definition at line 424 of file CPlanarityMaster.h.

◆ m_nSep

int ogdf::cluster_planarity::CPlanarityMaster::m_nSep

private

Stores number of separation calls.

Definition at line 423 of file CPlanarityMaster.h.

◆ m_shrink

bool ogdf::cluster_planarity::CPlanarityMaster::m_shrink

private

If set to true, search space reduction is performed. Reduction is only feasible when only a single independent bag exists, which has to be assured by external partitioning.

Definition at line 421 of file CPlanarityMaster.h.

◆ m_ssg

GraphCopy* ogdf::cluster_planarity::CPlanarityMaster::m_ssg

private

Search space graph, input graph plus edges modelled by initial variables.

Definition at line 422 of file CPlanarityMaster.h.

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

include/ogdf/cluster/internal/CPlanarityMaster.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CPlanarityMaster()

◆ ~CPlanarityMaster()

Member Function Documentation

◆ addExternalConnections()

◆ addInnerConnections()

◆ branchingOEdgeSelectGap()

◆ clusterConnection()

◆ createCompConnVars()

◆ createInitialVariables()

◆ createVariable() [1/3]

◆ createVariable() [2/3]

◆ createVariable() [3/3]

◆ firstSub()

◆ generateVariablesForFeasibility()

◆ getClusterGraph()

◆ getClusterNodes() [1/2]

◆ getClusterNodes() [2/2]

◆ getCoefficients()

◆ getConnectionOptimalSolutionEdges()

◆ getGraph()

◆ getHeuristicFractionalBound()

◆ getHeuristicLevel()

◆ getHeuristicRuns()

◆ getKBoundHigh()

◆ getKBoundLow()

◆ getKIterations()

◆ getMPHeuristic()

◆ getNKuratowskiSupportGraphs()

◆ getNSubdivisions()

◆ getNumAddVariables()

◆ getNumInactiveVars()

◆ getStdConstraintsFileName()

◆ getStrongConstraintViolation()

◆ getStrongVariableViolation()

◆ goodVar()

◆ heuristicInitialLowerBound()

◆ heuristicInitialUpperBound()

◆ heuristicLevel()

◆ initializeOptimization()

◆ isCP()

◆ nextConnectCoeff()

◆ nMaxVars()

◆ nodeDistances()

◆ numberOfHeuristicPermutationLists()

◆ perturbation()

◆ printGraph()

◆ searchSpaceGraph()

◆ setHeuristicFractionalBound()

◆ setHeuristicPermutationLists()

◆ setHeuristicRuns()

◆ setKBoundHigh()

◆ setKBoundLow()

◆ setKIterations()

◆ setMPHeuristic()

◆ setNHeuristicRuns()

◆ setNKuratowskiSupportGraphs()

◆ setNSubdivisions()

◆ setNumAddVariables()

◆ setPertubation()

◆ setSearchSpaceShrinking()

◆ setStrongConstraintViolation()

◆ setStrongVariableViolation()

◆ solutionInducedGraph()

◆ terminateOptimization()

◆ updateBestSubGraph()

Friends And Related Function Documentation

◆ CPlanaritySub

Member Data Documentation

◆ m_ca

◆ m_cNodes

◆ m_nSep

Open
Graph Drawing
Framework