1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/include/skeletons/graph.h Mon Mar 29 08:22:39 2004 +0000
1.3 @@ -0,0 +1,393 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_EMPTYGRAPH_H
1.6 +#define HUGO_EMPTYGRAPH_H
1.7 +
1.8 +///\file
1.9 +///\brief Declaration of GraphSkeleton.
1.10 +
1.11 +#include <invalid.h>
1.12 +
1.13 +/// The namespace of HugoLib
1.14 +namespace hugo {
1.15 +
1.16 + // @defgroup empty_graph The GraphSkeleton class
1.17 + // @{
1.18 +
1.19 + /// An empty graph class.
1.20 +
1.21 + /// This class provides all the common features of a graph structure,
1.22 + /// however completely without implementations and real data structures
1.23 + /// behind the interface.
1.24 + /// All graph algorithms should compile with this class, but it will not
1.25 + /// run properly, of course.
1.26 + ///
1.27 + /// It can be used for checking the interface compatibility,
1.28 + /// or it can serve as a skeleton of a new graph structure.
1.29 + ///
1.30 + /// Also, you will find here the full documentation of a certain graph
1.31 + /// feature, the documentation of a real graph imlementation
1.32 + /// like @ref ListGraph or
1.33 + /// @ref SmartGraph will just refer to this structure.
1.34 + class GraphSkeleton
1.35 + {
1.36 + public:
1.37 +
1.38 + /// The base type of the node iterators.
1.39 +
1.40 + /// This is the base type of each node iterators,
1.41 + /// thus each kind of node iterator will convert to this.
1.42 + class Node {
1.43 + public:
1.44 + /// @warning The default constructor sets the iterator
1.45 + /// to an undefined value.
1.46 + Node() {} //FIXME
1.47 + /// Invalid constructor \& conversion.
1.48 +
1.49 + /// This constructor initializes the iterator to be invalid.
1.50 + /// \sa Invalid for more details.
1.51 +
1.52 + Node(Invalid) {}
1.53 + //Node(const Node &) {}
1.54 +
1.55 + /// Two iterators are equal if and only if they point to the
1.56 + /// same object or both are invalid.
1.57 + bool operator==(Node n) const { return true; }
1.58 +
1.59 + /// \sa \ref operator==(Node n)
1.60 + ///
1.61 + bool operator!=(Node n) const { return true; }
1.62 +
1.63 + bool operator<(Node n) const { return true; }
1.64 + };
1.65 +
1.66 + /// This iterator goes through each node.
1.67 +
1.68 + /// This iterator goes through each node.
1.69 + /// Its usage is quite simple, for example you can count the number
1.70 + /// of nodes in graph \c G of type \c Graph like this:
1.71 + /// \code
1.72 + ///int count=0;
1.73 + ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
1.74 + /// \endcode
1.75 + class NodeIt : public Node {
1.76 + public:
1.77 + /// @warning The default constructor sets the iterator
1.78 + /// to an undefined value.
1.79 + NodeIt() {} //FIXME
1.80 + /// Invalid constructor \& conversion.
1.81 +
1.82 + /// Initialize the iterator to be invalid
1.83 + /// \sa Invalid for more details.
1.84 + NodeIt(Invalid) {}
1.85 + /// Sets the iterator to the first node of \c G.
1.86 + NodeIt(const GraphSkeleton &G) {}
1.87 + /// @warning The default constructor sets the iterator
1.88 + /// to an undefined value.
1.89 + NodeIt(const NodeIt &) {}
1.90 + };
1.91 +
1.92 +
1.93 + /// The base type of the edge iterators.
1.94 + class Edge {
1.95 + public:
1.96 + /// @warning The default constructor sets the iterator
1.97 + /// to an undefined value.
1.98 + Edge() {} //FIXME
1.99 + /// Initialize the iterator to be invalid
1.100 + Edge(Invalid) {}
1.101 + /// Two iterators are equal if and only if they point to the
1.102 + /// same object or both are invalid.
1.103 + bool operator==(Edge n) const { return true; }
1.104 + bool operator!=(Edge n) const { return true; }
1.105 + bool operator<(Edge n) const { return true; }
1.106 + };
1.107 +
1.108 + /// This iterator goes trough the outgoing edges of a node.
1.109 +
1.110 + /// This iterator goes trough the \e outgoing edges of a certain node
1.111 + /// of a graph.
1.112 + /// Its usage is quite simple, for example you can count the number
1.113 + /// of outgoing edges of a node \c n
1.114 + /// in graph \c G of type \c Graph as follows.
1.115 + /// \code
1.116 + ///int count=0;
1.117 + ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.118 + /// \endcode
1.119 +
1.120 + class OutEdgeIt : public Edge {
1.121 + public:
1.122 + /// @warning The default constructor sets the iterator
1.123 + /// to an undefined value.
1.124 + OutEdgeIt() {}
1.125 + /// Initialize the iterator to be invalid
1.126 + OutEdgeIt(Invalid) {}
1.127 + /// This constructor sets the iterator to first outgoing edge.
1.128 +
1.129 + /// This constructor set the iterator to the first outgoing edge of
1.130 + /// node
1.131 + ///@param n the node
1.132 + ///@param G the graph
1.133 + OutEdgeIt(const GraphSkeleton & G, Node n) {}
1.134 + };
1.135 +
1.136 + /// This iterator goes trough the incoming edges of a node.
1.137 +
1.138 + /// This iterator goes trough the \e incoming edges of a certain node
1.139 + /// of a graph.
1.140 + /// Its usage is quite simple, for example you can count the number
1.141 + /// of outgoing edges of a node \c n
1.142 + /// in graph \c G of type \c Graph as follows.
1.143 + /// \code
1.144 + ///int count=0;
1.145 + ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.146 + /// \endcode
1.147 +
1.148 + class InEdgeIt : public Edge {
1.149 + public:
1.150 + /// @warning The default constructor sets the iterator
1.151 + /// to an undefined value.
1.152 + InEdgeIt() {}
1.153 + /// Initialize the iterator to be invalid
1.154 + InEdgeIt(Invalid) {}
1.155 + InEdgeIt(const GraphSkeleton &, Node) {}
1.156 + };
1.157 + // class SymEdgeIt : public Edge {};
1.158 +
1.159 + /// This iterator goes through each edge.
1.160 +
1.161 + /// This iterator goes through each edge of a graph.
1.162 + /// Its usage is quite simple, for example you can count the number
1.163 + /// of edges in a graph \c G of type \c Graph as follows:
1.164 + /// \code
1.165 + ///int count=0;
1.166 + ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
1.167 + /// \endcode
1.168 + class EdgeIt : public Edge {
1.169 + public:
1.170 + /// @warning The default constructor sets the iterator
1.171 + /// to an undefined value.
1.172 + EdgeIt() {}
1.173 + /// Initialize the iterator to be invalid
1.174 + EdgeIt(Invalid) {}
1.175 + EdgeIt(const GraphSkeleton &) {}
1.176 + };
1.177 +
1.178 + /// First node of the graph.
1.179 +
1.180 + /// \post \c i and the return value will be the first node.
1.181 + ///
1.182 + NodeIt &first(NodeIt &i) const { return i;}
1.183 +
1.184 + /// The first incoming edge.
1.185 + InEdgeIt &first(InEdgeIt &i, Node n) const { return i;}
1.186 + /// The first outgoing edge.
1.187 + OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;}
1.188 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.189 + /// The first edge of the Graph.
1.190 + EdgeIt &first(EdgeIt &i) const { return i;}
1.191 +
1.192 +// Node getNext(Node) const {}
1.193 +// InEdgeIt getNext(InEdgeIt) const {}
1.194 +// OutEdgeIt getNext(OutEdgeIt) const {}
1.195 +// //SymEdgeIt getNext(SymEdgeIt) const {}
1.196 +// EdgeIt getNext(EdgeIt) const {}
1.197 +
1.198 + /// Go to the next node.
1.199 + NodeIt &next(NodeIt &i) const { return i;}
1.200 + /// Go to the next incoming edge.
1.201 + InEdgeIt &next(InEdgeIt &i) const { return i;}
1.202 + /// Go to the next outgoing edge.
1.203 + OutEdgeIt &next(OutEdgeIt &i) const { return i;}
1.204 + //SymEdgeIt &next(SymEdgeIt &) const {}
1.205 + /// Go to the next edge.
1.206 + EdgeIt &next(EdgeIt &i) const { return i;}
1.207 +
1.208 + ///Gives back the head node of an edge.
1.209 + Node head(Edge) const { return INVALID; }
1.210 + ///Gives back the tail node of an edge.
1.211 + Node tail(Edge) const { return INVALID; }
1.212 +
1.213 + // Node aNode(InEdgeIt) const {}
1.214 + // Node aNode(OutEdgeIt) const {}
1.215 + // Node aNode(SymEdgeIt) const {}
1.216 +
1.217 + // Node bNode(InEdgeIt) const {}
1.218 + // Node bNode(OutEdgeIt) const {}
1.219 + // Node bNode(SymEdgeIt) const {}
1.220 +
1.221 + /// Checks if a node iterator is valid
1.222 +
1.223 + ///\todo Maybe, it would be better if iterator converted to
1.224 + ///bool directly, as Jacint prefers.
1.225 + bool valid(const Node) const { return true;}
1.226 + /// Checks if an edge iterator is valid
1.227 +
1.228 + ///\todo Maybe, it would be better if iterator converted to
1.229 + ///bool directly, as Jacint prefers.
1.230 + bool valid(const Edge) const { return true;}
1.231 +
1.232 + ///Gives back the \e id of a node.
1.233 +
1.234 + ///\warning Not all graph structures provide this feature.
1.235 + ///
1.236 + int id(const Node) const { return 0;}
1.237 + ///Gives back the \e id of an edge.
1.238 +
1.239 + ///\warning Not all graph structures provide this feature.
1.240 + ///
1.241 + int id(const Edge) const { return 0;}
1.242 +
1.243 + //void setInvalid(Node &) const {};
1.244 + //void setInvalid(Edge &) const {};
1.245 +
1.246 + ///Add a new node to the graph.
1.247 +
1.248 + /// \return the new node.
1.249 + ///
1.250 + Node addNode() { return INVALID;}
1.251 + ///Add a new edge to the graph.
1.252 +
1.253 + ///Add a new edge to the graph with tail node \c tail
1.254 + ///and head node \c head.
1.255 + ///\return the new edge.
1.256 + Edge addEdge(Node tail, Node head) { return INVALID;}
1.257 +
1.258 + /// Resets the graph.
1.259 +
1.260 + /// This function deletes all edges and nodes of the graph.
1.261 + /// It also frees the memory allocated to store them.
1.262 + void clear() {}
1.263 +
1.264 + int nodeNum() const { return 0;}
1.265 + int edgeNum() const { return 0;}
1.266 +
1.267 + /// Defalult constructor.
1.268 + GraphSkeleton() {}
1.269 + ///Copy consructor.
1.270 + GraphSkeleton(const GraphSkeleton &G) {}
1.271 +
1.272 +
1.273 +
1.274 + ///Read/write/reference map of the nodes to type \c T.
1.275 +
1.276 + ///Read/write/reference map of the nodes to type \c T.
1.277 + /// \sa MemoryMapSkeleton
1.278 + /// \todo We may need copy constructor
1.279 + /// \todo We may need conversion from other nodetype
1.280 + /// \todo We may need operator=
1.281 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.282 + /// needs extra attention!
1.283 +
1.284 + template<class T> class NodeMap
1.285 + {
1.286 + public:
1.287 + typedef T ValueType;
1.288 + typedef Node KeyType;
1.289 +
1.290 + NodeMap(const GraphSkeleton &G) {}
1.291 + NodeMap(const GraphSkeleton &G, T t) {}
1.292 +
1.293 + template<typename TT> NodeMap(const NodeMap<TT> &m) {}
1.294 +
1.295 + /// Sets the value of a node.
1.296 +
1.297 + /// Sets the value associated with node \c i to the value \c t.
1.298 + ///
1.299 + void set(Node i, T t) {}
1.300 + /// Gets the value of a node.
1.301 + T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary
1.302 + T &operator[](Node i) {return *(T*)0;}
1.303 + const T &operator[](Node i) const {return *(T*)0;}
1.304 +
1.305 + /// Updates the map if the graph has been changed
1.306 +
1.307 + /// \todo Do we need this?
1.308 + ///
1.309 + void update() {}
1.310 + void update(T a) {} //FIXME: Is it necessary
1.311 + };
1.312 +
1.313 + ///Read/write/reference map of the edges to type \c T.
1.314 +
1.315 + ///Read/write/reference map of the edges to type \c T.
1.316 + ///It behaves exactly in the same way as \ref NodeMap.
1.317 + /// \sa NodeMap
1.318 + /// \sa MemoryMapSkeleton
1.319 + /// \todo We may need copy constructor
1.320 + /// \todo We may need conversion from other edgetype
1.321 + /// \todo We may need operator=
1.322 + template<class T> class EdgeMap
1.323 + {
1.324 + public:
1.325 + typedef T ValueType;
1.326 + typedef Edge KeyType;
1.327 +
1.328 + EdgeMap(const GraphSkeleton &G) {}
1.329 + EdgeMap(const GraphSkeleton &G, T t) {}
1.330 +
1.331 + void set(Edge i, T t) {}
1.332 + T get(Edge i) const {return *(T*)0;}
1.333 + T &operator[](Edge i) {return *(T*)0;}
1.334 +
1.335 + void update() {}
1.336 + void update(T a) {} //FIXME: Is it necessary
1.337 + };
1.338 + };
1.339 +
1.340 + /// An empty eraseable graph class.
1.341 +
1.342 + /// This class provides all the common features of an \e eraseable graph
1.343 + /// structure,
1.344 + /// however completely without implementations and real data structures
1.345 + /// behind the interface.
1.346 + /// All graph algorithms should compile with this class, but it will not
1.347 + /// run properly, of course.
1.348 + ///
1.349 + /// \todo This blabla could be replaced by a sepatate description about
1.350 + /// Skeletons.
1.351 + ///
1.352 + /// It can be used for checking the interface compatibility,
1.353 + /// or it can serve as a skeleton of a new graph structure.
1.354 + ///
1.355 + /// Also, you will find here the full documentation of a certain graph
1.356 + /// feature, the documentation of a real graph imlementation
1.357 + /// like @ref ListGraph or
1.358 + /// @ref SmartGraph will just refer to this structure.
1.359 + class EraseableGraphSkeleton : public GraphSkeleton
1.360 + {
1.361 + public:
1.362 + /// Deletes a node.
1.363 + void erase(Node n) {}
1.364 + /// Deletes an edge.
1.365 + void erase(Edge e) {}
1.366 +
1.367 + /// Defalult constructor.
1.368 + GraphSkeleton() {}
1.369 + ///Copy consructor.
1.370 + GraphSkeleton(const GraphSkeleton &G) {}
1.371 + };
1.372 +
1.373 +
1.374 + // @}
1.375 +
1.376 +} //namespace hugo
1.377 +
1.378 +
1.379 +
1.380 +// class EmptyBipGraph : public Graph Skeleton
1.381 +// {
1.382 +// class ANode {};
1.383 +// class BNode {};
1.384 +
1.385 +// ANode &next(ANode &) {}
1.386 +// BNode &next(BNode &) {}
1.387 +
1.388 +// ANode &getFirst(ANode &) const {}
1.389 +// BNode &getFirst(BNode &) const {}
1.390 +
1.391 +// enum NodeClass { A = 0, B = 1 };
1.392 +// NodeClass getClass(Node n) {}
1.393 +
1.394 +// }
1.395 +
1.396 +#endif // HUGO_EMPTYGRAPH_H
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/include/skeletons/maps.h Mon Mar 29 08:22:39 2004 +0000
2.3 @@ -0,0 +1,84 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_MAPSKELETON_H
2.6 +#define HUGO_MAPSKELETON_H
2.7 +
2.8 +///\file
2.9 +///\brief Map concepts checking classes for testing and documenting.
2.10 +
2.11 +namespace hugo {
2.12 +
2.13 + ///Readable map skeleton
2.14 + template<typename K, typename T>
2.15 + class ReadMapSkeleton
2.16 + {
2.17 + public:
2.18 + /// Map value type.
2.19 + typedef T ValueType;
2.20 + /// Map key type.
2.21 + typedef K KeyType;
2.22 +
2.23 + ///Default constructor.
2.24 + ReadMapSkeleton() {}
2.25 +
2.26 + ///Reads an element of the map.
2.27 + ValueType operator[](const KeyType &i) const {return ValueType();}
2.28 + };
2.29 +
2.30 +
2.31 + ///Writeable map skeleton
2.32 + template<typename K, typename T>
2.33 + class WriteMapSkeleton
2.34 + {
2.35 + public:
2.36 + /// Map value type.
2.37 + typedef T ValueType;
2.38 + /// Map key type.
2.39 + typedef K KeyType;
2.40 +
2.41 + ///Default constructor.
2.42 + WriteMapSkeleton() {}
2.43 + ///'Fill with' constructor.
2.44 + WriteMapSkeleton(const ValueType &t) {}
2.45 +
2.46 + ///Write an element of a map.
2.47 + void set(const KeyType &i,const ValueType &t) {}
2.48 + };
2.49 +
2.50 + ///Read/Write map skeleton.
2.51 + template<typename K, typename T>
2.52 + class ReadWriteMapSkeleton : public ReadMapSkeleton<K,T>,
2.53 + public WriteMapSkeleton<K,T>
2.54 + {
2.55 + public:
2.56 + ///Default constructor.
2.57 + ReadWriteMapSkeleton() : ReadMapSkeleton(), WriteMapSkeleton() {}
2.58 + ///'Fill with' constructor.
2.59 + ReadWriteMap(const ValueType &t) :ReadMapSkeleton(), WriteMapSkeleton(t) {}
2.60 + };
2.61 +
2.62 +
2.63 + ///Dereferable map skeleton
2.64 + template<typename K, typename T>
2.65 + class MemoryMapSkeleton : public ReadWriteMapSkeleton<K,T>
2.66 + {
2.67 + public:
2.68 + /// Map value type.
2.69 + typedef T ValueType;
2.70 + /// Map key type.
2.71 + typedef K KeyType;
2.72 +
2.73 + ///Default constructor.
2.74 + ReferenceMapSkeleton() : ReadWriteMapSkeleton() {}
2.75 + ///'Fill with' constructor.
2.76 + ReferenceMapSkeleton(const ValueType &t) : ReadWriteMapSkeleton(t) {}
2.77 +
2.78 + ///Give a reference to the value belonging to a key.
2.79 + ValueType &operator[](const KeyType &i) {return *(ValueType*)0;}
2.80 + ///Give a const reference to the value belonging to a key.
2.81 + const ValueType &operator[](const KeyType &i) const {return *(T*)0;}
2.82 + };
2.83 +
2.84 +
2.85 +
2.86 +}
2.87 +#endif // HUGO_MAPSKELETON_H
3.1 --- a/src/work/alpar/emptygraph.h Mon Mar 29 08:16:18 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,393 +0,0 @@
3.4 -// -*- c++ -*-
3.5 -#ifndef HUGO_EMPTYGRAPH_H
3.6 -#define HUGO_EMPTYGRAPH_H
3.7 -
3.8 -///\file
3.9 -///\brief Declaration of GraphSkeleton.
3.10 -
3.11 -#include <invalid.h>
3.12 -
3.13 -/// The namespace of HugoLib
3.14 -namespace hugo {
3.15 -
3.16 - // @defgroup empty_graph The GraphSkeleton class
3.17 - // @{
3.18 -
3.19 - /// An empty graph class.
3.20 -
3.21 - /// This class provides all the common features of a graph structure,
3.22 - /// however completely without implementations and real data structures
3.23 - /// behind the interface.
3.24 - /// All graph algorithms should compile with this class, but it will not
3.25 - /// run properly, of course.
3.26 - ///
3.27 - /// It can be used for checking the interface compatibility,
3.28 - /// or it can serve as a skeleton of a new graph structure.
3.29 - ///
3.30 - /// Also, you will find here the full documentation of a certain graph
3.31 - /// feature, the documentation of a real graph imlementation
3.32 - /// like @ref ListGraph or
3.33 - /// @ref SmartGraph will just refer to this structure.
3.34 - class GraphSkeleton
3.35 - {
3.36 - public:
3.37 -
3.38 - /// The base type of the node iterators.
3.39 -
3.40 - /// This is the base type of each node iterators,
3.41 - /// thus each kind of node iterator will convert to this.
3.42 - class Node {
3.43 - public:
3.44 - /// @warning The default constructor sets the iterator
3.45 - /// to an undefined value.
3.46 - Node() {} //FIXME
3.47 - /// Invalid constructor \& conversion.
3.48 -
3.49 - /// This constructor initializes the iterator to be invalid.
3.50 - /// \sa Invalid for more details.
3.51 -
3.52 - Node(Invalid) {}
3.53 - //Node(const Node &) {}
3.54 -
3.55 - /// Two iterators are equal if and only if they point to the
3.56 - /// same object or both are invalid.
3.57 - bool operator==(Node n) const { return true; }
3.58 -
3.59 - /// \sa \ref operator==(Node n)
3.60 - ///
3.61 - bool operator!=(Node n) const { return true; }
3.62 -
3.63 - bool operator<(Node n) const { return true; }
3.64 - };
3.65 -
3.66 - /// This iterator goes through each node.
3.67 -
3.68 - /// This iterator goes through each node.
3.69 - /// Its usage is quite simple, for example you can count the number
3.70 - /// of nodes in graph \c G of type \c Graph like this:
3.71 - /// \code
3.72 - ///int count=0;
3.73 - ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
3.74 - /// \endcode
3.75 - class NodeIt : public Node {
3.76 - public:
3.77 - /// @warning The default constructor sets the iterator
3.78 - /// to an undefined value.
3.79 - NodeIt() {} //FIXME
3.80 - /// Invalid constructor \& conversion.
3.81 -
3.82 - /// Initialize the iterator to be invalid
3.83 - /// \sa Invalid for more details.
3.84 - NodeIt(Invalid) {}
3.85 - /// Sets the iterator to the first node of \c G.
3.86 - NodeIt(const GraphSkeleton &G) {}
3.87 - /// @warning The default constructor sets the iterator
3.88 - /// to an undefined value.
3.89 - NodeIt(const NodeIt &) {}
3.90 - };
3.91 -
3.92 -
3.93 - /// The base type of the edge iterators.
3.94 - class Edge {
3.95 - public:
3.96 - /// @warning The default constructor sets the iterator
3.97 - /// to an undefined value.
3.98 - Edge() {} //FIXME
3.99 - /// Initialize the iterator to be invalid
3.100 - Edge(Invalid) {}
3.101 - /// Two iterators are equal if and only if they point to the
3.102 - /// same object or both are invalid.
3.103 - bool operator==(Edge n) const { return true; }
3.104 - bool operator!=(Edge n) const { return true; }
3.105 - bool operator<(Edge n) const { return true; }
3.106 - };
3.107 -
3.108 - /// This iterator goes trough the outgoing edges of a node.
3.109 -
3.110 - /// This iterator goes trough the \e outgoing edges of a certain node
3.111 - /// of a graph.
3.112 - /// Its usage is quite simple, for example you can count the number
3.113 - /// of outgoing edges of a node \c n
3.114 - /// in graph \c G of type \c Graph as follows.
3.115 - /// \code
3.116 - ///int count=0;
3.117 - ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
3.118 - /// \endcode
3.119 -
3.120 - class OutEdgeIt : public Edge {
3.121 - public:
3.122 - /// @warning The default constructor sets the iterator
3.123 - /// to an undefined value.
3.124 - OutEdgeIt() {}
3.125 - /// Initialize the iterator to be invalid
3.126 - OutEdgeIt(Invalid) {}
3.127 - /// This constructor sets the iterator to first outgoing edge.
3.128 -
3.129 - /// This constructor set the iterator to the first outgoing edge of
3.130 - /// node
3.131 - ///@param n the node
3.132 - ///@param G the graph
3.133 - OutEdgeIt(const GraphSkeleton & G, Node n) {}
3.134 - };
3.135 -
3.136 - /// This iterator goes trough the incoming edges of a node.
3.137 -
3.138 - /// This iterator goes trough the \e incoming edges of a certain node
3.139 - /// of a graph.
3.140 - /// Its usage is quite simple, for example you can count the number
3.141 - /// of outgoing edges of a node \c n
3.142 - /// in graph \c G of type \c Graph as follows.
3.143 - /// \code
3.144 - ///int count=0;
3.145 - ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
3.146 - /// \endcode
3.147 -
3.148 - class InEdgeIt : public Edge {
3.149 - public:
3.150 - /// @warning The default constructor sets the iterator
3.151 - /// to an undefined value.
3.152 - InEdgeIt() {}
3.153 - /// Initialize the iterator to be invalid
3.154 - InEdgeIt(Invalid) {}
3.155 - InEdgeIt(const GraphSkeleton &, Node) {}
3.156 - };
3.157 - // class SymEdgeIt : public Edge {};
3.158 -
3.159 - /// This iterator goes through each edge.
3.160 -
3.161 - /// This iterator goes through each edge of a graph.
3.162 - /// Its usage is quite simple, for example you can count the number
3.163 - /// of edges in a graph \c G of type \c Graph as follows:
3.164 - /// \code
3.165 - ///int count=0;
3.166 - ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
3.167 - /// \endcode
3.168 - class EdgeIt : public Edge {
3.169 - public:
3.170 - /// @warning The default constructor sets the iterator
3.171 - /// to an undefined value.
3.172 - EdgeIt() {}
3.173 - /// Initialize the iterator to be invalid
3.174 - EdgeIt(Invalid) {}
3.175 - EdgeIt(const GraphSkeleton &) {}
3.176 - };
3.177 -
3.178 - /// First node of the graph.
3.179 -
3.180 - /// \post \c i and the return value will be the first node.
3.181 - ///
3.182 - NodeIt &first(NodeIt &i) const { return i;}
3.183 -
3.184 - /// The first incoming edge.
3.185 - InEdgeIt &first(InEdgeIt &i, Node n) const { return i;}
3.186 - /// The first outgoing edge.
3.187 - OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;}
3.188 - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
3.189 - /// The first edge of the Graph.
3.190 - EdgeIt &first(EdgeIt &i) const { return i;}
3.191 -
3.192 -// Node getNext(Node) const {}
3.193 -// InEdgeIt getNext(InEdgeIt) const {}
3.194 -// OutEdgeIt getNext(OutEdgeIt) const {}
3.195 -// //SymEdgeIt getNext(SymEdgeIt) const {}
3.196 -// EdgeIt getNext(EdgeIt) const {}
3.197 -
3.198 - /// Go to the next node.
3.199 - NodeIt &next(NodeIt &i) const { return i;}
3.200 - /// Go to the next incoming edge.
3.201 - InEdgeIt &next(InEdgeIt &i) const { return i;}
3.202 - /// Go to the next outgoing edge.
3.203 - OutEdgeIt &next(OutEdgeIt &i) const { return i;}
3.204 - //SymEdgeIt &next(SymEdgeIt &) const {}
3.205 - /// Go to the next edge.
3.206 - EdgeIt &next(EdgeIt &i) const { return i;}
3.207 -
3.208 - ///Gives back the head node of an edge.
3.209 - Node head(Edge) const { return INVALID; }
3.210 - ///Gives back the tail node of an edge.
3.211 - Node tail(Edge) const { return INVALID; }
3.212 -
3.213 - // Node aNode(InEdgeIt) const {}
3.214 - // Node aNode(OutEdgeIt) const {}
3.215 - // Node aNode(SymEdgeIt) const {}
3.216 -
3.217 - // Node bNode(InEdgeIt) const {}
3.218 - // Node bNode(OutEdgeIt) const {}
3.219 - // Node bNode(SymEdgeIt) const {}
3.220 -
3.221 - /// Checks if a node iterator is valid
3.222 -
3.223 - ///\todo Maybe, it would be better if iterator converted to
3.224 - ///bool directly, as Jacint prefers.
3.225 - bool valid(const Node) const { return true;}
3.226 - /// Checks if an edge iterator is valid
3.227 -
3.228 - ///\todo Maybe, it would be better if iterator converted to
3.229 - ///bool directly, as Jacint prefers.
3.230 - bool valid(const Edge) const { return true;}
3.231 -
3.232 - ///Gives back the \e id of a node.
3.233 -
3.234 - ///\warning Not all graph structures provide this feature.
3.235 - ///
3.236 - int id(const Node) const { return 0;}
3.237 - ///Gives back the \e id of an edge.
3.238 -
3.239 - ///\warning Not all graph structures provide this feature.
3.240 - ///
3.241 - int id(const Edge) const { return 0;}
3.242 -
3.243 - //void setInvalid(Node &) const {};
3.244 - //void setInvalid(Edge &) const {};
3.245 -
3.246 - ///Add a new node to the graph.
3.247 -
3.248 - /// \return the new node.
3.249 - ///
3.250 - Node addNode() { return INVALID;}
3.251 - ///Add a new edge to the graph.
3.252 -
3.253 - ///Add a new edge to the graph with tail node \c tail
3.254 - ///and head node \c head.
3.255 - ///\return the new edge.
3.256 - Edge addEdge(Node tail, Node head) { return INVALID;}
3.257 -
3.258 - /// Resets the graph.
3.259 -
3.260 - /// This function deletes all edges and nodes of the graph.
3.261 - /// It also frees the memory allocated to store them.
3.262 - void clear() {}
3.263 -
3.264 - int nodeNum() const { return 0;}
3.265 - int edgeNum() const { return 0;}
3.266 -
3.267 - /// Defalult constructor.
3.268 - GraphSkeleton() {}
3.269 - ///Copy consructor.
3.270 - GraphSkeleton(const GraphSkeleton &G) {}
3.271 -
3.272 -
3.273 -
3.274 - ///Read/write/reference map of the nodes to type \c T.
3.275 -
3.276 - ///Read/write/reference map of the nodes to type \c T.
3.277 - /// \sa MemoryMapSkeleton
3.278 - /// \todo We may need copy constructor
3.279 - /// \todo We may need conversion from other nodetype
3.280 - /// \todo We may need operator=
3.281 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
3.282 - /// needs extra attention!
3.283 -
3.284 - template<class T> class NodeMap
3.285 - {
3.286 - public:
3.287 - typedef T ValueType;
3.288 - typedef Node KeyType;
3.289 -
3.290 - NodeMap(const GraphSkeleton &G) {}
3.291 - NodeMap(const GraphSkeleton &G, T t) {}
3.292 -
3.293 - template<typename TT> NodeMap(const NodeMap<TT> &m) {}
3.294 -
3.295 - /// Sets the value of a node.
3.296 -
3.297 - /// Sets the value associated with node \c i to the value \c t.
3.298 - ///
3.299 - void set(Node i, T t) {}
3.300 - /// Gets the value of a node.
3.301 - T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary
3.302 - T &operator[](Node i) {return *(T*)0;}
3.303 - const T &operator[](Node i) const {return *(T*)0;}
3.304 -
3.305 - /// Updates the map if the graph has been changed
3.306 -
3.307 - /// \todo Do we need this?
3.308 - ///
3.309 - void update() {}
3.310 - void update(T a) {} //FIXME: Is it necessary
3.311 - };
3.312 -
3.313 - ///Read/write/reference map of the edges to type \c T.
3.314 -
3.315 - ///Read/write/reference map of the edges to type \c T.
3.316 - ///It behaves exactly in the same way as \ref NodeMap.
3.317 - /// \sa NodeMap
3.318 - /// \sa MemoryMapSkeleton
3.319 - /// \todo We may need copy constructor
3.320 - /// \todo We may need conversion from other edgetype
3.321 - /// \todo We may need operator=
3.322 - template<class T> class EdgeMap
3.323 - {
3.324 - public:
3.325 - typedef T ValueType;
3.326 - typedef Edge KeyType;
3.327 -
3.328 - EdgeMap(const GraphSkeleton &G) {}
3.329 - EdgeMap(const GraphSkeleton &G, T t) {}
3.330 -
3.331 - void set(Edge i, T t) {}
3.332 - T get(Edge i) const {return *(T*)0;}
3.333 - T &operator[](Edge i) {return *(T*)0;}
3.334 -
3.335 - void update() {}
3.336 - void update(T a) {} //FIXME: Is it necessary
3.337 - };
3.338 - };
3.339 -
3.340 - /// An empty eraseable graph class.
3.341 -
3.342 - /// This class provides all the common features of an \e eraseable graph
3.343 - /// structure,
3.344 - /// however completely without implementations and real data structures
3.345 - /// behind the interface.
3.346 - /// All graph algorithms should compile with this class, but it will not
3.347 - /// run properly, of course.
3.348 - ///
3.349 - /// \todo This blabla could be replaced by a sepatate description about
3.350 - /// Skeletons.
3.351 - ///
3.352 - /// It can be used for checking the interface compatibility,
3.353 - /// or it can serve as a skeleton of a new graph structure.
3.354 - ///
3.355 - /// Also, you will find here the full documentation of a certain graph
3.356 - /// feature, the documentation of a real graph imlementation
3.357 - /// like @ref ListGraph or
3.358 - /// @ref SmartGraph will just refer to this structure.
3.359 - class EraseableGraphSkeleton : public GraphSkeleton
3.360 - {
3.361 - public:
3.362 - /// Deletes a node.
3.363 - void erase(Node n) {}
3.364 - /// Deletes an edge.
3.365 - void erase(Edge e) {}
3.366 -
3.367 - /// Defalult constructor.
3.368 - GraphSkeleton() {}
3.369 - ///Copy consructor.
3.370 - GraphSkeleton(const GraphSkeleton &G) {}
3.371 - };
3.372 -
3.373 -
3.374 - // @}
3.375 -
3.376 -} //namespace hugo
3.377 -
3.378 -
3.379 -
3.380 -// class EmptyBipGraph : public Graph Skeleton
3.381 -// {
3.382 -// class ANode {};
3.383 -// class BNode {};
3.384 -
3.385 -// ANode &next(ANode &) {}
3.386 -// BNode &next(BNode &) {}
3.387 -
3.388 -// ANode &getFirst(ANode &) const {}
3.389 -// BNode &getFirst(BNode &) const {}
3.390 -
3.391 -// enum NodeClass { A = 0, B = 1 };
3.392 -// NodeClass getClass(Node n) {}
3.393 -
3.394 -// }
3.395 -
3.396 -#endif // HUGO_EMPTYGRAPH_H
4.1 --- a/src/work/alpar/mapskeleton.h Mon Mar 29 08:16:18 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,84 +0,0 @@
4.4 -// -*- c++ -*-
4.5 -#ifndef HUGO_MAPSKELETON_H
4.6 -#define HUGO_MAPSKELETON_H
4.7 -
4.8 -///\file
4.9 -///\brief Map concepts checking classes for testing and documenting.
4.10 -
4.11 -namespace hugo {
4.12 -
4.13 - ///Readable map skeleton
4.14 - template<typename K, typename T>
4.15 - class ReadMapSkeleton
4.16 - {
4.17 - public:
4.18 - /// Map value type.
4.19 - typedef T ValueType;
4.20 - /// Map key type.
4.21 - typedef K KeyType;
4.22 -
4.23 - ///Default constructor.
4.24 - ReadMapSkeleton() {}
4.25 -
4.26 - ///Reads an element of the map.
4.27 - ValueType operator[](const KeyType &i) const {return ValueType();}
4.28 - };
4.29 -
4.30 -
4.31 - ///Writeable map skeleton
4.32 - template<typename K, typename T>
4.33 - class WriteMapSkeleton
4.34 - {
4.35 - public:
4.36 - /// Map value type.
4.37 - typedef T ValueType;
4.38 - /// Map key type.
4.39 - typedef K KeyType;
4.40 -
4.41 - ///Default constructor.
4.42 - WriteMapSkeleton() {}
4.43 - ///'Fill with' constructor.
4.44 - WriteMapSkeleton(const ValueType &t) {}
4.45 -
4.46 - ///Write an element of a map.
4.47 - void set(const KeyType &i,const ValueType &t) {}
4.48 - };
4.49 -
4.50 - ///Read/Write map skeleton.
4.51 - template<typename K, typename T>
4.52 - class ReadWriteMapSkeleton : public ReadMapSkeleton<K,T>,
4.53 - public WriteMapSkeleton<K,T>
4.54 - {
4.55 - public:
4.56 - ///Default constructor.
4.57 - ReadWriteMapSkeleton() : ReadMapSkeleton(), WriteMapSkeleton() {}
4.58 - ///'Fill with' constructor.
4.59 - ReadWriteMap(const ValueType &t) :ReadMapSkeleton(), WriteMapSkeleton(t) {}
4.60 - };
4.61 -
4.62 -
4.63 - ///Dereferable map skeleton
4.64 - template<typename K, typename T>
4.65 - class MemoryMapSkeleton : public ReadWriteMapSkeleton<K,T>
4.66 - {
4.67 - public:
4.68 - /// Map value type.
4.69 - typedef T ValueType;
4.70 - /// Map key type.
4.71 - typedef K KeyType;
4.72 -
4.73 - ///Default constructor.
4.74 - ReferenceMapSkeleton() : ReadWriteMapSkeleton() {}
4.75 - ///'Fill with' constructor.
4.76 - ReferenceMapSkeleton(const ValueType &t) : ReadWriteMapSkeleton(t) {}
4.77 -
4.78 - ///Give a reference to the value belonging to a key.
4.79 - ValueType &operator[](const KeyType &i) {return *(ValueType*)0;}
4.80 - ///Give a const reference to the value belonging to a key.
4.81 - const ValueType &operator[](const KeyType &i) const {return *(T*)0;}
4.82 - };
4.83 -
4.84 -
4.85 -
4.86 -}
4.87 -#endif // HUGO_MAPSKELETON_H