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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : Clique.cpp
00004 //  Description      : Store cliques for exact clique separation.
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:11:31 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 #include "Clique.hh"
00023 #include "Graph.hh"
00024 #include "StableSetMaster.hh"
00025 
00026 
00027 
00028 // -----------------------------------------------------------------------------
00029 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00030 // -----------------------------------------------------------------------------
00031 
00032 
00033 // -----------------------------------------------------------------------------
00034 // C o n s t r u c t o r
00035 //
00036 // The main part of the consructor is the initialisation of the ABA_BUFFERs to
00037 // store the clique and its hash key.
00038 // -----------------------------------------------------------------------------
00039 Clique::Clique(ABA_MASTER *master, Graph *theGraph, int sizeSep):
00040     master_(master),
00041     itsGraph(theGraph),
00042     allCliquesFound(false),
00043     lastClique(NULL),
00044     lastCliqueNew(false)
00045 {
00046     maxCliquesSep    = new ABA_BUFFER<int*> (master, sizeSep);
00047     keyOfCliqueSep   = new ABA_BUFFER<long> (master, sizeSep);
00048 }
00049 
00050 
00051 // -----------------------------------------------------------------------------
00052 // D e s t r u c t o r
00053 // -----------------------------------------------------------------------------
00054 Clique::~Clique() {
00055 
00056     for (int i=0; i<maxCliquesSep->number(); i++) {
00057         delete [] (*maxCliquesSep)[i];
00058         (*maxCliquesSep)[i] = NULL;
00059     }
00060     maxCliquesSep->clear();
00061     delete maxCliquesSep;
00062 
00063     keyOfCliqueSep->clear();
00064     delete keyOfCliqueSep;
00065 
00066     if (lastCliqueNew) {
00067         delete [] lastClique;
00068     }
00069 
00070 } // end: destructor
00071 
00072 
00073 // -----------------------------------------------------------------------------
00074 // a d d M a x C l i q u e
00075 //
00076 // This function adds a new maximal clique to the ABA_BUFFER of the clique
00077 // constraints of the max clique separation. It first checks if this
00078 // clique is really a new one before it is stored.
00079 // -----------------------------------------------------------------------------
00080 bool Clique::addMaxClique(vector<int> *clique) {
00081 
00082     if (lastCliqueNew) {
00083         delete [] lastClique;
00084         lastCliqueNew = false;
00085     }
00086 
00087     int *newClique = new int[clique->size()+1];
00088     newClique[0]   = clique->size();
00089     for (int i=0; i<clique->size(); i++) {
00090         newClique[i+1] = (*clique)[i];
00091     }
00092 
00093     // Check if this a really a new clique
00094     if (partOfMaximalClique(clique)) {
00095         // Store the last found maximal clique.
00096         lastClique    = newClique;
00097         lastCliqueNew = true;
00098         return false;
00099     }
00100 
00101     // Increase the buffer if necessary.
00102     if (maxCliquesSep->full()) {
00103         maxCliquesSep->realloc(maxCliquesSep->size()*2);
00104         keyOfCliqueSep->realloc(maxCliquesSep->size()*2);
00105     }
00106     // Add new maximal clique.
00107     maxCliquesSep->push(newClique);
00108     // Store the last found maximal clique.
00109     lastClique = newClique;
00110     // Calculate key of this constraint and store it.
00111     keyOfCliqueSep->push(calculateKey(clique));
00112 
00113     // New maximal clique added.
00114     return true;
00115 
00116 }// end: bool addMaxCliqueSep(..)
00117 
00118 
00119 // -----------------------------------------------------------------------------
00120 // g e t L a s t M a x C l i q u e
00121 //
00122 // Return last clique found by the exact max clique separation routine.
00123 // -----------------------------------------------------------------------------
00124 int *Clique::getLastMaxClique() const {
00125     return lastClique;
00126 }
00127 
00128 
00129 // -----------------------------------------------------------------------------
00130 // a l l M a x i m a l C l i q u e s F o u n d
00131 // -----------------------------------------------------------------------------
00132 bool Clique::allMaximalCliquesFound() const {
00133     return allCliquesFound;
00134 }
00135 
00136 
00137 // -----------------------------------------------------------------------------
00138 // s e t A l l C l i q u e s F o u n d
00139 // -----------------------------------------------------------------------------
00140 void Clique::setAllCliquesFound() {
00141     allCliquesFound = true;
00142 }
00143 
00144 
00145 // -----------------------------------------------------------------------------
00146 // c h e c k M a x C l i q u e s
00147 // 
00148 // This function checks all stored cliques if one is violated or not.
00149 // It returns the number of violated clique inequalities. The cliques are
00150 // available through the pointer to a vector with name maxClique.
00151 // -----------------------------------------------------------------------------
00152 int Clique::checkMaxCliques(vector<int*> *maxClique, double *xVal_) const {
00153 //cout << "Start max clique" << endl;
00154     int    i, j;
00155     int    size;
00156     int    numberOfMaxCliques = 0;              // Return value.
00157     double weight;
00158 
00159     for (i=0; i<maxCliquesSep->number(); i++) {
00160         size = (*maxCliquesSep)[i][0];
00161         weight = 0;
00162         for (j=0; j<size; j++) {
00163             weight += xVal_[(*maxCliquesSep)[i][j+1]];
00164         }
00165         if (weight >= 1 + ((StableSetMaster *)master_)->m_minAbsViolationClique) {
00166             maxClique->push_back((*maxCliquesSep)[i]);
00167             numberOfMaxCliques++;
00168         }
00169 
00170     }
00171 
00172     return numberOfMaxCliques;
00173 }// end: int checkMaxCliques();
00174 
00175 
00176 
00177 // -----------------------------------------------------------------------------
00178 // --------------- M e t h o d s  ( p r i v a t e ) ----------------------------
00179 // -----------------------------------------------------------------------------
00180 
00181 
00182 // -----------------------------------------------------------------------------
00183 // c a l c u l a t e K e y
00184 //
00185 // This function calculates a key for a clique. One clique is NOT part of an
00186 // other clique, if there is no natural number that the multiplication of one
00187 // key is equal to the otherkey.
00188 // -----------------------------------------------------------------------------
00189 unsigned long Clique::calculateKey(vector<int> *clique) const {
00190 
00191     // The key to be calculated.
00192     unsigned long key = 1;
00193 
00194     // Calculate the key.
00195     for (int i=0; i<(*clique).size(); i++) {
00196         // Ignore the node which is zero.
00197         if ((*clique)[i] == 0) {
00198             continue;
00199         }
00200         // Update key if possible.
00201         if (MAX_KEY_SIZE / (*clique)[i] > key) {
00202             key *= (*clique)[i];
00203         }
00204         else {
00205             key = 0;
00206             break;
00207         }
00208     }
00209 
00210     return key;
00211 
00212 }// end: unsigned long calculateKey(..)
00213 
00214 
00215 // -----------------------------------------------------------------------------
00216 // p a r t O f M a x i m a l C l i q u e
00217 //
00218 // This function checks if a clique is part of a maximal clique allready found.
00219 // Therefore it is necessary that the array clique is sorted!
00220 // -----------------------------------------------------------------------------
00221 bool Clique::partOfMaximalClique(vector<int> *clique) const {
00222 
00223     int  i, j, k;               // Loop variables.
00224     int  numberOfCliques;       // Number of max cliques allready computed.
00225     bool found;                 // If a vertex could not be found this has value
00226                                 // false.
00227 
00228     // Calculate a key and compare it with all others.
00229     // If the key is a fraction of one other, than compare all
00230     // elements of the clique.
00231     unsigned long key = calculateKey(clique);
00232     
00233     // Check all cliques from the clique separation.
00234     numberOfCliques = maxCliquesSep->number();
00235 
00236     for (i=0; i<numberOfCliques; i++) {
00237         // If key > keyOfCliqueCycle[i] or the number of elements
00238         // of the clique is greater than the clique to be compared:
00239         // continue with next clique.
00240         if (((key == 0) && ((*keyOfCliqueSep)[i] != 0))
00241              || clique->size() > (*maxCliquesSep)[i][0]
00242             ) {
00243            continue;
00244         }
00245         if ((key == 0)
00246             || ((*keyOfCliqueSep)[i] == 0)
00247             || (((*keyOfCliqueSep)[i] % key) == 0)
00248            ) {
00249             // Compare each element.
00250             found = true;
00251             j     = 0;
00252             k     = 1;
00253             while(j < clique->size()) {
00254                 if(!isMemberOfClique(i, k, (*clique)[j])) {
00255                     found = false;
00256                     break;
00257                 }
00258             }
00259             j++;
00260         }
00261         if (found) {
00262             return true;
00263         }
00264     }
00265 
00266     return false;
00267 
00268 }// end: bool partOfMaximalClique(..)
00269 
00270 
00271 // -----------------------------------------------------------------------------
00272 // i s M e m b e r O f C l i q u e
00273 //
00274 // Check if a node is member of a special clique.
00275 // This function uses, that the cliques are sorted.
00276 // index has to start with 1!!
00277 // -----------------------------------------------------------------------------
00278 bool Clique::isMemberOfClique(int index, int &i, int node) const {
00279 
00280     bool isElement = false;
00281     int  size;
00282 
00283     size = (*maxCliquesSep)[index][0];
00284     while (i < (size + 1)) {
00285         if (node <= (*maxCliquesSep)[index][i]) {
00286             // The clique is sorted and so we know that this node is deciding.
00287             if (node == (*maxCliquesSep)[index][i]) {
00288                 isElement = true;
00289             }
00290             break;
00291         }
00292         i++;
00293     }
00294  
00295     return isElement;
00296 
00297 }// end: bool isMemberOfClique(..)
00298 

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