C:/Programme/home/Administrator/CD/stableSetCode/EdgeProjection.hh

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : EdgeProjection.hh
00004 //  Description      : Separation through edge projection.
00005 //  Author           : Steffen Rebennack
00006 //  Email            : srebenac@ix.urz.uni-heidelberg.de;
00007 //                     steffen.rebennack@web.de
00008 //  Copyright        : (C) 2006 by the University of L'Aquvila and
00009 //                     University of Heidelberg
00010 //  Created on       : Wed Apr 05 08:37:06 2006
00011 //  Last modified by : -
00012 //  Last modified on : -
00013 //  Update count     : 0
00014 //
00016 //
00017 //  Date        Name            Changes/Extensions
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     // ------------- M e t h o d s  ( p u b l i c ) ----------------------------
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     // ------------- M e t h o d s  ( p r i v a t e ) --------------------------
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     // ------------- V a r i a b l e s  ( p r i v a t e ) ----------------------
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

Generated on Fri Apr 28 15:49:59 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO