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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : Graph.hh
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:56:36 2006
00010 //  Last modified by : -
00011 //  Last modified on : -
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
00017 //  ----        ----            ------------------
00018 //
00020 
00021 
00022 #ifndef GRAPH_HH
00023 #define GRAPH_HH
00024 
00025 #include "abacus/master.h"
00026 #include <vector>
00027 
00028 using namespace std;
00029 
00030 
00031 
00041 class Graph {
00042 
00043 public:
00044 
00045     // -------------------------------------------------------------------------
00046     // ------------- M e t h o d s  ( p u b l i c ) ----------------------------
00047     // -------------------------------------------------------------------------
00048 
00060     Graph(ABA_MASTER *master, int nodeNumber, int edgeNumber, bool weighted,
00061           char *fileName);
00062 
00066     ~Graph();
00067 
00075     void pushAdjacentNodes(int rightNode, int leftNode);
00076 
00084     void pushWeight(int i, double weight);
00085 
00092     void sortAdjacentList();
00093 
00100     int numberOfNodes() const;
00101 
00108     int numberOfEdges() const;
00109 
00116     vector<int> *getAdjacentList(int i);
00117 
00124     int adjacentListSize(int i) const;
00125 
00133     int adjacentListElement(int i, int j) const;
00134 
00145     bool isMemberOfAdjacentList(int index, int &begin, int node) const;
00146 
00154     bool weighted() const;
00155 
00162     double weight(int i) const;
00163 
00170     void initializeTranslator();
00171 
00178     int translateNode(int index) const;
00179 
00186     void deleteNodesFromGraph(const vector<int> *nodesOfClique);
00187 
00195     void deleteNodesFromGraph(const vector<int> *deleteNodes,
00196                               vector<int> *visitedNodes);
00197 
00204     void fixVariablesFirstLP(int numberOfFixedNodes);
00205 
00206 
00207 
00215     bool allVariablesFixed() const;
00216 
00223     char *getFileName();
00224 
00231     double getDensity() const;
00232 
00239     void printStatistic() const;
00240 
00247     void output() const;
00248 
00249 
00250 private:
00251 
00252     // -------------------------------------------------------------------------
00253     // ------------- M e t h o d s  ( p r i v a t e ) --------------------------
00254     // -------------------------------------------------------------------------
00255 
00259     void calculateDensity();
00260 
00261 
00262     // -------------------------------------------------------------------------
00263     // ------------- V a r i a b l e s  ( p r i v a t e ) ----------------------
00264     // -------------------------------------------------------------------------
00265 
00269     ABA_MASTER *master_;
00270 
00274     int numberOfNodes_;
00275 
00279     int numberOfEdges_;
00280 
00284     vector< vector<int> > adjacentList;
00285 
00290     bool weighted_;
00291 
00295     double *weightsOfNodes;
00296 
00300     double density;
00301 
00305     int fixedVariablesFirstLP;
00306 
00310     int fixedVariables;
00311 
00316     vector<int> translateNodes;
00317     
00321     char theFileName[256];
00322 
00323 };// end: class Graph
00324 
00325 #endif
00326 
00327 

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