OddCycleConstraint Class Reference

#include <OddCycleConstraint.hh>

List of all members.

Public Member Functions

 OddCycleConstraint (ABA_MASTER *master, int oddCycleSize, int *nodes, Graph *itsGraph)
virtual ~OddCycleConstraint ()
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 OddCycleConstraint is derived from the abstract ABACUS constraint class ABA_CONSTRAINT. It stores an odd cycle and computes the corresponding odd cycle constraint.

Definition at line 39 of file OddCycleConstraint.hh.


Constructor & Destructor Documentation

OddCycleConstraint::OddCycleConstraint ABA_MASTER *  master,
int  oddCycleSize,
int *  nodes,
Graph itsGraph
 

Constructor.

Parameters:
*master Pointer to the corresponding master of the optimization.
oddCycleSize The size of the odd cycle
  • the number of nodes in this cycle
*nodes An array with nodes of the odd cycle.
*theGraph Pointer to the object representing the graph of the problem.

Definition at line 52 of file OddCycleConstraint.cpp.

00053                                                                    :
00054     ABA_CONSTRAINT(master, NULL, ABA_CSENSE::Less, (oddCycleSize-1)*0.5, true,
00055                    false, false),
00056     oddCycle(oddCycleSize),
00057     itsGraph(theGraph)
00058 {
00059 
00060     for (int i=0; i<oddCycleSize; i++) {
00061         oddCycle[i] = nodes[i];
00062     }
00063     sort(oddCycle.begin(), oddCycle.end());
00064 
00065     // Store this inequality that it can be checked.
00066     ofstream fout(theGraph->getFileName(), ios::app);
00067     for (int i=0; i<oddCycleSize; i++) {
00068         fout << "  1 x_" << itsGraph->translateNode(oddCycle[i]);
00069     }
00070     fout << "  <  " << (oddCycleSize-1)*0.5 << endl;
00071     fout.close();
00072 
00073     // Calculate the key.
00074     calculateHashKey();
00075 }

OddCycleConstraint::~OddCycleConstraint  )  [virtual]
 

Destructor.

Definition at line 81 of file OddCycleConstraint.cpp.

00081                                         {
00082 }


Member Function Documentation

double OddCycleConstraint::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 odd cycle constraint.

Definition at line 115 of file OddCycleConstraint.cpp.

References Node::nodeNumber().

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

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

Compare if constraint cv is equal to this constraint.

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

false Otherwise.

Definition at line 164 of file OddCycleConstraint.cpp.

References hashKey().

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

int OddCycleConstraint::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 91 of file OddCycleConstraint.cpp.

00093 {
00094     // Store the indices of the nodes of the odd cycle.
00095     for (int i=0; i<oddCycle.size(); i++) {
00096         row.insert(oddCycle[i],1.0);
00097     }
00098     // The rhs of the odd cycle..
00099     row.rhs((oddCycle.size()-1)*0.5);
00100     // Sense of the inequality.
00101     row.sense(ABA_CSENSE::Less);
00102 
00103     return row.nnz();
00104 }

int OddCycleConstraint::getSize  ) 
 

Get size of odd cycle.

Parameters:
void 
Returns:
Size of vector oddCycle.

Definition at line 132 of file OddCycleConstraint.cpp.

00132                                 {
00133     return oddCycle.size();
00134 }

unsigned OddCycleConstraint::hashKey  )  [virtual]
 

This method returns the hashkey of the constraint.

Parameters:
void 
Returns:
The hashkey of the constraint.

Definition at line 203 of file OddCycleConstraint.cpp.

Referenced by equal().

00203                                      {
00204     return thisHashKey;
00205 }

bool OddCycleConstraint::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 144 of file OddCycleConstraint.cpp.

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

const char * OddCycleConstraint::name  )  [virtual]
 

This method returns the name of this constraint.

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

Definition at line 190 of file OddCycleConstraint.cpp.

00190                                      {
00191     return "OddCycleConstraint";
00192 }


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