Clique Class Reference

#include <Clique.hh>

List of all members.

Public Member Functions

 Clique (ABA_MASTER *master, Graph *theGraph, int sizeSep)
 ~Clique ()
bool addMaxClique (vector< int > *clique)
int * getLastMaxClique () const
bool allMaximalCliquesFound () const
void setAllCliquesFound ()
int checkMaxCliques (vector< int * > *maxClique, double *xVal_) const


Detailed Description

This class stores all computed maximal cliques by the separation routine for maximal cliques. These maximal cliques are stored in the ABA_BUFFER maxCliquesSep.

Definition at line 40 of file Clique.hh.


Constructor & Destructor Documentation

Clique::Clique ABA_MASTER *  master,
Graph theGraph,
int  sizeSep
 

Constructor.

Parameters:
*master Pointer to the master of the problem.
*theGraph Pointer to the graph.
sizeSep The size of the ABA_BUFFER maxCliqueSep.

Definition at line 39 of file Clique.cpp.

00039                                                               :
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 }

Clique::~Clique  ) 
 

Destructor.

Definition at line 54 of file Clique.cpp.

00054                 {
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


Member Function Documentation

bool Clique::addMaxClique vector< int > *  clique  ) 
 

Add a maximal clique.

Parameters:
*clique Pointer to a vector which stores a clique.
Returns:
true If this clique could be added.

false If the clique is part of a max clique allready found.

Definition at line 80 of file Clique.cpp.

00080                                              {
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(..)

bool Clique::allMaximalCliquesFound  )  const
 

Have all maximal cliques been found?

Parameters:
void 
Returns:
true If all cliques have been found.

false Otherwise.

Definition at line 132 of file Clique.cpp.

00132                                           {
00133     return allCliquesFound;
00134 }

int Clique::checkMaxCliques vector< int * > *  maxClique,
double *  xVal_
const
 

Check all maximal cliques if they are violated.

Parameters:
*maxCliques This is a pointer to a vector storing all violated cliques.
*xVal_ Pointer to the current LP solution.
Returns:
The number of violated cliques.

Definition at line 152 of file Clique.cpp.

00152                                                                         {
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();

int * Clique::getLastMaxClique  )  const
 

Get last max clique found by separation.

Parameters:
void 
Returns:
Pointer to the last maximal clique.

Definition at line 124 of file Clique.cpp.

Referenced by MaxCliquesSeparator::separate().

00124                                     {
00125     return lastClique;
00126 }

void Clique::setAllCliquesFound  ) 
 

Set bool allCliquesFound to value true.

Parameters:
void 
Returns:
void

Definition at line 140 of file Clique.cpp.

00140                                 {
00141     allCliquesFound = true;
00142 }


The documentation for this class was generated from the following files:
Generated on Fri Apr 28 15:50:00 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO