1.1 --- a/src/work/alpar/emptygraph.h Wed Mar 10 16:43:50 2004 +0000
1.2 +++ b/src/work/alpar/emptygraph.h Wed Mar 10 16:46:17 2004 +0000
1.3 @@ -1,144 +1,234 @@
1.4 // -*-mode: c++; -*-
1.5
1.6 -class EmptyGraph
1.7 -{
1.8 -public:
1.9 +#include <invalid.h>
1.10
1.11 - class NodeIt {
1.12 +/// The namespace of HugoLib
1.13 +namespace hugo {
1.14 +
1.15 + // @defgroup empty_graph The EmptyGraph class
1.16 + // @{
1.17 +
1.18 + /// An empty graph class.
1.19 +
1.20 + /// This class provides all the common features of a grapf structure,
1.21 + /// however completely without implementations or real data structures
1.22 + /// behind the interface.
1.23 + /// All graph algorithms should compile with this class, but it will not
1.24 + /// run properly, of course.
1.25 + ///
1.26 + /// It can be used for checking the interface compatibility,
1.27 + /// or it can serve as a skeleton of a new graph structure.
1.28 +
1.29 + class EmptyGraph
1.30 + {
1.31 public:
1.32 - NodeIt() {} //FIXME
1.33 - //NodeIt(const NodeIt &) {}
1.34 - bool operator==(NodeIt n) const {} //FIXME
1.35 - bool operator!=(NodeIt n) const {} //FIXME
1.36 - };
1.37
1.38 - class EachNodeIt : public NodeIt {
1.39 - public:
1.40 - EachNodeIt() {} //FIXME
1.41 - EachNodeIt(const EmptyGraph &) const {}
1.42 - EachNodeIt(const EachNodeIt &) const {} //FIXME
1.43 - };
1.44 + /// The base type of the node iterators.
1.45 + class Node {
1.46 + public:
1.47 + /// @warning The default constructor sets the iterator
1.48 + /// to an undefined value.
1.49 + Node() {} //FIXME
1.50 + /// Initialize the iterator to be invalid
1.51 + Node(Invalid) {};
1.52 + //Node(const Node &) {}
1.53 + bool operator==(Node n) const { return true; } //FIXME
1.54 + bool operator!=(Node n) const { return true; } //FIXME
1.55 + };
1.56
1.57 - class EdgeIt {
1.58 - EdgeIt() {} //FIXME
1.59 - //EdgeIt(const EdgeIt &) {}
1.60 - bool operator==(EdgeIt n) const {} //FIXME
1.61 - bool operator!=(EdgeIt n) const {} //FIXME
1.62 - };
1.63 + /// This iterator goes through each node.
1.64 + class NodeIt : public Node {
1.65 + public:
1.66 + /// @warning The default constructor sets the iterator
1.67 + /// to an undefined value.
1.68 + NodeIt() {} //FIXME
1.69 + /// Initialize the iterator to be invalid
1.70 + NodeIt(Invalid) {};
1.71 + /// Sets the iterator to the first node of \c G.
1.72 + NodeIt(const EmptyGraph &G) {}
1.73 + NodeIt(const NodeIt &) {} //FIXME
1.74 + };
1.75 +
1.76 +
1.77 + /// The base type of the edge iterators.
1.78 + class Edge {
1.79 + public:
1.80 + /// @warning The default constructor sets the iterator
1.81 + /// to an undefined value.
1.82 + Edge() {} //FIXME
1.83 + /// Initialize the iterator to be invalid
1.84 + Edge(Invalid) {};
1.85 + //Edge(const Edge &) {}
1.86 + bool operator==(Edge n) const { return true; } //FIXME
1.87 + bool operator!=(Edge n) const { return true; } //FIXME
1.88 + };
1.89 +
1.90 + /// This iterator goes trought the outgoing edges of a certain graph.
1.91 +
1.92 + class OutEdgeIt : public Edge {
1.93 + public:
1.94 + /// @warning The default constructor sets the iterator
1.95 + /// to an undefined value.
1.96 + OutEdgeIt() {}
1.97 + /// Initialize the iterator to be invalid
1.98 + OutEdgeIt(Invalid) {};
1.99 + /// This constructor sets the iterator to first outgoing edge.
1.100 +
1.101 + /// This constructor set the iterator to the first outgoing edge of
1.102 + /// node
1.103 + ///@param n the node
1.104 + ///@param G the graph
1.105 + OutEdgeIt(const EmptyGraph & G, Node n) {}
1.106 + };
1.107 +
1.108 + class InEdgeIt : public Edge {
1.109 + public:
1.110 + /// @warning The default constructor sets the iterator
1.111 + /// to an undefined value.
1.112 + InEdgeIt() {}
1.113 + /// Initialize the iterator to be invalid
1.114 + InEdgeIt(Invalid) {};
1.115 + InEdgeIt(const EmptyGraph &, Node) {}
1.116 + };
1.117 + // class SymEdgeIt : public Edge {};
1.118 + class EdgeIt : public Edge {
1.119 + public:
1.120 + /// @warning The default constructor sets the iterator
1.121 + /// to an undefined value.
1.122 + EdgeIt() {}
1.123 + /// Initialize the iterator to be invalid
1.124 + EdgeIt(Invalid) {};
1.125 + EdgeIt(const EmptyGraph &) {}
1.126 + };
1.127 +
1.128 + /// First node of the graph.
1.129 +
1.130 + /// \post \c i and the return value will be the first node.
1.131 + ///
1.132 + NodeIt &first(NodeIt &i) const { return i;}
1.133 +
1.134 + /// The first outgoing edge.
1.135 + InEdgeIt &first(InEdgeIt &i, Node n) const { return i;}
1.136 + /// The first incoming edge.
1.137 + OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;}
1.138 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.139 + /// The first edge of the Graph.
1.140 + EdgeIt &first(EdgeIt &i) const { return i;}
1.141 +
1.142 +// Node getNext(Node) const {}
1.143 +// InEdgeIt getNext(InEdgeIt) const {}
1.144 +// OutEdgeIt getNext(OutEdgeIt) const {}
1.145 +// //SymEdgeIt getNext(SymEdgeIt) const {}
1.146 +// EdgeIt getNext(EdgeIt) const {}
1.147 +
1.148 + /// Go to the next node.
1.149 + Node &next(Node &i) const { return i;}
1.150 + /// Go to the next incoming edge.
1.151 + InEdgeIt &next(InEdgeIt &i) const { return i;}
1.152 + /// Go to the next outgoing edge.
1.153 + OutEdgeIt &next(OutEdgeIt &i) const { return i;}
1.154 + //SymEdgeIt &next(SymEdgeIt &) const {}
1.155 + /// Go to the next edge.
1.156 + EdgeIt &next(EdgeIt &i) const { return i;}
1.157 +
1.158 + ///Gives back the head node of an edge.
1.159 + Node head(Edge) const { return INVALID; }
1.160 + ///Gives back the tail node of an edge.
1.161 + Node tail(Edge) const { return INVALID; }
1.162
1.163 - class OutEdgeIt : public EdgeIt {
1.164 - OutEdgeIt() {}
1.165 - OutEdgeIt(const EmptyGraph &, NodeIt) {}
1.166 + // Node aNode(InEdgeIt) const {}
1.167 + // Node aNode(OutEdgeIt) const {}
1.168 + // Node aNode(SymEdgeIt) const {}
1.169 +
1.170 + // Node bNode(InEdgeIt) const {}
1.171 + // Node bNode(OutEdgeIt) const {}
1.172 + // Node bNode(SymEdgeIt) const {}
1.173 +
1.174 + /// Checks if a node iterator is valid
1.175 + bool valid(const Node) const { return true;};
1.176 + /// Checks if an edge iterator is valid
1.177 + bool valid(const Edge) const { return true;};
1.178 +
1.179 + ///Gives back the \e id of a node.
1.180 + int id(const Node) const { return 0;};
1.181 + ///Gives back the \e id of an edge.
1.182 + int id(const Edge) const { return 0;};
1.183 +
1.184 + //void setInvalid(Node &) const {};
1.185 + //void setInvalid(Edge &) const {};
1.186 +
1.187 + Node addNode() { return INVALID;}
1.188 + Edge addEdge(Node tail, Node head) { return INVALID;}
1.189 +
1.190 + void erase(Node n) {}
1.191 + void erase(Edge e) {}
1.192 +
1.193 + void clear() {}
1.194 +
1.195 + int nodeNum() { return 0;}
1.196 + int edgeNum() { return 0;}
1.197 +
1.198 + EmptyGraph() {};
1.199 + EmptyGraph(const EmptyGraph &G) {};
1.200 +
1.201 +
1.202 +
1.203 + ///Read/write map from the nodes to type \c T.
1.204 + template<class T> class NodeMap
1.205 + {
1.206 + public:
1.207 + typedef T ValueType;
1.208 + typedef Node KeyType;
1.209 +
1.210 + NodeMap(const EmptyGraph &G) {}
1.211 + NodeMap(const EmptyGraph &G, T t) {}
1.212 +
1.213 + void set(Node i, T t) {}
1.214 + T get(Node i) const {return *(T*)NULL;} //FIXME: Is it necessary
1.215 + T &operator[](Node i) {return *(T*)NULL;}
1.216 + const T &operator[](Node i) const {return *(T*)NULL;}
1.217 +
1.218 + void update() {}
1.219 + void update(T a) {} //FIXME: Is it necessary
1.220 + };
1.221 +
1.222 + ///Read/write map from the edges to type \c T.
1.223 + template<class T> class EdgeMap
1.224 + {
1.225 + public:
1.226 + typedef T ValueType;
1.227 + typedef Edge KeyType;
1.228 +
1.229 + EdgeMap(const EmptyGraph &G) {}
1.230 + EdgeMap(const EmptyGraph &G, T t) {}
1.231 +
1.232 + void set(Edge i, T t) {}
1.233 + T get(Edge i) const {return *(T*)NULL;}
1.234 + T &operator[](Edge i) {return *(T*)NULL;}
1.235 +
1.236 + void update() {}
1.237 + void update(T a) {} //FIXME: Is it necessary
1.238 + };
1.239 };
1.240
1.241 - class InEdgeIt : public EdgeIt {
1.242 - InEdgeIt() {}
1.243 - InEdgeIt(const EmptyGraph &, NodeIt) {}
1.244 - };
1.245 - // class SymEdgeIt : public EdgeIt {};
1.246 - class EachEdgeIt : public EdgeIt {
1.247 - EachEdgeIt() {}
1.248 - EachEdgeIt(const EmptyGraph &) {}
1.249 - };
1.250 + // @}
1.251
1.252 - EachNodeIt &getFirst(EachNodeIt &) const {}
1.253 - InEdgeIt &getFirst(InEdgeIt &, NodeIt) const {}
1.254 - OutEdgeIt &getFirst(OutEdgeIt &, NodeIt) const {}
1.255 - // SymEdgeIt &getFirst(SymEdgeIt &, NodeIt) const {}
1.256 - EachEdgeIt &getFirst(EachEdgeIt &) const {}
1.257 +};
1.258
1.259 - NodeIt getNext(NodeIt) const {}
1.260 - InEdgeIt getNext(InEdgeIt) const {}
1.261 - OutEdgeIt getNext(OutEdgeIt) const {}
1.262 - //SymEdgeIt getNext(SymEdgeIt) const {}
1.263 - EachEdgeIt getNext(EachEdgeIt) const {}
1.264 -
1.265 - NodeIt &next(NodeIt &) const {}
1.266 - InEdgeIt &next(InEdgeIt &) const {}
1.267 - OutEdgeIt &next(OutEdgeIt &) const {}
1.268 - //SymEdgeIt &next(SymEdgeIt &) const {}
1.269 - EachEdgeIt &next(EachEdgeIt &) const {}
1.270 -
1.271 - NodeIt head(EdgeIt) const {}
1.272 - NodeIt tail(EdgeIt) const {}
1.273 -
1.274 -// NodeIt aNode(InEdgeIt) const {}
1.275 -// NodeIt aNode(OutEdgeIt) const {}
1.276 -// NodeIt aNode(SymEdgeIt) const {}
1.277 -
1.278 -// NodeIt bNode(InEdgeIt) const {}
1.279 -// NodeIt bNode(OutEdgeIt) const {}
1.280 -// NodeIt bNode(SymEdgeIt) const {}
1.281 -
1.282 - bool valid(const NodeIt) const {};
1.283 - bool valid(const EdgeIt) const {};
1.284 -
1.285 - int id(const NodeIt) const {};
1.286 - int id(const EdgeIt) const {};
1.287 -
1.288 - //void setInvalid(NodeIt &) const {};
1.289 - //void setInvalid(EdgeIt &) const {};
1.290 -
1.291 - NodeIt addNode() {}
1.292 - EdgeIt addEdge(NodeIt tail, NodeIt head) {}
1.293 -
1.294 - void erase(NodeIt n) {}
1.295 - void erase(EdgeIt e) {}
1.296 -
1.297 - void clear() {}
1.298 -
1.299 - int nodeNum() {}
1.300 - int edgeNum() {}
1.301 -
1.302 - template<class T> class NodeMap
1.303 - {
1.304 - public:
1.305 - typedef T ValueType;
1.306 - typedef NodeIt KeyType;
1.307 -
1.308 - NodeMap(const Graph &G) {}
1.309 - NodeMap(const Graph &G, T t) {}
1.310 -
1.311 - void set(NodeIt i, T t) {}
1.312 - T get(NodeIt i) const {} //FIXME: Is it necessary
1.313 - T &operator[](NodeIt i) {}
1.314 - const T &operator[](NodeIt i) const {}
1.315 -
1.316 - update() {}
1.317 - update(T a) {} //FIXME: Is it necessary
1.318 - };
1.319 -
1.320 - template<class T> class EdgeMap
1.321 - {
1.322 - public:
1.323 - typedef T ValueType;
1.324 - typedef EdgeIt KeyType;
1.325 -
1.326 - EdgeMap(const Graph &G) {}
1.327 - EdgeMap(const Graph &G, T t) {}
1.328 -
1.329 - void set(EdgeIt i, T t) {}
1.330 - T get(EdgeIt i) const {}
1.331 - T &operator[](EdgeIt i) {}
1.332 -
1.333 - update() {}
1.334 - update(T a) {} //FIXME: Is it necessary
1.335 - };
1.336 -};
1.337
1.338
1.339 // class EmptyBipGraph : public EmptyGraph
1.340 // {
1.341 -// class ANodeIt {};
1.342 -// class BNodeIt {};
1.343 +// class ANode {};
1.344 +// class BNode {};
1.345
1.346 -// ANodeIt &next(ANodeIt &) {}
1.347 -// BNodeIt &next(BNodeIt &) {}
1.348 +// ANode &next(ANode &) {}
1.349 +// BNode &next(BNode &) {}
1.350
1.351 -// ANodeIt &getFirst(ANodeIt &) const {}
1.352 -// BNodeIt &getFirst(BNodeIt &) const {}
1.353 +// ANode &getFirst(ANode &) const {}
1.354 +// BNode &getFirst(BNode &) const {}
1.355
1.356 // enum NodeClass { A = 0, B = 1 };
1.357 -// NodeClass getClass(NodeIt n) {}
1.358 +// NodeClass getClass(Node n) {}
1.359
1.360 // }