00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00016
00017
00018
00019
00021
00022
00023 #ifndef EDGE_PROJECTION_HH
00024 #define EDGE_PROJECTION_HH
00025
00026 #include "ProjectionNode.hh"
00027 #include <iostream>
00028 #include <fstream>
00029 #include <vector>
00030
00031 using namespace std;
00032
00033 class StableSetMaster;
00034
00035
00044 class EdgeProjection {
00045
00046 public:
00047
00048
00049
00050
00051
00057 EdgeProjection(vector< vector<int> > *adjacentList);
00058
00062 ~EdgeProjection();
00063
00071 int separate(double *lpValue);
00072
00081 int computeLargeInequality(double *lpValue, StableSetMaster *theMaster);
00082
00089 vector< vector<int>* >* getLHS();
00090
00097 vector<int>* getRHS();
00098
00099
00100 private:
00101
00102
00103
00104
00105
00113 bool edgeSelection(double *lpValue);
00114
00121 void projection();
00122
00131 int separation(double *lpValue, vector< vector<int> > *theLhs,
00132 vector<int> *theRhs);
00133
00141 void lifting(vector< vector<int> > *theLhs, vector<int> *theRhs);
00142
00151 void storeInequalities(vector< vector<int> > *theLhs, vector<int> *theRhs,
00152 double *lpValue);
00153
00161 void cleanUpInequalities(double *lpValue);
00162
00169 void checkStrongProjectability();
00170
00179 vector<int>* computeMaximalClique(vector< vector<int> > *theAdjacentList,
00180 vector<int> *theTranslator);
00181
00189 void computeFalseEdges(vector<int*> *falseEdges);
00190
00198 void getNeighborhood(int node, vector<int> *neighborhood);
00199
00206 void updateGraph();
00207
00214 void updateGraph(vector<int*> *falseEdges);
00215
00222 void addNode(vector<int*> *falseEdges);
00223
00230 void getReducedGraph(vector< vector<int> > *reducedGraph);
00231
00242 int cliqueSeparation(vector< vector<int> > *graph, double *lpValue,
00243 vector< vector<int> > *theLhs);
00244
00253 void solveStableSet(vector<int> *theLhs, int &theRhs,
00254 StableSetMaster *theMaster);
00255
00263 void liftAndStore(vector<int> *theLhs, int theRhs);
00264
00271 int getRandomNumber(int bound) const;
00272
00279 void cleanUp();
00280
00287 void printRoot();
00288
00289
00290
00291
00292
00293
00298 vector<int> translator;
00299
00303 vector< vector<int>* > lhs;
00304
00308 vector<int> rhs;
00309
00313 vector<double> slack;
00314
00319 char *storeInequalitiesFile;
00320
00324 int edge[2];
00325
00329 vector<int> deleteNodes;
00330
00334 vector<int*> deleteEdges;
00335
00339 int graphSize;
00340
00344 vector< vector<bool> > lowerAdjacentMatrix;
00345
00349 vector< int* > projectable;
00350
00354 int *adjacentListSize;
00355
00359 vector< ProjectionNode* > itsNodes;
00360
00364 ProjectionNode* currentNode;
00365
00366 };
00367
00368 #endif