00001 00002 // 00003 // Module : Preprocessing.hh 00004 // Description : Preprocessing for the maximum stable set problem. 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 Heidelberg 00009 // Created on : Thu Apr 06 10:08:39 2006 00010 // Last modified by : - 00011 // Last modified on : - 00012 // Update count : 0 00013 // 00015 // 00016 // Date Name Changes/Extensions 00017 // ---- ---- ------------------ 00018 // 00020 00021 00022 #ifndef PREPROCESSING_HH 00023 #define PREPROCESSING_HH 00024 00025 00026 //#include "abacus/constraint.h" 00027 //#include <vector> 00028 00029 //using namespace std; 00030 00031 00032 class Graph; 00033 class StableSetMaster; 00034 class StableSetStatistics; 00035 00036 00037 00041 class Preprocessing { 00042 00043 public: 00044 00045 // ------------------------------------------------------------------------- 00046 // ------------- M e t h o d s ( p u b l i c ) ---------------------------- 00047 // ------------------------------------------------------------------------- 00048 00057 Preprocessing(StableSetMaster *master, Graph *theGraph, 00058 StableSetStatistics *theStatistics); 00059 00063 virtual ~Preprocessing(); 00064 00071 void preprocessing(); 00072 00073 00074 private: 00075 00076 // ------------------------------------------------------------------------- 00077 // ------------- M e t h o d s ( p r i v a t e ) -------------------------- 00078 // ------------------------------------------------------------------------- 00079 00088 bool fixVariablesClique(); 00089 00097 double* solveLP(); 00098 00106 bool fixVariablesEdgeLP(double *sol); 00107 00108 00109 // ------------------------------------------------------------------------- 00110 // ------------- V a r i a b l e s ( p r i v a t e ) ---------------------- 00111 // ------------------------------------------------------------------------- 00112 00116 StableSetMaster *itsMaster; 00117 00122 Graph *itsGraph; 00123 00127 StableSetStatistics *itsStatistics; 00128 00129 }; 00130 00131 #endif 00132 00133 00134 00135