1.1 --- a/src/work/alpar/emptygraph.h Fri Mar 12 20:11:31 2004 +0000
1.2 +++ b/src/work/alpar/emptygraph.h Sat Mar 13 22:40:36 2004 +0000
1.3 @@ -7,7 +7,7 @@
1.4 /// The namespace of HugoLib
1.5 namespace hugo {
1.6
1.7 - // @defgroup empty_graph The EmptyGraph class
1.8 + // @defgroup empty_graph The GraphSkeleton class
1.9 // @{
1.10
1.11 /// An empty graph class.
1.12 @@ -25,21 +25,36 @@
1.13 /// feature, the documentation of a real graph imlementation
1.14 /// like @ref ListGraph or
1.15 /// @ref SmartGraph will just refer to this structure.
1.16 - class EmptyGraph
1.17 + class GraphSkeleton
1.18 {
1.19 public:
1.20
1.21 /// The base type of the node iterators.
1.22 +
1.23 + /// This \c Node is the base type of each node iterators,
1.24 + /// thus each kind of node iterator will convert to this.
1.25 class Node {
1.26 public:
1.27 /// @warning The default constructor sets the iterator
1.28 /// to an undefined value.
1.29 Node() {} //FIXME
1.30 - /// Initialize the iterator to be invalid
1.31 + /// Invalid constructor \& conversion.
1.32 +
1.33 + /// This constructor initializes the iterator to be invalid.
1.34 + /// \sa Invalid for more details.
1.35 +
1.36 Node(Invalid) {}
1.37 - //Node(const Node &) {}
1.38 - bool operator==(Node n) const { return true; } //FIXME
1.39 - bool operator!=(Node n) const { return true; } //FIXME
1.40 + //Node(const Node &) {}
1.41 +
1.42 + /// Two iterators are equal if and only if they point to the
1.43 + /// same object or both are invalid.
1.44 + bool operator==(Node n) const { return true; }
1.45 +
1.46 + /// \sa \ref operator==(Node n)
1.47 + ///
1.48 + bool operator!=(Node n) const { return true; }
1.49 +
1.50 + bool operator<(Node n) const { return true; }
1.51 };
1.52
1.53 /// This iterator goes through each node.
1.54 @@ -48,11 +63,16 @@
1.55 /// @warning The default constructor sets the iterator
1.56 /// to an undefined value.
1.57 NodeIt() {} //FIXME
1.58 + /// Invalid constructor \& conversion.
1.59 +
1.60 /// Initialize the iterator to be invalid
1.61 + /// \sa Invalid for more details.
1.62 NodeIt(Invalid) {}
1.63 /// Sets the iterator to the first node of \c G.
1.64 - NodeIt(const EmptyGraph &G) {}
1.65 - NodeIt(const NodeIt &) {} //FIXME
1.66 + NodeIt(const GraphSkeleton &G) {}
1.67 + /// @warning The default constructor sets the iterator
1.68 + /// to an undefined value.
1.69 + NodeIt(const NodeIt &) {}
1.70 };
1.71
1.72
1.73 @@ -64,9 +84,11 @@
1.74 Edge() {} //FIXME
1.75 /// Initialize the iterator to be invalid
1.76 Edge(Invalid) {}
1.77 - //Edge(const Edge &) {}
1.78 - bool operator==(Edge n) const { return true; } //FIXME
1.79 - bool operator!=(Edge n) const { return true; } //FIXME
1.80 + /// Two iterators are equal if and only if they point to the
1.81 + /// same object or both are invalid.
1.82 + bool operator==(Edge n) const { return true; }
1.83 + bool operator!=(Edge n) const { return true; }
1.84 + bool operator<(Edge n) const { return true; }
1.85 };
1.86
1.87 /// This iterator goes trought the outgoing edges of a certain graph.
1.88 @@ -84,7 +106,7 @@
1.89 /// node
1.90 ///@param n the node
1.91 ///@param G the graph
1.92 - OutEdgeIt(const EmptyGraph & G, Node n) {}
1.93 + OutEdgeIt(const GraphSkeleton & G, Node n) {}
1.94 };
1.95
1.96 class InEdgeIt : public Edge {
1.97 @@ -94,7 +116,7 @@
1.98 InEdgeIt() {}
1.99 /// Initialize the iterator to be invalid
1.100 InEdgeIt(Invalid) {}
1.101 - InEdgeIt(const EmptyGraph &, Node) {}
1.102 + InEdgeIt(const GraphSkeleton &, Node) {}
1.103 };
1.104 // class SymEdgeIt : public Edge {};
1.105 class EdgeIt : public Edge {
1.106 @@ -104,7 +126,7 @@
1.107 EdgeIt() {}
1.108 /// Initialize the iterator to be invalid
1.109 EdgeIt(Invalid) {}
1.110 - EdgeIt(const EmptyGraph &) {}
1.111 + EdgeIt(const GraphSkeleton &) {}
1.112 };
1.113
1.114 /// First node of the graph.
1.115 @@ -156,61 +178,106 @@
1.116 bool valid(const Edge) const { return true;}
1.117
1.118 ///Gives back the \e id of a node.
1.119 +
1.120 + ///\warning Not all graph structure provide this feature.
1.121 + ///
1.122 int id(const Node) const { return 0;}
1.123 ///Gives back the \e id of an edge.
1.124 +
1.125 + ///\warning Not all graph structure provide this feature.
1.126 + ///
1.127 int id(const Edge) const { return 0;}
1.128
1.129 //void setInvalid(Node &) const {};
1.130 //void setInvalid(Edge &) const {};
1.131
1.132 + ///Add a new node to the graph.
1.133 +
1.134 + /// \return the new node.
1.135 Node addNode() { return INVALID;}
1.136 + ///Add a new edge to the graph.
1.137 +
1.138 + ///Add a new edge to the graph with tail node \c tail
1.139 + ///and head node \c head.
1.140 + ///\return the new edge.
1.141 Edge addEdge(Node tail, Node head) { return INVALID;}
1.142
1.143 + /// Deletes a node.
1.144 +
1.145 + ///\warning Not all graph structure provide this feature.
1.146 + ///
1.147 void erase(Node n) {}
1.148 + /// Deletes an edge.
1.149 +
1.150 + ///\warning Not all graph structure provide this feature.
1.151 + ///
1.152 void erase(Edge e) {}
1.153
1.154 + /// Reset the graph.
1.155 +
1.156 + /// This function deletes all edges and nodes of the graph.
1.157 + /// It also frees the memory allocated to store them.
1.158 void clear() {}
1.159
1.160 int nodeNum() const { return 0;}
1.161 int edgeNum() const { return 0;}
1.162
1.163 - EmptyGraph() {}
1.164 - EmptyGraph(const EmptyGraph &G) {}
1.165 + GraphSkeleton() {}
1.166 + GraphSkeleton(const GraphSkeleton &G) {}
1.167
1.168
1.169
1.170 - ///Read/write map from the nodes to type \c T.
1.171 + ///Read/write map of the nodes to type \c T.
1.172 +
1.173 + /// \todo We may need copy constructor
1.174 + /// \todo We may need conversion from other nodetype
1.175 + /// \todo We may need operator=
1.176 +
1.177 template<class T> class NodeMap
1.178 {
1.179 public:
1.180 typedef T ValueType;
1.181 typedef Node KeyType;
1.182
1.183 - NodeMap(const EmptyGraph &G) {}
1.184 - NodeMap(const EmptyGraph &G, T t) {}
1.185 + NodeMap(const GraphSkeleton &G) {}
1.186 + NodeMap(const GraphSkeleton &G, T t) {}
1.187
1.188 + template<typename TT> NodeMap(const NodeMap<TT> &m) {}
1.189 +
1.190 + /// Sets the value of a node.
1.191 +
1.192 + /// Sets the value associated with node \c i to the value \c t.
1.193 + ///
1.194 void set(Node i, T t) {}
1.195 - T get(Node i) const {return *(T*)NULL;} //FIXME: Is it necessary
1.196 - T &operator[](Node i) {return *(T*)NULL;}
1.197 - const T &operator[](Node i) const {return *(T*)NULL;}
1.198 + /// Gets the value of a node.
1.199 + T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary
1.200 + T &operator[](Node i) {return *(T*)0;}
1.201 + const T &operator[](Node i) const {return *(T*)0;}
1.202
1.203 + /// Updates the map if the graph has been changed
1.204 +
1.205 + /// \todo Do we need this?
1.206 + ///
1.207 void update() {}
1.208 void update(T a) {} //FIXME: Is it necessary
1.209 };
1.210
1.211 - ///Read/write map from the edges to type \c T.
1.212 + ///Read/write map of the edges to type \c T.
1.213 +
1.214 + ///Read/write map of the edges to type \c T.
1.215 + ///It behaves exactly the same way as \ref NodeMap.
1.216 template<class T> class EdgeMap
1.217 {
1.218 public:
1.219 typedef T ValueType;
1.220 typedef Edge KeyType;
1.221
1.222 - EdgeMap(const EmptyGraph &G) {}
1.223 - EdgeMap(const EmptyGraph &G, T t) {}
1.224 + EdgeMap(const GraphSkeleton &G) {}
1.225 + EdgeMap(const GraphSkeleton &G, T t) {}
1.226
1.227 void set(Edge i, T t) {}
1.228 - T get(Edge i) const {return *(T*)NULL;}
1.229 - T &operator[](Edge i) {return *(T*)NULL;}
1.230 + T get(Edge i) const {return *(T*)0;}
1.231 + T &operator[](Edge i) {return *(T*)0;}
1.232
1.233 void update() {}
1.234 void update(T a) {} //FIXME: Is it necessary
1.235 @@ -223,7 +290,7 @@
1.236
1.237
1.238
1.239 -// class EmptyBipGraph : public EmptyGraph
1.240 +// class EmptyBipGraph : public Graph Skeleton
1.241 // {
1.242 // class ANode {};
1.243 // class BNode {};