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
00022
00023
00024 typedef pair<int,int> IntegerPair;
00025
00026
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
00047
00048
00050 Graph () : n_(0), directed_(false) {
00051
00052
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
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
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_;
00097 int n_;
00098 bool directed_;
00099 };
00100
00101
00102 #endif
00103
Algorithm Development Kit 1.0