C:/Programme/home/Administrator/CD/stableSetCode/Graph.cpp

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : Graph.cpp
00004 //  Description      : Manage the graph of a problem instance.
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       : Wed Apr 05 10:57:14 2006
00010 //  Last modified by : -
00011 //  Last modified on : -
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
00017 //  ----        ----            ------------------
00018 //
00020 
00021 #include "Graph.hh"
00022 #include <iostream>
00023 
00024 using namespace std;
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 // Store given information. Initialize the variables.
00037 // -----------------------------------------------------------------------------
00038 Graph::Graph(ABA_MASTER *master, int nodeNumber, int edgeNumber, bool weighted,
00039              char *fileName):
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 }
00056 
00057 
00058 // -----------------------------------------------------------------------------
00059 // D e s t r u c t o r
00060 // -----------------------------------------------------------------------------
00061 Graph::~Graph() {
00062 
00063     if (weighted_) {
00064         delete [] weightsOfNodes;
00065     }
00066     for (int i=adjacentList.size()-1; i>=0; i--) {
00067         adjacentList[i].clear();
00068     }
00069 }
00070 
00071 
00072 // -----------------------------------------------------------------------------
00073 // p u s h A d j a z e n t N o d e s
00074 // -----------------------------------------------------------------------------
00075 void Graph::pushAdjacentNodes(int rightNode, int leftNode) {
00076     adjacentList[rightNode].push_back(leftNode);
00077     adjacentList[leftNode].push_back(rightNode);
00078 }
00079 
00080 
00081 // -----------------------------------------------------------------------------
00082 // p u s h W e i g h t
00083 //
00084 // Store the weight of node i.
00085 // -----------------------------------------------------------------------------
00086 void Graph::pushWeight(int i, double weight) {
00087     weightsOfNodes[i] = weight;
00088 }
00089 
00090 
00091 // -----------------------------------------------------------------------------
00092 // s o r t A d j a z e n s L i s t
00093 //
00094 // Sort each adjacent list.
00095 // -----------------------------------------------------------------------------
00096 void Graph::sortAdjacentList() {
00097 
00098     for (int i=0; i<numberOfNodes_; i++) {
00099         sort(adjacentList[i].begin(), adjacentList[i].end());
00100     }
00101 }
00102 
00103 
00104 // -----------------------------------------------------------------------------
00105 // n u m b e r O f N o de s
00106 // -----------------------------------------------------------------------------
00107 int Graph::numberOfNodes() const {
00108     return numberOfNodes_;
00109 }
00110 
00111 
00112 // -----------------------------------------------------------------------------
00113 // n u m b e r O f E d g e s
00114 // -----------------------------------------------------------------------------
00115 int Graph::numberOfEdges() const {
00116     return numberOfEdges_;
00117 }
00118 
00119 
00120 // -----------------------------------------------------------------------------
00121 // g e t A d j a c e n t L i s t
00122 // -----------------------------------------------------------------------------
00123 vector<int> *Graph::getAdjacentList(int i) {
00124     return &adjacentList[i];
00125 }
00126 
00127 
00128 // -----------------------------------------------------------------------------
00129 // a d j a c e n t L i s t S i z e
00130 //
00131 // This function returns the number of adjacent nodes to node i.
00132 // -----------------------------------------------------------------------------
00133 int Graph::adjacentListSize(int i) const {
00134     return adjacentList[i].size();
00135 }
00136 
00137 
00138 // -----------------------------------------------------------------------------
00139 // a d j a c e n t L i s t E l e m e n t
00140 //
00141 // This function returns the j-th element of adjacent list of node i.
00142 // -----------------------------------------------------------------------------
00143 int Graph::adjacentListElement(int i, int j) const {
00144     return adjacentList[i][j];
00145 }
00146 
00147 
00148 // -----------------------------------------------------------------------------
00149 // i s M e m b e r O f A d j a c e n t L i s t
00150 //
00151 // This function checks if a node is member of the adjacent list of the
00152 // node with index index. The adjacent list is sorted and therfore we can use
00153 // information from a previous search and so we start by index begin.
00154 // -----------------------------------------------------------------------------
00155 bool Graph::isMemberOfAdjacentList(int index, int &begin, int node) const {
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 }
00170 
00171 
00172 // -----------------------------------------------------------------------------
00173 // w e i g h t e d
00174 // -----------------------------------------------------------------------------
00175 bool Graph::weighted() const {
00176     return weighted_;
00177 }
00178 
00179 
00180 // -----------------------------------------------------------------------------
00181 // w e i g h t
00182 // -----------------------------------------------------------------------------
00183 double Graph::weight(int i) const {
00184     return weightsOfNodes[i];
00185 }
00186 
00187 
00188 // -----------------------------------------------------------------------------
00189 // i n i t i a l i z e T r a n s l a t o r
00190 // -----------------------------------------------------------------------------
00191 void Graph::initializeTranslator() {
00192 
00193     translateNodes.resize(numberOfNodes_);
00194 
00195     for (int i=0; i<numberOfNodes_; i++) {
00196         translateNodes[i] = i;
00197     }
00198 
00199 }
00200 
00201 
00202 // -----------------------------------------------------------------------------
00203 // t r a n s l a t e N o d e
00204 //
00205 // Get translation of node 'index'
00206 // -----------------------------------------------------------------------------
00207 int Graph::translateNode(int index) const {
00208     return translateNodes[index];
00209 
00210 }
00211 
00212 
00213 // -----------------------------------------------------------------------------
00214 // d e l e t e N o d e s F r o m G r a p h
00215 //
00216 // Delete all nodes of vector deleteNodes from the adjacent list. Because
00217 // each edge is stored twice we have to delete each node two times.
00218 // The clique has to be sorted.
00219 // Update the translator.
00220 // -----------------------------------------------------------------------------
00221 void Graph::deleteNodesFromGraph(const vector<int> *deleteNodes) {
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(..)
00290 
00291 
00292 // -----------------------------------------------------------------------------
00293 // d e l e t e N o d e s F r o m G r a p h
00294 //
00295 // Delete all nodes of vector deleteNodes from the adjacent list. Because
00296 // each edge is stored twice we have to delete each node from two times.
00297 // This function returns all nodes which have an updates neighborhood.
00298 // -----------------------------------------------------------------------------
00299 void Graph::deleteNodesFromGraph(const vector<int> *deleteNodes,
00300                                  vector<int> *visitedNodes) {
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(..)
00398 
00399 
00400 // -----------------------------------------------------------------------------
00401 // f i x V a r i a b l e s F i r s t L P
00402 //
00403 // Update counter.
00404 // -----------------------------------------------------------------------------
00405 void Graph::fixVariablesFirstLP(int numberOfFixedNodes) {
00406     fixedVariables += numberOfFixedNodes;
00407     fixedVariablesFirstLP = numberOfFixedNodes;
00408 }
00409 
00410 
00411 // -----------------------------------------------------------------------------
00412 // a l l V a r i a b l e s F i x e d
00413 //
00414 // This function checks if all variables have been fixed.
00415 // -----------------------------------------------------------------------------
00416 bool Graph::allVariablesFixed() const {
00417     return (fixedVariables == numberOfNodes_);
00418 }
00419 
00420 
00421 // -----------------------------------------------------------------------------
00422 // g e t F i l e N a m e
00423 // -----------------------------------------------------------------------------
00424 char *Graph::getFileName() {
00425     return theFileName;
00426 }
00427 
00428 
00429 // -----------------------------------------------------------------------------
00430 // g e t D e n s i t y
00431 // -----------------------------------------------------------------------------
00432 double Graph::getDensity() const {
00433     return density;
00434 }
00435 
00436 
00437 
00438 // -----------------------------------------------------------------------------
00439 // p r i n t S t a t i s t i c
00440 //
00441 // Print some information about the fixing of variables.
00442 // -----------------------------------------------------------------------------
00443 void Graph::printStatistic() const{
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()
00451 
00452 
00453 // -----------------------------------------------------------------------------
00454 // o u t p u t
00455 //
00456 // Print some information about the graph itself.
00457 // -----------------------------------------------------------------------------
00458 void Graph::output() const {
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 }
00476 
00477 
00478 
00479 // -----------------------------------------------------------------------------
00480 // --------------- M e t h o d s  ( p r i v a t e ) ----------------------------
00481 // -----------------------------------------------------------------------------
00482 
00483 
00484 // -----------------------------------------------------------------------------
00485 // c a l c u l a t e D e n s i t y
00486 // -----------------------------------------------------------------------------
00487 void Graph::calculateDensity() {
00488     if (numberOfNodes_ == 0 || numberOfNodes_ == 1) {
00489         density = -1;
00490     }
00491     else {
00492         density = (1.0*numberOfEdges_) / numberOfNodes_;
00493         density = density / (numberOfNodes_ -1);
00494         density *= 2;
00495     }
00496 }
00497 
00498 

Generated on Fri Apr 28 15:49:59 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO