Open
Graph Drawing
Framework

 v.2012.07
 

MaxCPlanar_Master.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2523 $
3  *
4  * last checkin:
5  * $Author: gutwenger $
6  * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7  ***************************************************************/
8 
48 #ifndef OGDF_MAX_CPLANAR_MASTER_H
49 #define OGDF_MAX_CPLANAR_MASTER_H
50 
51 //#include <ogdf/timer.h>
52 #include <ogdf/basic/GraphCopy.h>
55 #include <ogdf/basic/Logger.h>
56 #include <ogdf/basic/ArrayBuffer.h>
57 
58 #include <abacus/string.h>
59 
60 namespace ogdf {
61 
62 
63 
64 class Master : public ABA_MASTER {
65 
66  friend class Sub;
67 
68  // Pointers to the given Clustergraph and underlying Graph are stored.
69  const ClusterGraph *m_C;
70  const Graph *m_G;
71 
72 
73  // Each time the primal bound is improved, the integer solution induced Graph is built.
74  // \a m_solutionGraph is a pointer to the currently best solution induced Graph.
76 
77  List<nodePair> m_allOneEdges; //<! Contains all nodePairs whose variable is set to 1.0
78  List<nodePair> m_originalOneEdges; //<! Contains original nodePairs whose variable is set to 1.0
79  List<nodePair> m_connectionOneEdges; //<! Contains connection nodePairs whose variable is set to 1.0
80  List<edge> m_deletedOriginalEdges; //<! Contains original edges whose variable is set to 0.0
81 
82 public:
83 
84  // Construction and default values
85  Master(
86  const ClusterGraph &C,
87  int heuristicLevel=1,
88  int heuristicRuns=2,
89  double heuristicOEdgeBound=0.3,
90  int heuristicNPermLists=5,
91  int kuratowskiIterations=3,
92  int subdivisions=10,
93  int kSupportGraphs=3,
94  double kuratowskiHigh=0.7,
95  double kuratowskiLow=0.3,
96  bool perturbation=false,
97  double branchingGap=0.4,
98  const char *time="00:20:00", //maximum computation time
99  bool dopricing = true,
100  bool checkCPlanar = false, //just check c-planarity
101  int numAddVariables = 15,
102  double strongConstraintViolation = 0.3,
103  double strongVariableViolation = 0.3,
104  ABA_MASTER::OUTLEVEL ol=Silent);
105 
106  // Destruction
107  virtual ~Master();
108 
109  // Initialisation of the first Subproblem
110  virtual ABA_SUB *firstSub();
111 
112  // Returns the objective function coefficient of C-edges
113  double epsilon() const {return m_epsilon;}
114 
115  // Returns the number of variables
116  int nMaxVars() const {return m_nMaxVars;}
117 
118  // Returns a pointer to the underlying Graph
119  const Graph *getGraph() const {return m_G;}
120 
121  // Returns a pointer to the given Clustergraph.
122  const ClusterGraph *getClusterGraph() const {return m_C;}
123 
124  // Updates the "best" Subgraph \a m_solutionGraph found so far and fills edge lists with
125  // corresponding edges (nodePairs).
126  void updateBestSubGraph(List<nodePair> &original, List<nodePair> &connection, List<edge> &deleted);
127 
128  // Returns the optimal solution induced Clustergraph
130 
131  // Returns nodePairs of original, connection, deleted or all optimal solution edges in list \a edges.
132  void getAllOptimalSolutionEdges(List<nodePair> &edges) const;
135  void getDeletedEdges(List<edge> &edges) const;
136 
137  // Get parameters
138  const int getKIterations() const {return m_nKuratowskiIterations;}
139  const int getNSubdivisions() const {return m_nSubdivisions;}
141  const int getHeuristicLevel() const {return m_heuristicLevel;}
142  const int getHeuristicRuns() const {return m_nHeuristicRuns;}
143  const double getKBoundHigh() const {return m_kuratowskiBoundHigh;}
144  const double getKBoundLow() const {return m_kuratowskiBoundLow;}
145  const bool perturbation() const {return m_usePerturbation;}
146  const double branchingOEdgeSelectGap() const {return m_branchingGap;}
149  const bool getMPHeuristic() const {return m_mpHeuristic;}
150  const bool getCheckCPlanar() const {return m_checkCPlanar;}
151  const int getNumAddVariables() const {return m_numAddVariables;}
154 
155  // Read global constraint counter, i.e. the number of added constraints of specific type.
156  const int addedKConstraints() const {return m_nKConsAdded;}
157  const int addedCConstraints() const {return m_nCConsAdded;}
158 
159 
160  // Set parameters
165  void setKBoundHigh(double n) {m_kuratowskiBoundHigh = ((n>0.0 && n<1.0) ? n : 0.8);}
166  void setKBoundLow(double n) {m_kuratowskiBoundLow = ((n>0.0 && n<1.0) ? n : 0.2);}
167  void heuristicLevel(int level) {m_heuristicLevel = level;}
169  void setPertubation(bool b) {m_usePerturbation = b;}
172  void setMPHeuristic(bool b) {m_mpHeuristic = b;}
176 
178  void setPortaFile(bool b) {m_porta = b;}
179 
180  // Updating global constraint counter
181  void updateAddedCCons(int n) {m_nCConsAdded += n;}
182  void updateAddedKCons(int n) {m_nKConsAdded += n;}
183 
184  // Returns global primal and dual bounds.
186  double getDualBound() {return globalDualBound;}
187 
188  // Cut pools for connectivity and planarity
190  ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *getCutConnPool() {return m_cutConnPool;}
192  ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *getCutKuraPool() {return m_cutKuraPool;}
193 
197 
198 #ifdef OGDF_DEBUG
199  bool m_solByHeuristic; //solution computed by heuristic or ILP
200  // Simple output function to print the given graph to the console.
201  // Used for debugging only.
202  void printGraph(const Graph &G);
203 #endif
204 
208  {
209  return "StdConstraints.txt";
210  }
211 
213 
214 protected:
215 
216  // Initializes constraints and variables and an initial dual bound.
217  virtual void initializeOptimization();
218 
219  // Function that is invoked at the end of the optimization
220  virtual void terminateOptimization();
221 
223 
224 private:
225 
226  // Computes a dual bound for the optimal solution.
227  // Tries to find as many edge-disjoint Kuratowski subdivisions as possible.
228  // If k edge-disjoint groups of subdivisions are found, the upper bound can be
229  // initialized with number of edges in underlying graph minus k.
231 
232  // Is invoked by heuristicInitialUpperBound()
233  void clusterConnection(cluster c, GraphCopy &GC, double &upperBound);
234 
235  // Computes the graphtheoretical distances of edges incident to node \a u.
236  void nodeDistances(node u, NodeArray<NodeArray<int> > &dist);
237 
238 
239  // Parameters
240  int m_nKuratowskiSupportGraphs; // Maximal number of times the Kuratowski support graph is computed
241  int m_nKuratowskiIterations; // Maximal number of times BoyerMyrvold is invoked
242  int m_nSubdivisions; // Maximal number of extracted Kuratowski subdivisions
243  int m_nMaxVars; // Max Number of variables
244  int m_heuristicLevel; // Indicates if primal heuristic shall be used or not
245  int m_nHeuristicRuns; // Counts how often the primal heuristic has been called
246 
247  bool m_usePerturbation; // Indicates whether C-variables should be perturbated or not
248  double m_branchingGap; // Modifies the branching behaviour
250  int m_nHeuristicPermutationLists; // The number of permutation lists used in the primal heuristic
252  // should be used to derive lower bound if only root cluster exists
253 
254  double m_kuratowskiBoundHigh; // Upper bound for deterministic edge addition in computation of the Supportgraph
255  double m_kuratowskiBoundLow; // Lower bound for deterministic edge deletion in computation of the Supportgraph
256 
257  int m_numAddVariables; // how many variables should i add maximally per pricing round?
258  double m_strongConstraintViolation; // when do i consider a constraint strongly violated -> separate in first stage
259  double m_strongVariableViolation; // when do i consider a variable strongly violated (red.cost) -> separate in first stage
260 
261  ABA_MASTER::OUTLEVEL m_out; // Determines the output level of ABACUS
262  ABA_STRING *m_maxCpuTime; // Time threshold for optimization
263 
264 
265  // The basic objective function coefficient for connection edges.
266  double m_epsilon;
267  // If pertubation is used, this variable stores the largest occuring coeff,
268  // i.e. the one closest to 0. Otherwise it corresponds to \a m_epsilon
270 
271  // Counters for the number of added constraints
285  inline void clearActiveRepairs() {
286  if(m_activeRepairs) {
288  m_activeRepairs = 0;
289  }
290  }
291 
294 
295  inline double getDoubleTime(const ABA_TIMER* act) {
296  long tempo = act->centiSeconds()+100*act->seconds()+6000*act->minutes()+360000*act->hours();
297  return ((double) tempo)/ 100.0;
298  }
299 
300  //number of calls of the fast max planar subgraph heuristic
302 
304  ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE > *m_cutConnPool;
305  ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE > *m_cutKuraPool;
306 
310 
315 
317  double m_delta;
318  double m_deltaCount;
319  double nextConnectCoeff() { return (m_checkCPlanar ? -1 : -m_epsilon) + m_deltaCount--*m_delta; } // TODO-TESTING
321  ++m_varsAdded;
322  EdgeVar* v = new EdgeVar(this, nextConnectCoeff(), EdgeVar::CONNECT, (*it).v1, (*it).v2);
323  v->printMe(Logger::slout());
325  return v;
326  }
329 
330  bool goodVar(node a, node b);
331 
333  bool m_porta;
336  void getCoefficients(ABA_CONSTRAINT* con, const List<EdgeVar *> & orig,
337  const List<EdgeVar* > & connect, List<double> & coeffs);
338 };
339 
340 }//end namespace
341 
342 #endif