|
|||
|
|
|
|||
|
|
#include <ogdf/internal/cluster/MaxCPlanar_Master.h>
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 () |
| virtual ABA_SUB * | firstSub () |
| double | epsilon () const |
| int | nMaxVars () const |
| const Graph * | getGraph () const |
| const ClusterGraph * | getClusterGraph () const |
| void | updateBestSubGraph (List< nodePair > &original, List< nodePair > &connection, List< edge > &deleted) |
| Graph * | solutionInducedGraph () |
| void | getAllOptimalSolutionEdges (List< nodePair > &edges) const |
| void | getOriginalOptimalSolutionEdges (List< nodePair > &edges) const |
| void | getConnectionOptimalSolutionEdges (List< nodePair > &egdes) const |
| void | getDeletedEdges (List< edge > &edges) const |
| const int | getKIterations () const |
| const int | getNSubdivisions () const |
| const int | getNKuratowskiSupportGraphs () const |
| const int | getHeuristicLevel () const |
| const int | getHeuristicRuns () const |
| const double | getKBoundHigh () const |
| const double | getKBoundLow () const |
| const bool | perturbation () const |
| const double | branchingOEdgeSelectGap () const |
| const double | getHeuristicFractionalBound () const |
| const int | numberOfHeuristicPermutationLists () const |
| const bool | getMPHeuristic () const |
| const bool | getCheckCPlanar () const |
| const int | getNumAddVariables () const |
| const double | getStrongConstraintViolation () const |
| const double | getStrongVariableViolation () const |
| const int | addedKConstraints () const |
| const int | addedCConstraints () const |
| void | setKIterations (int n) |
| void | setNSubdivisions (int n) |
| void | setNKuratowskiSupportGraphs (int n) |
| void | setNHeuristicRuns (int n) |
| void | setKBoundHigh (double n) |
| void | setKBoundLow (double n) |
| void | heuristicLevel (int level) |
| void | setHeuristicRuns (int n) |
| void | setPertubation (bool b) |
| void | setHeuristicFractionalBound (double b) |
| void | setHeuristicPermutationLists (int n) |
| void | setMPHeuristic (bool b) |
| Switches use of lower bound heuristic. | |
| void | setNumAddVariables (int i) |
| void | setStrongConstraintViolation (double d) |
| void | setStrongVariableViolation (double d) |
| void | setPortaFile (bool b) |
| If set to true, PORTA output is written in a file. | |
| void | updateAddedCCons (int n) |
| void | updateAddedKCons (int n) |
| double | getPrimalBound () |
| double | getDualBound () |
| ABA_STANDARDPOOL < ABA_CONSTRAINT, ABA_VARIABLE > * | getCutConnPool () |
| Returns cut pool for connectivity. | |
| ABA_STANDARDPOOL < ABA_CONSTRAINT, ABA_VARIABLE > * | getCutKuraPool () |
| Returns cut pool for planarity. | |
| bool & | useDefaultCutPool () |
| const char * | getStdConstraintsFileName () |
| int | getNumInactiveVars () |
Protected Member Functions | |
| virtual void | initializeOptimization () |
| virtual void | terminateOptimization () |
| double | heuristicInitialLowerBound () |
Private Member Functions | |
| double | heuristicInitialUpperBound () |
| void | clusterConnection (cluster c, GraphCopy &GC, double &upperBound) |
| void | nodeDistances (node u, NodeArray< NodeArray< int > > &dist) |
| void | clearActiveRepairs () |
| double | getDoubleTime (const ABA_TIMER *act) |
| double | nextConnectCoeff () |
| EdgeVar * | createVariable (ListIterator< nodePair > &it) |
| void | generateVariablesForFeasibility (const List< ChunkConnection * > &ccons, List< EdgeVar * > &connectVars) |
| bool | goodVar (node a, node b) |
| void | getCoefficients (ABA_CONSTRAINT *con, const List< EdgeVar * > &orig, const List< EdgeVar * > &connect, List< double > &coeffs) |
Private Attributes | |
| const ClusterGraph * | m_C |
| const Graph * | m_G |
| GraphCopy * | m_solutionGraph |
| List< nodePair > | m_allOneEdges |
| List< nodePair > | m_originalOneEdges |
| List< nodePair > | m_connectionOneEdges |
| List< edge > | m_deletedOriginalEdges |
| int | m_nKuratowskiSupportGraphs |
| int | m_nKuratowskiIterations |
| int | m_nSubdivisions |
| int | m_nMaxVars |
| int | m_heuristicLevel |
| int | m_nHeuristicRuns |
| bool | m_usePerturbation |
| double | m_branchingGap |
| double | m_heuristicFractionalBound |
| int | m_nHeuristicPermutationLists |
| bool | m_mpHeuristic |
| Indicates if simple max planar subgraph heuristic. | |
| double | m_kuratowskiBoundHigh |
| double | m_kuratowskiBoundLow |
| int | m_numAddVariables |
| double | m_strongConstraintViolation |
| double | m_strongVariableViolation |
| ABA_MASTER::OUTLEVEL | m_out |
| ABA_STRING * | m_maxCpuTime |
| double | m_epsilon |
| double | m_largestConnectionCoeff |
| int | m_nCConsAdded |
| int | m_nKConsAdded |
| int | m_solvesLP |
| int | m_varsInit |
| int | m_varsAdded |
| int | m_varsPotential |
| int | m_varsMax |
| int | m_varsCut |
| int | m_varsKura |
| int | m_varsPrice |
| int | m_varsBranch |
| int | m_activeRepairs |
| ArrayBuffer< int > | m_repairStat |
| double | globalPrimalBound |
| double | globalDualBound |
| const int | m_fastHeuristicRuns |
| 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. | |
| bool | m_useDefaultCutPool |
| bool | m_checkCPlanar |
| double | m_delta |
| double | m_deltaCount |
| List< nodePair > | m_inactiveVariables |
| bool | m_porta |
| If set to true, PORTA output is written in a file. | |
Friends | |
| class | Sub |
Definition at line 63 of file MaxCPlanar_Master.h.
| 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] |
| const int ogdf::Master::addedCConstraints | ( | ) | const [inline] |
Definition at line 156 of file MaxCPlanar_Master.h.
| const int ogdf::Master::addedKConstraints | ( | ) | const [inline] |
Definition at line 155 of file MaxCPlanar_Master.h.
| const double ogdf::Master::branchingOEdgeSelectGap | ( | ) | const [inline] |
Definition at line 145 of file MaxCPlanar_Master.h.
| void ogdf::Master::clearActiveRepairs | ( | ) | [inline, private] |
Definition at line 284 of file MaxCPlanar_Master.h.
| void ogdf::Master::clusterConnection | ( | cluster | c, |
| GraphCopy & | GC, | ||
| double & | upperBound | ||
| ) | [private] |
| EdgeVar* ogdf::Master::createVariable | ( | ListIterator< nodePair > & | it | ) | [inline, private] |
Definition at line 319 of file MaxCPlanar_Master.h.
| double ogdf::Master::epsilon | ( | ) | const [inline] |
Definition at line 112 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 149 of file MaxCPlanar_Master.h.
| const ClusterGraph* ogdf::Master::getClusterGraph | ( | ) | const [inline] |
Definition at line 121 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 189 of file MaxCPlanar_Master.h.
| ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE>* ogdf::Master::getCutKuraPool | ( | ) | [inline] |
Returns cut pool for planarity.
Definition at line 191 of file MaxCPlanar_Master.h.
| void ogdf::Master::getDeletedEdges | ( | List< edge > & | edges | ) | const |
| double ogdf::Master::getDoubleTime | ( | const ABA_TIMER * | act | ) | [inline, private] |
Definition at line 294 of file MaxCPlanar_Master.h.
| double ogdf::Master::getDualBound | ( | ) | [inline] |
Definition at line 185 of file MaxCPlanar_Master.h.
| const Graph* ogdf::Master::getGraph | ( | ) | const [inline] |
Definition at line 118 of file MaxCPlanar_Master.h.
| const double ogdf::Master::getHeuristicFractionalBound | ( | ) | const [inline] |
Definition at line 146 of file MaxCPlanar_Master.h.
| const int ogdf::Master::getHeuristicLevel | ( | ) | const [inline] |
Definition at line 140 of file MaxCPlanar_Master.h.
| const int ogdf::Master::getHeuristicRuns | ( | ) | const [inline] |
Definition at line 141 of file MaxCPlanar_Master.h.
| const double ogdf::Master::getKBoundHigh | ( | ) | const [inline] |
Definition at line 142 of file MaxCPlanar_Master.h.
| const double ogdf::Master::getKBoundLow | ( | ) | const [inline] |
Definition at line 143 of file MaxCPlanar_Master.h.
| const int ogdf::Master::getKIterations | ( | ) | const [inline] |
Definition at line 137 of file MaxCPlanar_Master.h.
| const bool ogdf::Master::getMPHeuristic | ( | ) | const [inline] |
Definition at line 148 of file MaxCPlanar_Master.h.
| const int ogdf::Master::getNKuratowskiSupportGraphs | ( | ) | const [inline] |
Definition at line 139 of file MaxCPlanar_Master.h.
| const int ogdf::Master::getNSubdivisions | ( | ) | const [inline] |
Definition at line 138 of file MaxCPlanar_Master.h.
| const int ogdf::Master::getNumAddVariables | ( | ) | const [inline] |
Definition at line 150 of file MaxCPlanar_Master.h.
| int ogdf::Master::getNumInactiveVars | ( | ) | [inline] |
Definition at line 211 of file MaxCPlanar_Master.h.
| void ogdf::Master::getOriginalOptimalSolutionEdges | ( | List< nodePair > & | edges | ) | const |
| double ogdf::Master::getPrimalBound | ( | ) | [inline] |
Definition at line 184 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 206 of file MaxCPlanar_Master.h.
| const double ogdf::Master::getStrongConstraintViolation | ( | ) | const [inline] |
Definition at line 151 of file MaxCPlanar_Master.h.
| const double ogdf::Master::getStrongVariableViolation | ( | ) | const [inline] |
Definition at line 152 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 166 of file MaxCPlanar_Master.h.
| virtual void ogdf::Master::initializeOptimization | ( | ) | [protected, virtual] |
| double ogdf::Master::nextConnectCoeff | ( | ) | [inline, private] |
Definition at line 318 of file MaxCPlanar_Master.h.
| int ogdf::Master::nMaxVars | ( | ) | const [inline] |
Definition at line 115 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 147 of file MaxCPlanar_Master.h.
| const bool ogdf::Master::perturbation | ( | ) | const [inline] |
Definition at line 144 of file MaxCPlanar_Master.h.
| void ogdf::Master::setHeuristicFractionalBound | ( | double | b | ) | [inline] |
Definition at line 169 of file MaxCPlanar_Master.h.
| void ogdf::Master::setHeuristicPermutationLists | ( | int | n | ) | [inline] |
Definition at line 170 of file MaxCPlanar_Master.h.
| void ogdf::Master::setHeuristicRuns | ( | int | n | ) | [inline] |
Definition at line 167 of file MaxCPlanar_Master.h.
| void ogdf::Master::setKBoundHigh | ( | double | n | ) | [inline] |
Definition at line 164 of file MaxCPlanar_Master.h.
| void ogdf::Master::setKBoundLow | ( | double | n | ) | [inline] |
Definition at line 165 of file MaxCPlanar_Master.h.
| void ogdf::Master::setKIterations | ( | int | n | ) | [inline] |
Definition at line 160 of file MaxCPlanar_Master.h.
| void ogdf::Master::setMPHeuristic | ( | bool | b | ) | [inline] |
Switches use of lower bound heuristic.
Definition at line 171 of file MaxCPlanar_Master.h.
| void ogdf::Master::setNHeuristicRuns | ( | int | n | ) | [inline] |
Definition at line 163 of file MaxCPlanar_Master.h.
| void ogdf::Master::setNKuratowskiSupportGraphs | ( | int | n | ) | [inline] |
Definition at line 162 of file MaxCPlanar_Master.h.
| void ogdf::Master::setNSubdivisions | ( | int | n | ) | [inline] |
Definition at line 161 of file MaxCPlanar_Master.h.
| void ogdf::Master::setNumAddVariables | ( | int | i | ) | [inline] |
Definition at line 172 of file MaxCPlanar_Master.h.
| void ogdf::Master::setPertubation | ( | bool | b | ) | [inline] |
Definition at line 168 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 177 of file MaxCPlanar_Master.h.
| void ogdf::Master::setStrongConstraintViolation | ( | double | d | ) | [inline] |
Definition at line 173 of file MaxCPlanar_Master.h.
| void ogdf::Master::setStrongVariableViolation | ( | double | d | ) | [inline] |
Definition at line 174 of file MaxCPlanar_Master.h.
| Graph* ogdf::Master::solutionInducedGraph | ( | ) | [inline] |
Definition at line 128 of file MaxCPlanar_Master.h.
| virtual void ogdf::Master::terminateOptimization | ( | ) | [protected, virtual] |
| void ogdf::Master::updateAddedCCons | ( | int | n | ) | [inline] |
Definition at line 180 of file MaxCPlanar_Master.h.
| void ogdf::Master::updateAddedKCons | ( | int | n | ) | [inline] |
Definition at line 181 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 195 of file MaxCPlanar_Master.h.
friend class Sub [friend] |
Definition at line 65 of file MaxCPlanar_Master.h.
double ogdf::Master::globalDualBound [private] |
Definition at line 292 of file MaxCPlanar_Master.h.
double ogdf::Master::globalPrimalBound [private] |
Definition at line 291 of file MaxCPlanar_Master.h.
int ogdf::Master::m_activeRepairs [private] |
Definition at line 282 of file MaxCPlanar_Master.h.
List<nodePair> ogdf::Master::m_allOneEdges [private] |
Definition at line 76 of file MaxCPlanar_Master.h.
double ogdf::Master::m_branchingGap [private] |
Definition at line 247 of file MaxCPlanar_Master.h.
const ClusterGraph* ogdf::Master::m_C [private] |
Definition at line 68 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 313 of file MaxCPlanar_Master.h.
List<nodePair> ogdf::Master::m_connectionOneEdges [private] |
Definition at line 78 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 303 of file MaxCPlanar_Master.h.
ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE >* ogdf::Master::m_cutKuraPool [private] |
Kuratowski Cuts.
Definition at line 304 of file MaxCPlanar_Master.h.
List<edge> ogdf::Master::m_deletedOriginalEdges [private] |
Definition at line 79 of file MaxCPlanar_Master.h.
double ogdf::Master::m_delta [private] |
Definition at line 316 of file MaxCPlanar_Master.h.
double ogdf::Master::m_deltaCount [private] |
Definition at line 317 of file MaxCPlanar_Master.h.
double ogdf::Master::m_epsilon [private] |
Definition at line 265 of file MaxCPlanar_Master.h.
const int ogdf::Master::m_fastHeuristicRuns [private] |
Definition at line 300 of file MaxCPlanar_Master.h.
const Graph* ogdf::Master::m_G [private] |
Definition at line 69 of file MaxCPlanar_Master.h.
double ogdf::Master::m_heuristicFractionalBound [private] |
Definition at line 248 of file MaxCPlanar_Master.h.
int ogdf::Master::m_heuristicLevel [private] |
Definition at line 243 of file MaxCPlanar_Master.h.
List<nodePair> ogdf::Master::m_inactiveVariables [private] |
Definition at line 326 of file MaxCPlanar_Master.h.
double ogdf::Master::m_kuratowskiBoundHigh [private] |
Definition at line 253 of file MaxCPlanar_Master.h.
double ogdf::Master::m_kuratowskiBoundLow [private] |
Definition at line 254 of file MaxCPlanar_Master.h.
double ogdf::Master::m_largestConnectionCoeff [private] |
Definition at line 268 of file MaxCPlanar_Master.h.
ABA_STRING* ogdf::Master::m_maxCpuTime [private] |
Definition at line 261 of file MaxCPlanar_Master.h.
bool ogdf::Master::m_mpHeuristic [private] |
Indicates if simple max planar subgraph heuristic.
Definition at line 250 of file MaxCPlanar_Master.h.
int ogdf::Master::m_nCConsAdded [private] |
Definition at line 271 of file MaxCPlanar_Master.h.
int ogdf::Master::m_nHeuristicPermutationLists [private] |
Definition at line 249 of file MaxCPlanar_Master.h.
int ogdf::Master::m_nHeuristicRuns [private] |
Definition at line 244 of file MaxCPlanar_Master.h.
int ogdf::Master::m_nKConsAdded [private] |
Definition at line 272 of file MaxCPlanar_Master.h.
int ogdf::Master::m_nKuratowskiIterations [private] |
Definition at line 240 of file MaxCPlanar_Master.h.
int ogdf::Master::m_nKuratowskiSupportGraphs [private] |
Definition at line 239 of file MaxCPlanar_Master.h.
int ogdf::Master::m_nMaxVars [private] |
Definition at line 242 of file MaxCPlanar_Master.h.
int ogdf::Master::m_nSubdivisions [private] |
Definition at line 241 of file MaxCPlanar_Master.h.
int ogdf::Master::m_numAddVariables [private] |
Definition at line 256 of file MaxCPlanar_Master.h.
List<nodePair> ogdf::Master::m_originalOneEdges [private] |
Definition at line 77 of file MaxCPlanar_Master.h.
ABA_MASTER::OUTLEVEL ogdf::Master::m_out [private] |
Definition at line 260 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 332 of file MaxCPlanar_Master.h.
ArrayBuffer<int> ogdf::Master::m_repairStat [private] |
Definition at line 283 of file MaxCPlanar_Master.h.
GraphCopy* ogdf::Master::m_solutionGraph [private] |
Definition at line 74 of file MaxCPlanar_Master.h.
int ogdf::Master::m_solvesLP [private] |
Definition at line 273 of file MaxCPlanar_Master.h.
double ogdf::Master::m_strongConstraintViolation [private] |
Definition at line 257 of file MaxCPlanar_Master.h.
double ogdf::Master::m_strongVariableViolation [private] |
Definition at line 258 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 308 of file MaxCPlanar_Master.h.
bool ogdf::Master::m_usePerturbation [private] |
Definition at line 246 of file MaxCPlanar_Master.h.
int ogdf::Master::m_varsAdded [private] |
Definition at line 275 of file MaxCPlanar_Master.h.
int ogdf::Master::m_varsBranch [private] |
Definition at line 281 of file MaxCPlanar_Master.h.
int ogdf::Master::m_varsCut [private] |
Definition at line 278 of file MaxCPlanar_Master.h.
int ogdf::Master::m_varsInit [private] |
Definition at line 274 of file MaxCPlanar_Master.h.
int ogdf::Master::m_varsKura [private] |
Definition at line 279 of file MaxCPlanar_Master.h.
int ogdf::Master::m_varsMax [private] |
Definition at line 277 of file MaxCPlanar_Master.h.
int ogdf::Master::m_varsPotential [private] |
Definition at line 276 of file MaxCPlanar_Master.h.
int ogdf::Master::m_varsPrice [private] |
Definition at line 280 of file MaxCPlanar_Master.h.
