Graph/Graph.h

Go to the documentation of this file.
00001 
00012 #ifndef _GRAPH_H_
00013 #define _GRAPH_H_
00014 
00015 #include <limits>
00016 #include <list>
00017 #include <vector>
00018 
00019 using namespace std;
00020 
00021 // For vertex u, store information about (v,w) where edge (u,v)
00022 // has the designated edge weight w. The first value is the id
00023 // for the vertex v while the second value is the weight w.
00024 typedef pair<int,int>          IntegerPair;
00025 
00026 // Adjacency list for a vertex
00027 typedef list<IntegerPair>    VertexList;
00028 
00030 enum vertexColor { White, Gray, Black };
00031 
00033 enum edgeType { Tree, Backward, Forward, Cross };
00034 
00042 class Graph {
00043 
00044 public:
00045 
00046   // creation interface
00047   // ------------------
00048   //
00050   Graph () : n_(0), directed_(false) {
00051     // by standard we can't create zero-element array, so 
00052     // we create with one element since it won't matter.
00053     vertices_ = new VertexList[1];
00054   }
00055 
00057   Graph (int n, bool d) : n_(n), directed_(d) {
00058     vertices_ = new VertexList[n];
00059   }
00060 
00062   Graph (int n) : n_(n), directed_(false) {
00063     vertices_ = new VertexList[n];
00064   }
00065 
00067   ~Graph () { n_ = -1; delete [] vertices_; }
00068 
00070   void load (char *fileName);
00071 
00072   // read-only information about graph
00073   // ----------------------------
00074   const int numVertices() const { return n_; }
00075   bool directed() const { return directed_; }
00076   bool isEdge (int, int) const;
00077   bool isEdge (int, int, int &) const;
00078   int edgeWeight (int, int) const;
00079 
00080   VertexList::const_iterator begin(int u) const {
00081     return vertices_[u].begin();
00082   }
00083 
00084   VertexList::const_iterator end(int u) const {
00085     return vertices_[u].end();
00086   } 
00087 
00088   // update edge structure of graph (when no weight, assumed to be 1).
00089   // ---------------------------------------------------------------
00090   void addEdge (int u, int v) { addEdge (u, v, 1); }
00091   void addEdge (int, int, int);
00092   bool removeEdge (int, int);
00093 
00094  protected:
00095 
00096   VertexList  *vertices_;  // each vertex has list.
00097   int  n_;                 // size of graph 
00098   bool directed_;          // is graph directed?
00099 };
00100 
00101 
00102 #endif /* _GRAPH_H_ */
00103 
Algorithm Development Kit 1.0