Graph Class Reference

#include <Graph.hh>

List of all members.

Public Member Functions

 Graph (ABA_MASTER *master, int nodeNumber, int edgeNumber, bool weighted, char *fileName)
 ~Graph ()
void pushAdjacentNodes (int rightNode, int leftNode)
void pushWeight (int i, double weight)
void sortAdjacentList ()
int numberOfNodes () const
int numberOfEdges () const
vector< int > * getAdjacentList (int i)
int adjacentListSize (int i) const
int adjacentListElement (int i, int j) const
bool isMemberOfAdjacentList (int index, int &begin, int node) const
bool weighted () const
double weight (int i) const
void initializeTranslator ()
int translateNode (int index) const
void deleteNodesFromGraph (const vector< int > *nodesOfClique)
void deleteNodesFromGraph (const vector< int > *deleteNodes, vector< int > *visitedNodes)
void fixVariablesFirstLP (int numberOfFixedNodes)
bool allVariablesFixed () const
char * getFileName ()
double getDensity () const
void printStatistic () const
void output () const


Detailed Description

This class stores all necessary information about the problem instance:

Definition at line 41 of file Graph.hh.


Constructor & Destructor Documentation

Graph::Graph ABA_MASTER *  master,
int  nodeNumber,
int  edgeNumber,
bool  weighted,
char *  fileName
 

Constructor.

Parameters:
*master Pointer to the master of the problem.
nodeNumber Number of nodes of the problem instance.
edgeNumber Number of edges of the problem instance.
weighted If the problem has weights than this variable is true, otherwise it is false.
*fileName Pointer storing the file name where all computed inequalities are stored.

Definition at line 38 of file Graph.cpp.

00039                             :
00040     master_(master),
00041     numberOfNodes_(nodeNumber),
00042     numberOfEdges_(edgeNumber),
00043     weighted_(weighted),
00044     fixedVariablesFirstLP(0),
00045     fixedVariables(0)
00046 {
00047     adjacentList.resize(nodeNumber);
00048     if (weighted) {
00049         // Allocate weightsOfNodes.
00050         weightsOfNodes = new double[nodeNumber];
00051     }
00052     calculateDensity();
00053     
00054     sprintf( theFileName, "%s", fileName );
00055 }

Graph::~Graph  ) 
 

Destructor.

Definition at line 61 of file Graph.cpp.

00061               {
00062 
00063     if (weighted_) {
00064         delete [] weightsOfNodes;
00065     }
00066     for (int i=adjacentList.size()-1; i>=0; i--) {
00067         adjacentList[i].clear();
00068     }
00069 }


Member Function Documentation

int Graph::adjacentListElement int  i,
int  j
const
 

Get Element of adjacent list.

Parameters:
i Index of a node.
j Index for the adjacent list of node i.
Returns:
j-th element of adjacent list of node i.

Definition at line 143 of file Graph.cpp.

00143                                                  {
00144     return adjacentList[i][j];
00145 }

int Graph::adjacentListSize int  i  )  const
 

Get size of adjacent list.

Parameters:
i Index of a node.
Returns:
Size of adjazens list of node i.

Definition at line 133 of file Graph.cpp.

Referenced by deleteNodesFromGraph(), and StableSetSub::feasible().

00133                                        {
00134     return adjacentList[i].size();
00135 }

bool Graph::allVariablesFixed  )  const
 

Have all variables been fixed?

Parameters:
void 
Returns:
true If all variables have been fixed.

false Otherwise

Definition at line 416 of file Graph.cpp.

00416                                     {
00417     return (fixedVariables == numberOfNodes_);
00418 }

void Graph::deleteNodesFromGraph const vector< int > *  deleteNodes,
vector< int > *  visitedNodes
 

Delete all nodes from the graph and return all nodes with changed neighborhood.

Parameters:
*nodesOfClique Nodes of a clique.
Returns:
void

Definition at line 299 of file Graph.cpp.

References adjacentListSize().

00300                                                             {
00301 
00302     const int NUM_NODES = deleteNodes->size();
00303 
00304     int  i, j, k;               // Loop counter.
00305     int  adjacentListSize;      // Size of an adjacent list.
00306     int  vertex;                // A node.
00307     int size;
00308 
00309     //
00310     // Update adjacent list.
00311     //
00312     // Go through the adjacent list of all nodes of the vector and delete
00313     // node deleteNodes[i] from its adjacent list
00314     for (i=0; i<NUM_NODES; i++) {
00315         adjacentListSize = adjacentList[(*deleteNodes)[i]].size();
00316         for (j=0; j<adjacentListSize; j++) {
00317             vertex = adjacentList[(*deleteNodes)[i]][j];
00318             // Do something only if this is NOT a member of the vector deleteNodes.
00319 
00320             k = 0;
00321             while ((k < (NUM_NODES-1)) && ((*deleteNodes)[k] != vertex)) {
00322                 k++;
00323             }
00324 
00325             if((*deleteNodes)[k] == vertex) {
00326                 continue;
00327             }
00328 
00329             k = 0;
00330             // Find index of vertex deleteNodes[i] in the adjacent list.
00331             if (!isMemberOfAdjacentList(vertex, k, (*deleteNodes)[i])) {
00332                 master_->err() << "ERROR in Graph::deleteNodesFrom";
00333                 master_->err() << "Graph:\n";
00334                 master_->err() << "Vertex " << (*deleteNodes)[i];
00335                 master_->err() << " could not be found in the adjacent list of";
00336                 master_->err() << " node " << vertex << " ." << endl;
00337                 exit(master_->Fatal);
00338             }
00339             k--;
00340             // Remove this element
00341             adjacentList[vertex].erase(adjacentList[vertex].begin() +k);
00342             k = 0;
00343             while ((k < visitedNodes->size())
00344                    && ((*visitedNodes)[k] != vertex)
00345                   ) {
00346                 k++;
00347             }
00348             if (k == visitedNodes->size()) {
00349                 visitedNodes->push_back(vertex);
00350             }
00351             numberOfEdges_--;
00352 
00353         }
00354         adjacentList[(*deleteNodes)[i]].clear();
00355     }
00356     numberOfEdges_ -= (NUM_NODES * (NUM_NODES - 1)) / 2;
00357 
00358 
00359     //
00360     // Remove the nodes from the graph.
00361     //
00362     for (i=NUM_NODES-1; i>=0; i--) {
00363 
00364         adjacentList.erase(adjacentList.begin() + (*deleteNodes)[i]);
00365         numberOfNodes_--;
00366 
00367         for (j=(*deleteNodes)[i]; j<translateNodes.size()-1; j++) {
00368             translateNodes[j] = translateNodes[j+1];
00369         }
00370         translateNodes.pop_back();
00371 
00372         // Update all nodes of the graph and of the list of nodes to be checked.
00373         for (j=0; j<numberOfNodes_; j++) {
00374             size = adjacentList[j].size();
00375             for (k=0; k<size; k++) {
00376                 if (adjacentList[j][k] > (*deleteNodes)[i]) {
00377                     adjacentList[j][k] -= 1;
00378                 }
00379             }
00380 
00381         }
00382         size = visitedNodes->size();
00383         for (j=0; j<size; j++) {
00384             if ((*visitedNodes)[j] > (*deleteNodes)[i]) {
00385                 (*visitedNodes)[j] -= 1;
00386             }
00387         }
00388 
00389 
00390     }
00391 
00392     fixedVariables += NUM_NODES;
00393 
00394     calculateDensity();
00395 //    output();
00396 
00397 }// void deleteNodesFromGraph(..)

void Graph::deleteNodesFromGraph const vector< int > *  nodesOfClique  ) 
 

Delete all nodes of the given vector from the graph.

Parameters:
*nodesOfClique Nodes of a clique.
Returns:
void

Definition at line 221 of file Graph.cpp.

References adjacentListSize(), and isMemberOfAdjacentList().

00221                                                                {
00222 
00223     const int NUM_NODES = deleteNodes->size();
00224     int  i, j, k;               // Loop counter.
00225     int  adjacentListSize;      // Size of an adjacent list.
00226     int  vertex;                // A node.
00227     bool found;                 // Flag which shows if a node is member of
00228                                 // vector nodesOfClique.
00229     int size;
00230 
00231     //
00232     // Update adjacent list.
00233     //
00234     // Go through the adjacent list of all nodes of the vector and delete
00235     // node deleteNodes[i] from its adjacent list
00236     for (i=0; i<NUM_NODES; i++) {
00237         adjacentListSize = adjacentList[(*deleteNodes)[i]].size();
00238         for (j=0; j<adjacentListSize; j++) {
00239             vertex = adjacentList[(*deleteNodes)[i]][j];
00240 
00241             k = 0;
00242             // Find index of vertex deleteNodes[i] in the adjacent list.
00243             if (!isMemberOfAdjacentList(vertex, k, (*deleteNodes)[i])) {
00244                 master_->err() << "ERROR in Graph::deleteNodesFrom";
00245                 master_->err() << "Graph:\n";
00246                 master_->err() << "Vertex " << (*deleteNodes)[i];
00247                 master_->err() << " could not be found in the adjacent list of";
00248                 master_->err() << " node " << vertex << " ." << endl;
00249                 exit(master_->Fatal);
00250             }
00251             k--;
00252             // Remove this element
00253             adjacentList[vertex].erase(adjacentList[vertex].begin() +k);
00254             numberOfEdges_--;
00255 
00256         }
00257         adjacentList[(*deleteNodes)[i]].clear();
00258     }
00259 
00260     //
00261     // Remove the nodes from the graph.
00262     //
00263     for (i=NUM_NODES-1; i>=0; i--) {
00264 
00265         adjacentList.erase(adjacentList.begin() + (*deleteNodes)[i]);
00266         numberOfNodes_--;
00267 
00268         for (j=(*deleteNodes)[i]; j<translateNodes.size()-1; j++) {
00269             translateNodes[j] = translateNodes[j+1];
00270         }
00271         translateNodes.pop_back();
00272 
00273         // Update all nodes of the graph and of the list of nodes to be checked.
00274         for (j=0; j<numberOfNodes_; j++) {
00275             size = adjacentList[j].size();
00276             for (k=0; k<size; k++) {
00277                 if (adjacentList[j][k] > (*deleteNodes)[i]) {
00278                     adjacentList[j][k] -= 1;
00279                 }
00280             }
00281 
00282         }
00283 
00284     }
00285 
00286     calculateDensity();
00287 //    output();
00288 
00289 }// void deleteNodesFromGraph(..)

void Graph::fixVariablesFirstLP int  numberOfFixedNodes  ) 
 

Update counter for fixed nodes.

Parameters:
numberOfFixedNodes Number of nodes which have been fixed.
Returns:
void

Definition at line 405 of file Graph.cpp.

00405                                                       {
00406     fixedVariables += numberOfFixedNodes;
00407     fixedVariablesFirstLP = numberOfFixedNodes;
00408 }

vector< int > * Graph::getAdjacentList int  i  ) 
 

Get adjacent list.

Parameters:
i Index of a node.
Returns:
Adjazens list of node i.

Definition at line 123 of file Graph.cpp.

Referenced by StableSetSub::feasible(), and CliqueHeuristicsSeparator::separate().

00123                                          {
00124     return &adjacentList[i];
00125 }

double Graph::getDensity  )  const
 

Get density of the graph.

Parameters:
void 
Returns:
Density of the graph.

Definition at line 432 of file Graph.cpp.

00432                                {
00433     return density;
00434 }

char * Graph::getFileName  ) 
 

Get name of the file where all computed inequalities are stored.

Parameters:
void 
Returns:
Pointer to a char storing the file name.

Definition at line 424 of file Graph.cpp.

Referenced by CliqueConstraint::CliqueConstraint(), StableSetSub::feasible(), GeneralConstraint::GeneralConstraint(), RankConstraint::RankConstraint(), and StableSetSub::separate().

00424                          {
00425     return theFileName;
00426 }

void Graph::initializeTranslator  ) 
 

Copy the current nodes in translator.

Parameters:
void 
Returns:
void

Definition at line 191 of file Graph.cpp.

00191                                  {
00192 
00193     translateNodes.resize(numberOfNodes_);
00194 
00195     for (int i=0; i<numberOfNodes_; i++) {
00196         translateNodes[i] = i;
00197     }
00198 
00199 }

bool Graph::isMemberOfAdjacentList int  index,
int &  begin,
int  node
const
 

Check if two vertices are adjacent.

Parameters:
index Index of a node.
&begin Reference to an index we start the search in the adjacent list.
node A vertex.
Returns:
true If node is adjacent to vertex index.

false Otherwise.

Definition at line 155 of file Graph.cpp.

Referenced by deleteNodesFromGraph(), StableSetSub::feasible(), and CliqueHeuristicsSeparator::separate().

00155                                                                         {
00156 
00157     bool found = false;
00158     int  size = adjacentList[index].size();
00159 
00160     while((begin < size) && (node > adjacentList[index][begin])) {
00161         begin++;
00162     }
00163     if ((begin < size) && (node == adjacentList[index][begin])) {
00164         found = true;
00165         begin++;
00166     }
00167 
00168     return found;
00169 }

int Graph::numberOfEdges  )  const
 

Get number of edges.

Parameters:
void 
Returns:
Number of edges.

Definition at line 115 of file Graph.cpp.

00115                                {
00116     return numberOfEdges_;
00117 }

int Graph::numberOfNodes  )  const
 

Get number of nodes.

Parameters:
void 
Returns:
Number of nodes.

Definition at line 107 of file Graph.cpp.

Referenced by LowerBoundHeuristic::computeSolution(), StableSetSub::feasible(), StableSetSub::generateBranchRules(), Preprocessing::preprocessing(), StableSetSub::separate(), CliqueHeuristicsSeparator::separate(), StableSetModKSeparator::StableSetModKSeparator(), and StableSetMaster::~StableSetMaster().

00107                                {
00108     return numberOfNodes_;
00109 }

void Graph::output  )  const
 

Print some information about the problem instance.

Parameters:
void 
Returns:
void

Definition at line 458 of file Graph.cpp.

00458                          {
00459 
00460     master_->out()  << "\nGraph:\n";
00461     master_->out()  << "------------------------------------------------------";
00462     master_->out()  << "\nnNodes:\t" << numberOfNodes_;
00463     master_->out()  << "\nnEdges:\t" << numberOfEdges_;
00464     master_->out()  << "\nDensity:\t" << density;
00465     master_->out()  << "\n\nEdges:\n";
00466     for (int i=0; i<numberOfNodes_; i++) {
00467         master_->out()  << "  node[" << i << "]:\t";
00468         for (int j=0; j<adjacentList[i].size(); j++) {
00469             master_->out()  << adjacentList[i][j] << " ";
00470         }
00471         master_->out()  << endl;
00472     }
00473     master_->out()  << "------------------------------------------------------";
00474     master_->out()  << endl << endl;
00475 }

void Graph::printStatistic  )  const
 

Print statistic about fixed nodes.

Parameters:
void 
Returns:
void

Definition at line 443 of file Graph.cpp.

Referenced by StableSetMaster::output().

00443                                 {
00444 
00445     master_->out() << "  Number of fixed variables according to LP\t:  ";
00446     master_->out() << fixedVariablesFirstLP;
00447     master_->out() << "\n  Number of fixed variables according to clique\t:  ";
00448     master_->out() << fixedVariables - fixedVariablesFirstLP;
00449 
00450 }// end: void printStatistic()

void Graph::pushAdjacentNodes int  rightNode,
int  leftNode
 

Store adjacent nodes.

Parameters:
rightNode One end node of the edge.
leftNode The other end node of the edge.
Returns:
void

Definition at line 75 of file Graph.cpp.

00075                                                          {
00076     adjacentList[rightNode].push_back(leftNode);
00077     adjacentList[leftNode].push_back(rightNode);
00078 }

void Graph::pushWeight int  i,
double  weight
 

Set weight of a node.

Parameters:
i Index of node.
weight Weight of node i.
Returns:
void

Definition at line 86 of file Graph.cpp.

00086                                            {
00087     weightsOfNodes[i] = weight;
00088 }

void Graph::sortAdjacentList  ) 
 

Sort each adjazens list.

Parameters:
void 
Returns:
void

Definition at line 96 of file Graph.cpp.

00096                              {
00097 
00098     for (int i=0; i<numberOfNodes_; i++) {
00099         sort(adjacentList[i].begin(), adjacentList[i].end());
00100     }
00101 }

int Graph::translateNode int  index  )  const
 

Translate a node.

Parameters:
index Index of a node.
Returns:
Translation of node.

Definition at line 207 of file Graph.cpp.

Referenced by CliqueConstraint::CliqueConstraint(), GeneralConstraint::GeneralConstraint(), StableSetMaster::output(), and RankConstraint::RankConstraint().

00207                                         {
00208     return translateNodes[index];
00209 
00210 }

double Graph::weight int  i  )  const
 

Get weight of node.

Parameters:
i Index od node.
Returns:
Weight of node i.

Definition at line 183 of file Graph.cpp.

00183                                 {
00184     return weightsOfNodes[i];
00185 }

bool Graph::weighted  )  const
 

Get type of problem.

Parameters:
void 
Returns:
true If the problem is weighted.

false Otherwise.

Definition at line 175 of file Graph.cpp.

Referenced by StableSetSub::improve().

00175                            {
00176     return weighted_;
00177 }


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