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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : Clique.hh
00004 //  Description      :
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       : Mon Apr 03 20:17: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 CLIQUE_HH
00023 #define CLIQUE_HH
00024 
00025 #include "abacus/buffer.h"
00026 #include "abacus/master.h"
00027 #include <vector>
00028 
00029 using namespace std;
00030 
00031 class Graph;
00032 
00033 
00034 
00040 class Clique {
00041 
00042 
00043 public:
00044 
00045     // -------------------------------------------------------------------------
00046     // ------------- M e t h o d s  ( p u b l i c ) ----------------------------
00047     // -------------------------------------------------------------------------
00048 
00056     Clique(ABA_MASTER *master, Graph *theGraph, int sizeSep);
00057 
00061     ~Clique();
00062 
00070     bool addMaxClique(vector<int> *clique);
00071 
00078     int* getLastMaxClique() const;
00079 
00087     bool allMaximalCliquesFound() const;
00088 
00094     void setAllCliquesFound();
00095 
00104     int checkMaxCliques(vector<int*> *maxClique, double *xVal_) const;
00105 
00106 
00107 private:
00108 
00109     // -------------------------------------------------------------------------
00110     // ------------- M e t h o d s  ( p r i v a t e ) --------------------------
00111     // -------------------------------------------------------------------------
00112 
00119     unsigned long calculateKey(vector<int> *clique) const;
00120 
00128     bool partOfMaximalClique(vector<int> *clique) const;
00129 
00139     bool isMemberOfClique(int index, int &i, int node) const;
00140 
00141  
00142     // -------------------------------------------------------------------------
00143     // ------------- V a r i a b l e s  ( p r i v a t e ) ----------------------
00144     // -------------------------------------------------------------------------
00145 
00149     const static long MAX_KEY_SIZE = 40000000;
00150 
00154     ABA_MASTER *master_;
00155 
00160     Graph *itsGraph;
00161 
00167     ABA_BUFFER<int*> *maxCliquesSep;
00168 
00172     ABA_BUFFER<long> *keyOfCliqueSep;
00173 
00177     bool allCliquesFound;
00178 
00185     int *lastClique;
00186 
00191     bool lastCliqueNew;
00192 
00193 };
00194 
00195 #endif
00196 
00197 

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