ogdf::Master Class Reference

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

List of all members.

Public Member Functions
	Master (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:20:00", bool dopricing=true, bool checkCPlanar=false, int numAddVariables=15, double strongConstraintViolation=0.3, double strongVariableViolation=0.3, ABA_MASTER::OUTLEVEL ol=Silent)
virtual	~Master ()
const int	addedCConstraints () const
const int	addedKConstraints () const
const double	branchingOEdgeSelectGap () const
double	epsilon () const
virtual ABA_SUB *	firstSub ()
void	getAllOptimalSolutionEdges (List< nodePair > &edges) const
const bool	getCheckCPlanar () const
const ClusterGraph *	getClusterGraph () const
void	getConnectionOptimalSolutionEdges (List< nodePair > &egdes) const
ABA_STANDARDPOOL < ABA_CONSTRAINT, ABA_VARIABLE > *	getCutConnPool ()
	Returns cut pool for connectivity.
ABA_STANDARDPOOL < ABA_CONSTRAINT, ABA_VARIABLE > *	getCutKuraPool ()
	Returns cut pool for planarity.
void	getDeletedEdges (List< edge > &edges) const
double	getDualBound ()
const Graph *	getGraph () const
const double	getHeuristicFractionalBound () const
const int	getHeuristicLevel () const
const int	getHeuristicRuns () const
const double	getKBoundHigh () const
const double	getKBoundLow () const
const int	getKIterations () const
const bool	getMPHeuristic () const
const int	getNKuratowskiSupportGraphs () const
const int	getNSubdivisions () const
const int	getNumAddVariables () const
int	getNumInactiveVars ()
void	getOriginalOptimalSolutionEdges (List< nodePair > &edges) const
double	getPrimalBound ()
const char *	getStdConstraintsFileName ()
const double	getStrongConstraintViolation () const
const double	getStrongVariableViolation () const
void	heuristicLevel (int level)
int	nMaxVars () const
const int	numberOfHeuristicPermutationLists () const
const bool	perturbation () 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.
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.
void	setStrongConstraintViolation (double d)
void	setStrongVariableViolation (double d)
Graph *	solutionInducedGraph ()
void	updateAddedCCons (int n)
void	updateAddedKCons (int n)
void	updateBestSubGraph (List< nodePair > &original, List< nodePair > &connection, List< edge > &deleted)
bool &	useDefaultCutPool ()

Protected Member Functions
double	heuristicInitialLowerBound ()
virtual void	initializeOptimization ()
virtual void	terminateOptimization ()

Private Member Functions
void	clearActiveRepairs ()
void	clusterConnection (cluster c, GraphCopy &GC, double &upperBound)
EdgeVar *	createVariable (ListIterator< nodePair > &it)
void	generateVariablesForFeasibility (const List< ChunkConnection * > &ccons, List< EdgeVar * > &connectVars)
void	getCoefficients (ABA_CONSTRAINT *con, const List< EdgeVar * > &orig, const List< EdgeVar * > &connect, List< double > &coeffs)
double	getDoubleTime (const ABA_TIMER *act)
bool	goodVar (node a, node b)
double	heuristicInitialUpperBound ()
double	nextConnectCoeff ()
void	nodeDistances (node u, NodeArray< NodeArray< int > > &dist)

Private Attributes
double	globalDualBound
double	globalPrimalBound
int	m_activeRepairs
List< nodePair >	m_allOneEdges
double	m_branchingGap
const ClusterGraph *	m_C
bool	m_checkCPlanar
List< nodePair >	m_connectionOneEdges
ABA_STANDARDPOOL < ABA_CONSTRAINT, ABA_VARIABLE > *	m_cutConnPool
	Cut pools for connectivity and Kuratowski constraints.
ABA_STANDARDPOOL < ABA_CONSTRAINT, ABA_VARIABLE > *	m_cutKuraPool
	Kuratowski Cuts.
List< edge >	m_deletedOriginalEdges
double	m_delta
double	m_deltaCount
double	m_epsilon
const int	m_fastHeuristicRuns
const Graph *	m_G
double	m_heuristicFractionalBound
int	m_heuristicLevel
List< nodePair >	m_inactiveVariables
double	m_kuratowskiBoundHigh
double	m_kuratowskiBoundLow
double	m_largestConnectionCoeff
ABA_STRING *	m_maxCpuTime
bool	m_mpHeuristic
	Indicates if simple max planar subgraph heuristic.
int	m_nCConsAdded
int	m_nHeuristicPermutationLists
int	m_nHeuristicRuns
int	m_nKConsAdded
int	m_nKuratowskiIterations
int	m_nKuratowskiSupportGraphs
int	m_nMaxVars
int	m_nSubdivisions
int	m_numAddVariables
List< nodePair >	m_originalOneEdges
ABA_MASTER::OUTLEVEL	m_out
bool	m_porta
	If set to true, PORTA output is written in a file.
ArrayBuffer< int >	m_repairStat
GraphCopy *	m_solutionGraph
int	m_solvesLP
double	m_strongConstraintViolation
double	m_strongVariableViolation
bool	m_useDefaultCutPool
bool	m_usePerturbation
int	m_varsAdded
int	m_varsBranch
int	m_varsCut
int	m_varsInit
int	m_varsKura
int	m_varsMax
int	m_varsPotential
int	m_varsPrice

Friends
class	Sub

---

Detailed Description

Definition at line 64 of file MaxCPlanar_Master.h.

---

Constructor & Destructor Documentation

ogdf::Master::Master	(	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:20:00",
		bool	dopricing = true,
		bool	checkCPlanar = false,
		int	numAddVariables = 15,
		double	strongConstraintViolation = 0.3,
		double	strongVariableViolation = 0.3,
		ABA_MASTER::OUTLEVEL	ol = Silent
	)

virtual ogdf::Master::~Master ( )

virtual

---

Member Function Documentation

const int ogdf::Master::addedCConstraints ( ) const

inline

Definition at line 157 of file MaxCPlanar_Master.h.

const int ogdf::Master::addedKConstraints ( ) const

inline

Definition at line 156 of file MaxCPlanar_Master.h.

const double ogdf::Master::branchingOEdgeSelectGap ( ) const

inline

Definition at line 146 of file MaxCPlanar_Master.h.

void ogdf::Master::clearActiveRepairs ( )

inlineprivate

Definition at line 285 of file MaxCPlanar_Master.h.

void ogdf::Master::clusterConnection ( cluster  c, GraphCopy &  GC, double &  upperBound  )

private

EdgeVar* ogdf::Master::createVariable ( ListIterator< nodePair > &  it )

inlineprivate

Definition at line 320 of file MaxCPlanar_Master.h.

double ogdf::Master::epsilon ( ) const

inline

Definition at line 113 of file MaxCPlanar_Master.h.

virtual ABA_SUB* ogdf::Master::firstSub ( )

virtual

void ogdf::Master::generateVariablesForFeasibility ( const List< ChunkConnection * > &  ccons, List< EdgeVar * > &  connectVars  )

private

void ogdf::Master::getAllOptimalSolutionEdges

(

List< nodePair > &

edges

)

const

const bool ogdf::Master::getCheckCPlanar ( ) const

inline

Definition at line 150 of file MaxCPlanar_Master.h.

const ClusterGraph* ogdf::Master::getClusterGraph ( ) const

inline

Definition at line 122 of file MaxCPlanar_Master.h.

void ogdf::Master::getCoefficients ( ABA_CONSTRAINT *  con, const List< EdgeVar * > &  orig, const List< EdgeVar * > &  connect, List< double > &  coeffs  )

private

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

void ogdf::Master::getConnectionOptimalSolutionEdges

(

List< nodePair > &

egdes

)

const

ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE>* ogdf::Master::getCutConnPool ( )

inline

Returns cut pool for connectivity.

Definition at line 190 of file MaxCPlanar_Master.h.

ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE>* ogdf::Master::getCutKuraPool ( )

inline

Returns cut pool for planarity.

Definition at line 192 of file MaxCPlanar_Master.h.

void ogdf::Master::getDeletedEdges

(

List< edge > &

edges

)

const

double ogdf::Master::getDoubleTime ( const ABA_TIMER *  act )

inlineprivate

Definition at line 295 of file MaxCPlanar_Master.h.

double ogdf::Master::getDualBound ( )

inline

Definition at line 186 of file MaxCPlanar_Master.h.

const Graph* ogdf::Master::getGraph ( ) const

inline

Definition at line 119 of file MaxCPlanar_Master.h.

const double ogdf::Master::getHeuristicFractionalBound ( ) const

inline

Definition at line 147 of file MaxCPlanar_Master.h.

const int ogdf::Master::getHeuristicLevel ( ) const

inline

Definition at line 141 of file MaxCPlanar_Master.h.

const int ogdf::Master::getHeuristicRuns ( ) const

inline

Definition at line 142 of file MaxCPlanar_Master.h.

const double ogdf::Master::getKBoundHigh ( ) const

inline

Definition at line 143 of file MaxCPlanar_Master.h.

const double ogdf::Master::getKBoundLow ( ) const

inline

Definition at line 144 of file MaxCPlanar_Master.h.

const int ogdf::Master::getKIterations ( ) const

inline

Definition at line 138 of file MaxCPlanar_Master.h.

const bool ogdf::Master::getMPHeuristic ( ) const

inline

Definition at line 149 of file MaxCPlanar_Master.h.

const int ogdf::Master::getNKuratowskiSupportGraphs ( ) const

inline

Definition at line 140 of file MaxCPlanar_Master.h.

const int ogdf::Master::getNSubdivisions ( ) const

inline

Definition at line 139 of file MaxCPlanar_Master.h.

const int ogdf::Master::getNumAddVariables ( ) const

inline

Definition at line 151 of file MaxCPlanar_Master.h.

int ogdf::Master::getNumInactiveVars ( )

inline

Definition at line 212 of file MaxCPlanar_Master.h.

void ogdf::Master::getOriginalOptimalSolutionEdges

(

List< nodePair > &

edges

)

const

double ogdf::Master::getPrimalBound ( )

inline

Definition at line 185 of file MaxCPlanar_Master.h.

const char* ogdf::Master::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 207 of file MaxCPlanar_Master.h.

const double ogdf::Master::getStrongConstraintViolation ( ) const

inline

Definition at line 152 of file MaxCPlanar_Master.h.

const double ogdf::Master::getStrongVariableViolation ( ) const

inline

Definition at line 153 of file MaxCPlanar_Master.h.

bool ogdf::Master::goodVar ( node  a, node  b  )

private

double ogdf::Master::heuristicInitialLowerBound ( )

protected

double ogdf::Master::heuristicInitialUpperBound ( )

private

void ogdf::Master::heuristicLevel ( int  level )

inline

Definition at line 167 of file MaxCPlanar_Master.h.

virtual void ogdf::Master::initializeOptimization ( )

protectedvirtual

double ogdf::Master::nextConnectCoeff ( )

inlineprivate

Definition at line 319 of file MaxCPlanar_Master.h.

int ogdf::Master::nMaxVars ( ) const

inline

Definition at line 116 of file MaxCPlanar_Master.h.

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

private

const int ogdf::Master::numberOfHeuristicPermutationLists ( ) const

inline

Definition at line 148 of file MaxCPlanar_Master.h.

const bool ogdf::Master::perturbation ( ) const

inline

Definition at line 145 of file MaxCPlanar_Master.h.

void ogdf::Master::setHeuristicFractionalBound ( double  b )

inline

Definition at line 170 of file MaxCPlanar_Master.h.

void ogdf::Master::setHeuristicPermutationLists ( int  n )

inline

Definition at line 171 of file MaxCPlanar_Master.h.

void ogdf::Master::setHeuristicRuns ( int  n )

inline

Definition at line 168 of file MaxCPlanar_Master.h.

void ogdf::Master::setKBoundHigh ( double  n )

inline

Definition at line 165 of file MaxCPlanar_Master.h.

void ogdf::Master::setKBoundLow ( double  n )

inline

Definition at line 166 of file MaxCPlanar_Master.h.

void ogdf::Master::setKIterations ( int  n )

inline

Definition at line 161 of file MaxCPlanar_Master.h.

void ogdf::Master::setMPHeuristic ( bool  b )

inline

Switches use of lower bound heuristic.

Definition at line 172 of file MaxCPlanar_Master.h.

void ogdf::Master::setNHeuristicRuns ( int  n )

inline

Definition at line 164 of file MaxCPlanar_Master.h.

void ogdf::Master::setNKuratowskiSupportGraphs ( int  n )

inline

Definition at line 163 of file MaxCPlanar_Master.h.

void ogdf::Master::setNSubdivisions ( int  n )

inline

Definition at line 162 of file MaxCPlanar_Master.h.

void ogdf::Master::setNumAddVariables ( int  i )

inline

Definition at line 173 of file MaxCPlanar_Master.h.

void ogdf::Master::setPertubation ( bool  b )

inline

Definition at line 169 of file MaxCPlanar_Master.h.

void ogdf::Master::setPortaFile ( bool  b )

inline

If set to true, PORTA output is written in a file.

Definition at line 178 of file MaxCPlanar_Master.h.

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

inline

Definition at line 174 of file MaxCPlanar_Master.h.

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

inline

Definition at line 175 of file MaxCPlanar_Master.h.

Graph* ogdf::Master::solutionInducedGraph ( )

inline

Definition at line 129 of file MaxCPlanar_Master.h.

virtual void ogdf::Master::terminateOptimization ( )

protectedvirtual

void ogdf::Master::updateAddedCCons ( int  n )

inline

Definition at line 181 of file MaxCPlanar_Master.h.

void ogdf::Master::updateAddedKCons ( int  n )

inline

Definition at line 182 of file MaxCPlanar_Master.h.

void ogdf::Master::updateBestSubGraph	(	List< nodePair > &	original,
		List< nodePair > &	connection,
		List< edge > &	deleted
	)

bool& ogdf::Master::useDefaultCutPool ( )

inline

Returns true if default cut pool is used. Otherwise, separate connectivity and Kuratowski pools are generated and used.

Definition at line 196 of file MaxCPlanar_Master.h.

---

Friends And Related Function Documentation

friend class Sub

friend

Definition at line 66 of file MaxCPlanar_Master.h.

---

Member Data Documentation

double ogdf::Master::globalDualBound

private

Definition at line 293 of file MaxCPlanar_Master.h.

double ogdf::Master::globalPrimalBound

private

Definition at line 292 of file MaxCPlanar_Master.h.

int ogdf::Master::m_activeRepairs

private

Definition at line 283 of file MaxCPlanar_Master.h.

List<nodePair> ogdf::Master::m_allOneEdges

private

Definition at line 77 of file MaxCPlanar_Master.h.

double ogdf::Master::m_branchingGap

private

Definition at line 248 of file MaxCPlanar_Master.h.

const ClusterGraph* ogdf::Master::m_C

private

Definition at line 69 of file MaxCPlanar_Master.h.

bool ogdf::Master::m_checkCPlanar

private

Defines if only clustered planarity is checked, i.e., all edges of the original graph need to be fixed to be part of the solution

Definition at line 314 of file MaxCPlanar_Master.h.

List<nodePair> ogdf::Master::m_connectionOneEdges

private

Definition at line 79 of file MaxCPlanar_Master.h.

ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE >* ogdf::Master::m_cutConnPool

private

Cut pools for connectivity and Kuratowski constraints.

Connectivity Cuts

Definition at line 304 of file MaxCPlanar_Master.h.

ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE >* ogdf::Master::m_cutKuraPool

private

Kuratowski Cuts.

Definition at line 305 of file MaxCPlanar_Master.h.

List<edge> ogdf::Master::m_deletedOriginalEdges

private

Definition at line 80 of file MaxCPlanar_Master.h.

double ogdf::Master::m_delta

private

Definition at line 317 of file MaxCPlanar_Master.h.

double ogdf::Master::m_deltaCount

private

Definition at line 318 of file MaxCPlanar_Master.h.

double ogdf::Master::m_epsilon

private

Definition at line 266 of file MaxCPlanar_Master.h.

const int ogdf::Master::m_fastHeuristicRuns

private

Definition at line 301 of file MaxCPlanar_Master.h.

const Graph* ogdf::Master::m_G

private

Definition at line 70 of file MaxCPlanar_Master.h.

double ogdf::Master::m_heuristicFractionalBound

private

Definition at line 249 of file MaxCPlanar_Master.h.

int ogdf::Master::m_heuristicLevel

private

Definition at line 244 of file MaxCPlanar_Master.h.

List<nodePair> ogdf::Master::m_inactiveVariables

private

Definition at line 327 of file MaxCPlanar_Master.h.

double ogdf::Master::m_kuratowskiBoundHigh

private

Definition at line 254 of file MaxCPlanar_Master.h.

double ogdf::Master::m_kuratowskiBoundLow

private

Definition at line 255 of file MaxCPlanar_Master.h.

double ogdf::Master::m_largestConnectionCoeff

private

Definition at line 269 of file MaxCPlanar_Master.h.

ABA_STRING* ogdf::Master::m_maxCpuTime

private

Definition at line 262 of file MaxCPlanar_Master.h.

bool ogdf::Master::m_mpHeuristic

private

Indicates if simple max planar subgraph heuristic.

Definition at line 251 of file MaxCPlanar_Master.h.

int ogdf::Master::m_nCConsAdded

private

Definition at line 272 of file MaxCPlanar_Master.h.

int ogdf::Master::m_nHeuristicPermutationLists

private

Definition at line 250 of file MaxCPlanar_Master.h.

int ogdf::Master::m_nHeuristicRuns

private

Definition at line 245 of file MaxCPlanar_Master.h.

int ogdf::Master::m_nKConsAdded

private

Definition at line 273 of file MaxCPlanar_Master.h.

int ogdf::Master::m_nKuratowskiIterations

private

Definition at line 241 of file MaxCPlanar_Master.h.

int ogdf::Master::m_nKuratowskiSupportGraphs

private

Definition at line 240 of file MaxCPlanar_Master.h.

int ogdf::Master::m_nMaxVars

private

Definition at line 243 of file MaxCPlanar_Master.h.

int ogdf::Master::m_nSubdivisions

private

Definition at line 242 of file MaxCPlanar_Master.h.

int ogdf::Master::m_numAddVariables

private

Definition at line 257 of file MaxCPlanar_Master.h.

List<nodePair> ogdf::Master::m_originalOneEdges

private

Definition at line 78 of file MaxCPlanar_Master.h.

ABA_MASTER::OUTLEVEL ogdf::Master::m_out

private

Definition at line 261 of file MaxCPlanar_Master.h.

bool ogdf::Master::m_porta

private

If set to true, PORTA output is written in a file.

Definition at line 333 of file MaxCPlanar_Master.h.

ArrayBuffer<int> ogdf::Master::m_repairStat

private

Definition at line 284 of file MaxCPlanar_Master.h.

GraphCopy* ogdf::Master::m_solutionGraph

private

Definition at line 75 of file MaxCPlanar_Master.h.

int ogdf::Master::m_solvesLP

private

Definition at line 274 of file MaxCPlanar_Master.h.

double ogdf::Master::m_strongConstraintViolation

private

Definition at line 258 of file MaxCPlanar_Master.h.

double ogdf::Master::m_strongVariableViolation

private

Definition at line 259 of file MaxCPlanar_Master.h.

bool ogdf::Master::m_useDefaultCutPool

private

Defines if the ABACUS default cut pool or the separate Connectivity and Kuratowski constraint pools are used

Definition at line 309 of file MaxCPlanar_Master.h.

bool ogdf::Master::m_usePerturbation

private

Definition at line 247 of file MaxCPlanar_Master.h.

int ogdf::Master::m_varsAdded

private

Definition at line 276 of file MaxCPlanar_Master.h.

int ogdf::Master::m_varsBranch

private

Definition at line 282 of file MaxCPlanar_Master.h.

int ogdf::Master::m_varsCut

private

Definition at line 279 of file MaxCPlanar_Master.h.

int ogdf::Master::m_varsInit

private

Definition at line 275 of file MaxCPlanar_Master.h.

int ogdf::Master::m_varsKura

private

Definition at line 280 of file MaxCPlanar_Master.h.

int ogdf::Master::m_varsMax

private

Definition at line 278 of file MaxCPlanar_Master.h.

int ogdf::Master::m_varsPotential

private

Definition at line 277 of file MaxCPlanar_Master.h.

int ogdf::Master::m_varsPrice

private

Definition at line 281 of file MaxCPlanar_Master.h.

---

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

• ogdf/internal/cluster/MaxCPlanar_Master.h