CliqueConstraint Class Reference

#include <CliqueConstraint.hh>

List of all members.

Public Member Functions

 CliqueConstraint (ABA_MASTER *master, vector< int > *clique, Graph *theGraph)
virtual ~CliqueConstraint ()
int genRow (ABA_ACTIVE< ABA_VARIABLE, ABA_CONSTRAINT > *var, ABA_ROW &row)
virtual double coeff (ABA_VARIABLE *var)
int getSize ()
bool isInConstraint (int node)
virtual bool equal (ABA_CONVAR *cv)
virtual const char * name ()
virtual unsigned hashKey ()


Detailed Description

The class CliqueConstraint is derived from the abstract ABACUS constraint class ABA_CONSTRAINT. It stores a maximal clique and computes the corresponding clique constraint.

Definition at line 39 of file CliqueConstraint.hh.


Constructor & Destructor Documentation

CliqueConstraint::CliqueConstraint ABA_MASTER *  master,
vector< int > *  clique,
Graph theGraph
 

Constructor.

Parameters:
*master Pointer to the corresponding master of the optimization.
*clique Pointer to a vector which stores a clique.
*theGraph Pointer to the object representing the graph of the problem.

Definition at line 51 of file CliqueConstraint.cpp.

References Graph::getFileName(), and Graph::translateNode().

00052                                                    :
00053     ABA_CONSTRAINT(master, NULL, ABA_CSENSE::Less, 1.0, true, false, false),
00054     nodesOfClique(clique->size()),
00055     itsGraph(theGraph)
00056 {
00057     // Store this inequality that it can be checked.
00058     ofstream fout(theGraph->getFileName(), ios::app);
00059 
00060     // Save the clique inequality.
00061     for (int i=0; i<clique->size(); i++) {
00062         nodesOfClique[i] = (*clique)[i];
00063         fout << "  1 x_" << itsGraph->translateNode(nodesOfClique[i]);
00064     }
00065     fout << "  <  1" << endl;
00066     fout.close();
00067 
00068     // Calculate the key.
00069     calculateHashKey();
00070 }

CliqueConstraint::~CliqueConstraint  )  [virtual]
 

Destructor.

Definition at line 76 of file CliqueConstraint.cpp.

00076                                     {
00077 }


Member Function Documentation

double CliqueConstraint::coeff ABA_VARIABLE *  var  )  [virtual]
 

Get coefficient of a variable.

Parameters:
*var Pointer to a variable.
Returns:
The coefficient of the variable var in this clique constraint.

Definition at line 113 of file CliqueConstraint.cpp.

References Node::nodeNumber().

00113                                                 {
00114 
00115     // Cast ABA_VARIABLE* to NODE*.
00116     Node *node = (Node *) var;
00117     // search for this variable in the clique
00118     for (int i=0; i<nodesOfClique.size(); i++) {
00119         if (node->nodeNumber() == nodesOfClique[i]) {
00120             return 1.0;
00121         }
00122     }
00123     return 0.0;
00124 }

bool CliqueConstraint::equal ABA_CONVAR *  cv  )  [virtual]
 

Compare if constraint cv is equal to this constraint.

Parameters:
*cv Pointer to the constraint to be compared with this one.
Returns:
true If both constraints are equal.

false Otherwise.

Definition at line 162 of file CliqueConstraint.cpp.

References hashKey().

00162                                            {
00163 
00164     bool isEqual = true;
00165     if (thisHashKey != ((CliqueConstraint *)cv)->hashKey()) {
00166         isEqual = false;
00167     }
00168     if (nodesOfClique.size() != ((CliqueConstraint *)cv)->getSize()) {
00169         isEqual = false;
00170     }
00171 
00172     for(int i=0; i<nodesOfClique.size(); i++) {
00173         if (!((CliqueConstraint *)cv)->isInConstraint(nodesOfClique[i])) {
00174             isEqual = false;
00175         }
00176     }
00177 
00178     return isEqual;
00179 }

int CliqueConstraint::genRow ABA_ACTIVE< ABA_VARIABLE, ABA_CONSTRAINT > *  var,
ABA_ROW &  row
 

Get constraint in sparse format.

Parameters:
*var Pointer to a variable set.
&row Reference to abacus object storing the inequality.
Returns:
Number of non-zeros in the inequality.

Definition at line 86 of file CliqueConstraint.cpp.

00088 {
00089 //    row.realloc(nodesOfClique.size() + 1);
00090 //    row.clear();
00091     
00092     // Store the indices of the nodes of the clique.
00093     for (int i=0; i<nodesOfClique.size(); i++) {
00094         row.insert(nodesOfClique[i],1.0);
00095     }
00096     // The rhs of the clique.
00097     row.rhs(1);
00098     // Sense of the inequality.
00099     row.sense(ABA_CSENSE::Less);
00100     
00101     return row.nnz();
00102 }

int CliqueConstraint::getSize  ) 
 

Get size of clique.

Parameters:
void 
Returns:
Size of vector nodesOfClique.

Definition at line 130 of file CliqueConstraint.cpp.

00130                               {
00131     return nodesOfClique.size();
00132 }

unsigned CliqueConstraint::hashKey  )  [virtual]
 

This method returns the hashkey of the constraint.

Parameters:
void 
Returns:
The hashkey of the constraint.

Definition at line 201 of file CliqueConstraint.cpp.

Referenced by equal().

00201                                    {
00202     return thisHashKey;
00203 }

bool CliqueConstraint::isInConstraint int  node  ) 
 

Checks if node is member of this constraint.

Parameters:
node A node.
Returns:
true Node is member of this constraint.

false Otherwise.

Definition at line 142 of file CliqueConstraint.cpp.

00142                                               {
00143 
00144     for(int i=0; i<nodesOfClique.size(); i++) {
00145         if (nodesOfClique[i] == node) {
00146             return true;
00147         }
00148     }
00149 
00150     return false;
00151 }

const char * CliqueConstraint::name  )  [virtual]
 

This method returns the name of this constraint.

Parameters:
void 
Returns:
Pointer to the name of this constraint

Definition at line 188 of file CliqueConstraint.cpp.

00188                                    {
00189     return "CliqueConstraint";
00190 }


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