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