Skeletons have been simplified.
"Optional features" have been deleted.
Map skeletons have been renamed.
1.1 --- a/src/hugo/skeletons/graph.h Thu Jul 22 19:49:28 2004 +0000
1.2 +++ b/src/hugo/skeletons/graph.h Thu Jul 22 19:59:18 2004 +0000
1.3 @@ -6,376 +6,365 @@
1.4 ///\brief Declaration of GraphSkeleton.
1.5
1.6 #include <hugo/invalid.h>
1.7 +#include <hugo/skeletons/maps.h>
1.8
1.9 /// The namespace of HugoLib
1.10 namespace hugo {
1.11 + namespace skeleton {
1.12 +
1.13 + // @defgroup empty_graph The GraphSkeleton class
1.14 + // @{
1.15
1.16 - // @defgroup empty_graph The GraphSkeleton class
1.17 - // @{
1.18 + /// An empty static graph class.
1.19 +
1.20 + /// This class provides all the common features of a graph structure,
1.21 + /// however completely without implementations and 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 + /// Also, you will find here the full documentation of a certain graph
1.30 + /// feature, the documentation of a real graph imlementation
1.31 + /// like @ref ListGraph or
1.32 + /// @ref SmartGraph will just refer to this structure.
1.33 + class StaticGraphSkeleton
1.34 + {
1.35 + public:
1.36 + /// Defalult constructor.
1.37 + StaticGraphSkeleton() {}
1.38 + ///Copy consructor.
1.39
1.40 - /// An empty graph class.
1.41 + ///\todo It is not clear, what we expect from a copy constructor.
1.42 + ///E.g. How to assign the nodes/edges to each other? What about maps?
1.43 + StaticGraphSkeleton(const StaticGraphSkeleton &G) {}
1.44 +
1.45 + /// The base type of the node iterators.
1.46 +
1.47 + /// This is the base type of each node iterators,
1.48 + /// thus each kind of node iterator will convert to this.
1.49 + class Node {
1.50 + public:
1.51 + /// @warning The default constructor sets the iterator
1.52 + /// to an undefined value.
1.53 + Node() {} //FIXME
1.54 + /// Invalid constructor \& conversion.
1.55 +
1.56 + /// This constructor initializes the iterator to be invalid.
1.57 + /// \sa Invalid for more details.
1.58 +
1.59 + Node(Invalid) {}
1.60 + //Node(const Node &) {}
1.61 +
1.62 + /// Two iterators are equal if and only if they point to the
1.63 + /// same object or both are invalid.
1.64 + bool operator==(Node) const { return true; }
1.65 +
1.66 + /// \sa \ref operator==(Node n)
1.67 + ///
1.68 + bool operator!=(Node) const { return true; }
1.69 +
1.70 + bool operator<(Node) const { return true; }
1.71 + };
1.72 +
1.73 + /// This iterator goes through each node.
1.74 +
1.75 + /// This iterator goes through each node.
1.76 + /// Its usage is quite simple, for example you can count the number
1.77 + /// of nodes in graph \c G of type \c Graph like this:
1.78 + /// \code
1.79 + ///int count=0;
1.80 + ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
1.81 + /// \endcode
1.82 + class NodeIt : public Node {
1.83 + public:
1.84 + /// @warning The default constructor sets the iterator
1.85 + /// to an undefined value.
1.86 + NodeIt() {} //FIXME
1.87 + /// Invalid constructor \& conversion.
1.88 +
1.89 + /// Initialize the iterator to be invalid
1.90 + /// \sa Invalid for more details.
1.91 + NodeIt(Invalid) {}
1.92 + /// Sets the iterator to the first node of \c G.
1.93 + NodeIt(const StaticGraphSkeleton &) {}
1.94 + /// @warning The default constructor sets the iterator
1.95 + /// to an undefined value.
1.96 + NodeIt(const NodeIt &n) : Node(n) {}
1.97 + };
1.98 +
1.99 +
1.100 + /// The base type of the edge iterators.
1.101 + class Edge {
1.102 + public:
1.103 + /// @warning The default constructor sets the iterator
1.104 + /// to an undefined value.
1.105 + Edge() {} //FIXME
1.106 + /// Initialize the iterator to be invalid
1.107 + Edge(Invalid) {}
1.108 + /// Two iterators are equal if and only if they point to the
1.109 + /// same object or both are invalid.
1.110 + bool operator==(Edge) const { return true; }
1.111 + bool operator!=(Edge) const { return true; }
1.112 + bool operator<(Edge) const { return true; }
1.113 + };
1.114 +
1.115 + /// This iterator goes trough the outgoing edges of a node.
1.116 +
1.117 + /// This iterator goes trough the \e outgoing edges of a certain node
1.118 + /// of a graph.
1.119 + /// Its usage is quite simple, for example you can count the number
1.120 + /// of outgoing edges of a node \c n
1.121 + /// in graph \c G of type \c Graph as follows.
1.122 + /// \code
1.123 + ///int count=0;
1.124 + ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.125 + /// \endcode
1.126 +
1.127 + class OutEdgeIt : public Edge {
1.128 + public:
1.129 + /// @warning The default constructor sets the iterator
1.130 + /// to an undefined value.
1.131 + OutEdgeIt() {}
1.132 + /// Initialize the iterator to be invalid
1.133 + OutEdgeIt(Invalid) {}
1.134 + /// This constructor sets the iterator to first outgoing edge.
1.135 +
1.136 + /// This constructor set the iterator to the first outgoing edge of
1.137 + /// node
1.138 + ///@param n the node
1.139 + ///@param G the graph
1.140 + OutEdgeIt(const StaticGraphSkeleton &, Node) {}
1.141 + };
1.142 +
1.143 + /// This iterator goes trough the incoming edges of a node.
1.144 +
1.145 + /// This iterator goes trough the \e incoming edges of a certain node
1.146 + /// of a graph.
1.147 + /// Its usage is quite simple, for example you can count the number
1.148 + /// of outgoing edges of a node \c n
1.149 + /// in graph \c G of type \c Graph as follows.
1.150 + /// \code
1.151 + ///int count=0;
1.152 + ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.153 + /// \endcode
1.154 +
1.155 + class InEdgeIt : public Edge {
1.156 + public:
1.157 + /// @warning The default constructor sets the iterator
1.158 + /// to an undefined value.
1.159 + InEdgeIt() {}
1.160 + /// Initialize the iterator to be invalid
1.161 + InEdgeIt(Invalid) {}
1.162 + InEdgeIt(const StaticGraphSkeleton &, Node) {}
1.163 + };
1.164 + // class SymEdgeIt : public Edge {};
1.165 +
1.166 + /// This iterator goes through each edge.
1.167 +
1.168 + /// This iterator goes through each edge of a graph.
1.169 + /// Its usage is quite simple, for example you can count the number
1.170 + /// of edges in a graph \c G of type \c Graph as follows:
1.171 + /// \code
1.172 + ///int count=0;
1.173 + ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
1.174 + /// \endcode
1.175 + class EdgeIt : public Edge {
1.176 + public:
1.177 + /// @warning The default constructor sets the iterator
1.178 + /// to an undefined value.
1.179 + EdgeIt() {}
1.180 + /// Initialize the iterator to be invalid
1.181 + EdgeIt(Invalid) {}
1.182 + EdgeIt(const StaticGraphSkeleton &) {}
1.183 + };
1.184 +
1.185 + /// First node of the graph.
1.186 +
1.187 + /// \retval i the first node.
1.188 + /// \return the first node.
1.189 + ///
1.190 + NodeIt &first(NodeIt &i) const { return i;}
1.191 +
1.192 + /// The first incoming edge.
1.193 + InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
1.194 + /// The first outgoing edge.
1.195 + OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
1.196 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.197 + /// The first edge of the Graph.
1.198 + EdgeIt &first(EdgeIt &i) const { return i;}
1.199 +
1.200 + // Node getNext(Node) const {}
1.201 + // InEdgeIt getNext(InEdgeIt) const {}
1.202 + // OutEdgeIt getNext(OutEdgeIt) const {}
1.203 + // //SymEdgeIt getNext(SymEdgeIt) const {}
1.204 + // EdgeIt getNext(EdgeIt) const {}
1.205 +
1.206 + /// Go to the next node.
1.207 + NodeIt &next(NodeIt &i) const { return i;}
1.208 + /// Go to the next incoming edge.
1.209 + InEdgeIt &next(InEdgeIt &i) const { return i;}
1.210 + /// Go to the next outgoing edge.
1.211 + OutEdgeIt &next(OutEdgeIt &i) const { return i;}
1.212 + //SymEdgeIt &next(SymEdgeIt &) const {}
1.213 + /// Go to the next edge.
1.214 + EdgeIt &next(EdgeIt &i) const { return i;}
1.215 +
1.216 + ///Gives back the head node of an edge.
1.217 + Node head(Edge) const { return INVALID; }
1.218 + ///Gives back the tail node of an edge.
1.219 + Node tail(Edge) const { return INVALID; }
1.220
1.221 - /// This class provides all the common features of a graph structure,
1.222 - /// however completely without implementations and real data structures
1.223 - /// behind the interface.
1.224 - /// All graph algorithms should compile with this class, but it will not
1.225 - /// run properly, of course.
1.226 - ///
1.227 - /// It can be used for checking the interface compatibility,
1.228 - /// or it can serve as a skeleton of a new graph structure.
1.229 - ///
1.230 - /// Also, you will find here the full documentation of a certain graph
1.231 - /// feature, the documentation of a real graph imlementation
1.232 - /// like @ref ListGraph or
1.233 - /// @ref SmartGraph will just refer to this structure.
1.234 - class GraphSkeleton
1.235 - {
1.236 - public:
1.237 - /// Defalult constructor.
1.238 - GraphSkeleton() {}
1.239 - ///Copy consructor.
1.240 + // Node aNode(InEdgeIt) const {}
1.241 + // Node aNode(OutEdgeIt) const {}
1.242 + // Node aNode(SymEdgeIt) const {}
1.243
1.244 - ///\todo It is not clear, what we expect from a copy constructor.
1.245 - ///E.g. How to assign the nodes/edges to each other? What about maps?
1.246 - GraphSkeleton(const GraphSkeleton &G) {}
1.247 + // Node bNode(InEdgeIt) const {}
1.248 + // Node bNode(OutEdgeIt) const {}
1.249 + // Node bNode(SymEdgeIt) const {}
1.250
1.251 - /// The base type of the node iterators.
1.252 + /// Checks if a node iterator is valid
1.253
1.254 - /// This is the base type of each node iterators,
1.255 - /// thus each kind of node iterator will convert to this.
1.256 - class Node {
1.257 - public:
1.258 - /// @warning The default constructor sets the iterator
1.259 - /// to an undefined value.
1.260 - Node() {} //FIXME
1.261 - /// Invalid constructor \& conversion.
1.262 + ///\todo Maybe, it would be better if iterator converted to
1.263 + ///bool directly, as Jacint prefers.
1.264 + bool valid(const Node&) const { return true;}
1.265 + /// Checks if an edge iterator is valid
1.266
1.267 - /// This constructor initializes the iterator to be invalid.
1.268 - /// \sa Invalid for more details.
1.269 + ///\todo Maybe, it would be better if iterator converted to
1.270 + ///bool directly, as Jacint prefers.
1.271 + bool valid(const Edge&) const { return true;}
1.272
1.273 - Node(Invalid) {}
1.274 - //Node(const Node &) {}
1.275 + ///Gives back the \e id of a node.
1.276
1.277 - /// Two iterators are equal if and only if they point to the
1.278 - /// same object or both are invalid.
1.279 - bool operator==(Node) const { return true; }
1.280 + ///\warning Not all graph structures provide this feature.
1.281 + ///
1.282 + int id(const Node&) const { return 0;}
1.283 + ///Gives back the \e id of an edge.
1.284
1.285 - /// \sa \ref operator==(Node n)
1.286 + ///\warning Not all graph structures provide this feature.
1.287 ///
1.288 - bool operator!=(Node) const { return true; }
1.289 + int id(const Edge&) const { return 0;}
1.290
1.291 - bool operator<(Node) const { return true; }
1.292 - };
1.293 + /// Resets the graph.
1.294 +
1.295 + /// This function deletes all edges and nodes of the graph.
1.296 + /// It also frees the memory allocated to store them.
1.297 + void clear() {}
1.298 +
1.299 + int nodeNum() const { return 0;}
1.300 + int edgeNum() const { return 0;}
1.301 +
1.302 +
1.303 +
1.304 + ///Reference map of the nodes to type \c T.
1.305 +
1.306 + ///Reference map of the nodes to type \c T.
1.307 + /// \sa ReferenceSkeleton
1.308 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.309 + /// needs extra attention!
1.310 +
1.311 + template<class T> class NodeMap
1.312 + : public ReferenceMap< Node, T >
1.313 + {
1.314 + public:
1.315 +
1.316 + class ReferenceMap<Node,T>;
1.317 +
1.318 + NodeMap(const StaticGraphSkeleton &) {}
1.319 + NodeMap(const StaticGraphSkeleton &, T) {}
1.320 +
1.321 + ///Copy constructor
1.322 + template<typename TT> NodeMap(const NodeMap<TT> &) {}
1.323 + ///Assignment operator
1.324 + template<typename TT> NodeMap &operator=(const NodeMap<TT> &)
1.325 + {return *this;}
1.326 + };
1.327 +
1.328 + ///Reference map of the edges to type \c T.
1.329 +
1.330 + ///Reference map of the edges to type \c T.
1.331 + /// \sa ReferenceSkeleton
1.332 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.333 + /// needs extra attention!
1.334 + template<class T> class EdgeMap
1.335 + : public ReferenceMap<Edge,T>
1.336 + {
1.337 + public:
1.338 + typedef T ValueType;
1.339 + typedef Edge KeyType;
1.340 +
1.341 + EdgeMap(const StaticGraphSkeleton &) {}
1.342 + EdgeMap(const StaticGraphSkeleton &, T ) {}
1.343
1.344 - /// This iterator goes through each node.
1.345 -
1.346 - /// This iterator goes through each node.
1.347 - /// Its usage is quite simple, for example you can count the number
1.348 - /// of nodes in graph \c G of type \c Graph like this:
1.349 - /// \code
1.350 - ///int count=0;
1.351 - ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
1.352 - /// \endcode
1.353 - class NodeIt : public Node {
1.354 - public:
1.355 - /// @warning The default constructor sets the iterator
1.356 - /// to an undefined value.
1.357 - NodeIt() {} //FIXME
1.358 - /// Invalid constructor \& conversion.
1.359 -
1.360 - /// Initialize the iterator to be invalid
1.361 - /// \sa Invalid for more details.
1.362 - NodeIt(Invalid) {}
1.363 - /// Sets the iterator to the first node of \c G.
1.364 - NodeIt(const GraphSkeleton &) {}
1.365 - /// @warning The default constructor sets the iterator
1.366 - /// to an undefined value.
1.367 - NodeIt(const NodeIt &n) : Node(n) {}
1.368 - };
1.369 -
1.370 -
1.371 - /// The base type of the edge iterators.
1.372 - class Edge {
1.373 - public:
1.374 - /// @warning The default constructor sets the iterator
1.375 - /// to an undefined value.
1.376 - Edge() {} //FIXME
1.377 - /// Initialize the iterator to be invalid
1.378 - Edge(Invalid) {}
1.379 - /// Two iterators are equal if and only if they point to the
1.380 - /// same object or both are invalid.
1.381 - bool operator==(Edge) const { return true; }
1.382 - bool operator!=(Edge) const { return true; }
1.383 - bool operator<(Edge) const { return true; }
1.384 - };
1.385 -
1.386 - /// This iterator goes trough the outgoing edges of a node.
1.387 -
1.388 - /// This iterator goes trough the \e outgoing edges of a certain node
1.389 - /// of a graph.
1.390 - /// Its usage is quite simple, for example you can count the number
1.391 - /// of outgoing edges of a node \c n
1.392 - /// in graph \c G of type \c Graph as follows.
1.393 - /// \code
1.394 - ///int count=0;
1.395 - ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.396 - /// \endcode
1.397 -
1.398 - class OutEdgeIt : public Edge {
1.399 - public:
1.400 - /// @warning The default constructor sets the iterator
1.401 - /// to an undefined value.
1.402 - OutEdgeIt() {}
1.403 - /// Initialize the iterator to be invalid
1.404 - OutEdgeIt(Invalid) {}
1.405 - /// This constructor sets the iterator to first outgoing edge.
1.406 -
1.407 - /// This constructor set the iterator to the first outgoing edge of
1.408 - /// node
1.409 - ///@param n the node
1.410 - ///@param G the graph
1.411 - OutEdgeIt(const GraphSkeleton &, Node) {}
1.412 + ///Copy constructor
1.413 + template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
1.414 + ///Assignment operator
1.415 + template<typename TT> EdgeMap &operator=(const EdgeMap<TT> &)
1.416 + {return *this;}
1.417 + };
1.418 };
1.419
1.420 - /// This iterator goes trough the incoming edges of a node.
1.421
1.422 - /// This iterator goes trough the \e incoming edges of a certain node
1.423 - /// of a graph.
1.424 - /// Its usage is quite simple, for example you can count the number
1.425 - /// of outgoing edges of a node \c n
1.426 - /// in graph \c G of type \c Graph as follows.
1.427 - /// \code
1.428 - ///int count=0;
1.429 - ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.430 - /// \endcode
1.431 +
1.432 + /// An empty graph class.
1.433
1.434 - class InEdgeIt : public Edge {
1.435 + /// This class provides everything that \c StaticGraphSkeleton
1.436 + /// with additional functionality which enables to build a
1.437 + /// graph from scratch.
1.438 + class GraphSkeleton : public StaticGraphSkeleton
1.439 + {
1.440 public:
1.441 - /// @warning The default constructor sets the iterator
1.442 - /// to an undefined value.
1.443 - InEdgeIt() {}
1.444 - /// Initialize the iterator to be invalid
1.445 - InEdgeIt(Invalid) {}
1.446 - InEdgeIt(const GraphSkeleton &, Node) {}
1.447 - };
1.448 - // class SymEdgeIt : public Edge {};
1.449 + /// Defalult constructor.
1.450 + GraphSkeleton() {}
1.451 + ///Copy consructor.
1.452
1.453 - /// This iterator goes through each edge.
1.454 + ///\todo It is not clear, what we expect from a copy constructor.
1.455 + ///E.g. How to assign the nodes/edges to each other? What about maps?
1.456 + GraphSkeleton(const GraphSkeleton &G) {}
1.457
1.458 - /// This iterator goes through each edge of a graph.
1.459 - /// Its usage is quite simple, for example you can count the number
1.460 - /// of edges in a graph \c G of type \c Graph as follows:
1.461 - /// \code
1.462 - ///int count=0;
1.463 - ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
1.464 - /// \endcode
1.465 - class EdgeIt : public Edge {
1.466 - public:
1.467 - /// @warning The default constructor sets the iterator
1.468 - /// to an undefined value.
1.469 - EdgeIt() {}
1.470 - /// Initialize the iterator to be invalid
1.471 - EdgeIt(Invalid) {}
1.472 - EdgeIt(const GraphSkeleton &) {}
1.473 + ///Add a new node to the graph.
1.474 +
1.475 + /// \return the new node.
1.476 + ///
1.477 + Node addNode() { return INVALID;}
1.478 + ///Add a new edge to the graph.
1.479 +
1.480 + ///Add a new edge to the graph with tail node \c tail
1.481 + ///and head node \c head.
1.482 + ///\return the new edge.
1.483 + Edge addEdge(Node, Node) { return INVALID;}
1.484 +
1.485 + /// Resets the graph.
1.486 +
1.487 + /// This function deletes all edges and nodes of the graph.
1.488 + /// It also frees the memory allocated to store them.
1.489 + /// \todo It might belong to \c EraseableGraphSkeleton.
1.490 + void clear() {}
1.491 };
1.492
1.493 - /// First node of the graph.
1.494 -
1.495 - /// \retval i the first node.
1.496 - /// \return the first node.
1.497 - ///
1.498 - NodeIt &first(NodeIt &i) const { return i;}
1.499 -
1.500 - /// The first incoming edge.
1.501 - InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
1.502 - /// The first outgoing edge.
1.503 - OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
1.504 - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.505 - /// The first edge of the Graph.
1.506 - EdgeIt &first(EdgeIt &i) const { return i;}
1.507 -
1.508 -// Node getNext(Node) const {}
1.509 -// InEdgeIt getNext(InEdgeIt) const {}
1.510 -// OutEdgeIt getNext(OutEdgeIt) const {}
1.511 -// //SymEdgeIt getNext(SymEdgeIt) const {}
1.512 -// EdgeIt getNext(EdgeIt) const {}
1.513 -
1.514 - /// Go to the next node.
1.515 - NodeIt &next(NodeIt &i) const { return i;}
1.516 - /// Go to the next incoming edge.
1.517 - InEdgeIt &next(InEdgeIt &i) const { return i;}
1.518 - /// Go to the next outgoing edge.
1.519 - OutEdgeIt &next(OutEdgeIt &i) const { return i;}
1.520 - //SymEdgeIt &next(SymEdgeIt &) const {}
1.521 - /// Go to the next edge.
1.522 - EdgeIt &next(EdgeIt &i) const { return i;}
1.523 -
1.524 - ///Gives back the head node of an edge.
1.525 - Node head(Edge) const { return INVALID; }
1.526 - ///Gives back the tail node of an edge.
1.527 - Node tail(Edge) const { return INVALID; }
1.528 + /// An empty eraseable graph class.
1.529
1.530 - // Node aNode(InEdgeIt) const {}
1.531 - // Node aNode(OutEdgeIt) const {}
1.532 - // Node aNode(SymEdgeIt) const {}
1.533 -
1.534 - // Node bNode(InEdgeIt) const {}
1.535 - // Node bNode(OutEdgeIt) const {}
1.536 - // Node bNode(SymEdgeIt) const {}
1.537 -
1.538 - /// Checks if a node iterator is valid
1.539 -
1.540 - ///\todo Maybe, it would be better if iterator converted to
1.541 - ///bool directly, as Jacint prefers.
1.542 - bool valid(const Node&) const { return true;}
1.543 - /// Checks if an edge iterator is valid
1.544 -
1.545 - ///\todo Maybe, it would be better if iterator converted to
1.546 - ///bool directly, as Jacint prefers.
1.547 - bool valid(const Edge&) const { return true;}
1.548 -
1.549 - ///Gives back the \e id of a node.
1.550 -
1.551 - ///\warning Not all graph structures provide this feature.
1.552 - ///
1.553 - int id(const Node&) const { return 0;}
1.554 - ///Gives back the \e id of an edge.
1.555 -
1.556 - ///\warning Not all graph structures provide this feature.
1.557 - ///
1.558 - int id(const Edge&) const { return 0;}
1.559 -
1.560 - //void setInvalid(Node &) const {};
1.561 - //void setInvalid(Edge &) const {};
1.562 -
1.563 - ///Add a new node to the graph.
1.564 -
1.565 - /// \return the new node.
1.566 - ///
1.567 - Node addNode() { return INVALID;}
1.568 - ///Add a new edge to the graph.
1.569 -
1.570 - ///Add a new edge to the graph with tail node \c tail
1.571 - ///and head node \c head.
1.572 - ///\return the new edge.
1.573 - Edge addEdge(Node, Node) { return INVALID;}
1.574 -
1.575 - /// Resets the graph.
1.576 -
1.577 - /// This function deletes all edges and nodes of the graph.
1.578 - /// It also frees the memory allocated to store them.
1.579 - void clear() {}
1.580 -
1.581 - int nodeNum() const { return 0;}
1.582 - int edgeNum() const { return 0;}
1.583 -
1.584 - ///Read/write/reference map of the nodes to type \c T.
1.585 -
1.586 - ///Read/write/reference map of the nodes to type \c T.
1.587 - /// \sa MemoryMapSkeleton
1.588 - /// \todo We may need copy constructor
1.589 - /// \todo We may need conversion from other nodetype
1.590 - /// \todo We may need operator=
1.591 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.592 - /// needs extra attention!
1.593 -
1.594 - template<class T> class NodeMap
1.595 + /// This class is an extension of \c GraphSkeleton. It also makes it
1.596 + /// possible to erase edges or nodes.
1.597 + class EraseableGraphSkeleton : public GraphSkeleton
1.598 {
1.599 public:
1.600 - typedef T ValueType;
1.601 - typedef Node KeyType;
1.602 + /// Deletes a node.
1.603 + void erase(Node n) {}
1.604 + /// Deletes an edge.
1.605 + void erase(Edge e) {}
1.606
1.607 - NodeMap(const GraphSkeleton &) {}
1.608 - NodeMap(const GraphSkeleton &, T) {}
1.609 -
1.610 - template<typename TT> NodeMap(const NodeMap<TT> &) {}
1.611 -
1.612 - /// Sets the value of a node.
1.613 -
1.614 - /// Sets the value associated with node \c i to the value \c t.
1.615 - ///
1.616 - void set(Node, T) {}
1.617 - // Gets the value of a node.
1.618 - //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary?
1.619 - T &operator[](Node) {return *(T*)0;}
1.620 - const T &operator[](Node) const {return *(T*)0;}
1.621 -
1.622 - /// Updates the map if the graph has been changed
1.623 -
1.624 - /// \todo Do we need this?
1.625 - ///
1.626 - void update() {}
1.627 - void update(T a) {} //FIXME: Is it necessary
1.628 + /// Defalult constructor.
1.629 + EraseableGraphSkeleton() {}
1.630 + ///Copy consructor.
1.631 + EraseableGraphSkeleton(const GraphSkeleton &G) {}
1.632 };
1.633
1.634 - ///Read/write/reference map of the edges to type \c T.
1.635 -
1.636 - ///Read/write/reference map of the edges to type \c T.
1.637 - ///It behaves exactly in the same way as \ref NodeMap.
1.638 - /// \sa NodeMap
1.639 - /// \sa MemoryMapSkeleton
1.640 - /// \todo We may need copy constructor
1.641 - /// \todo We may need conversion from other edgetype
1.642 - /// \todo We may need operator=
1.643 - template<class T> class EdgeMap
1.644 - {
1.645 - public:
1.646 - typedef T ValueType;
1.647 - typedef Edge KeyType;
1.648 -
1.649 - EdgeMap(const GraphSkeleton &) {}
1.650 - EdgeMap(const GraphSkeleton &, T ) {}
1.651 -
1.652 - ///\todo It can copy between different types.
1.653 - ///
1.654 - template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
1.655 -
1.656 - void set(Edge, T) {}
1.657 - //T get(Edge) const {return *(T*)0;}
1.658 - T &operator[](Edge) {return *(T*)0;}
1.659 - const T &operator[](Edge) const {return *(T*)0;}
1.660 -
1.661 - void update() {}
1.662 - void update(T a) {} //FIXME: Is it necessary
1.663 - };
1.664 - };
1.665 -
1.666 - /// An empty eraseable graph class.
1.667 + // @}
1.668 + } //namespace skeleton
1.669
1.670 - /// This class provides all the common features of an \e eraseable graph
1.671 - /// structure,
1.672 - /// however completely without implementations and real data structures
1.673 - /// behind the interface.
1.674 - /// All graph algorithms should compile with this class, but it will not
1.675 - /// run properly, of course.
1.676 - ///
1.677 - /// \todo This blabla could be replaced by a sepatate description about
1.678 - /// Skeletons.
1.679 - ///
1.680 - /// It can be used for checking the interface compatibility,
1.681 - /// or it can serve as a skeleton of a new graph structure.
1.682 - ///
1.683 - /// Also, you will find here the full documentation of a certain graph
1.684 - /// feature, the documentation of a real graph imlementation
1.685 - /// like @ref ListGraph or
1.686 - /// @ref SmartGraph will just refer to this structure.
1.687 - class EraseableGraphSkeleton : public GraphSkeleton
1.688 - {
1.689 - public:
1.690 - /// Deletes a node.
1.691 - void erase(Node n) {}
1.692 - /// Deletes an edge.
1.693 - void erase(Edge e) {}
1.694 -
1.695 - /// Defalult constructor.
1.696 - EraseableGraphSkeleton() {}
1.697 - ///Copy consructor.
1.698 - EraseableGraphSkeleton(const GraphSkeleton &G) {}
1.699 - };
1.700 -
1.701 -
1.702 - // @}
1.703 -
1.704 } //namespace hugo
1.705
1.706
2.1 --- a/src/hugo/skeletons/maps.h Thu Jul 22 19:49:28 2004 +0000
2.2 +++ b/src/hugo/skeletons/maps.h Thu Jul 22 19:59:18 2004 +0000
2.3 @@ -12,7 +12,7 @@
2.4
2.5 /// Readable map concept
2.6 template<typename K, typename T>
2.7 - class ReadableMap
2.8 + class ReadMap
2.9 {
2.10 public:
2.11 /// Map's key type.
2.12 @@ -23,18 +23,14 @@
2.13 /// Returns the value associated with a key.
2.14 ValueType operator[](const KeyType &k) const {return ValueType();}
2.15
2.16 - /// Copy contsructor. (optional)
2.17 - ReadableMap(const ReadableMap&) {}
2.18 - /// Assignment operator. (optional)
2.19 - ReadableMap& operator=(const ReadableMap&) {return *this;}
2.20 -
2.21 - ReadableMap() {}
2.22 + ///Default constructor
2.23 + ReadMap() {}
2.24 };
2.25
2.26
2.27 /// Writable map concept
2.28 template<typename K, typename T>
2.29 - class WritableMap
2.30 + class WriteMap
2.31 {
2.32 public:
2.33 /// Map's key type.
2.34 @@ -45,13 +41,14 @@
2.35 /// Sets the value associated with a key.
2.36 void set(const KeyType &k,const ValueType &t) {}
2.37
2.38 - WritableMap() {}
2.39 + ///Default constructor
2.40 + WriteMap() {}
2.41 };
2.42
2.43 ///Read/Writeable map concept
2.44 template<typename K, typename T>
2.45 - class ReadWritableMap : public ReadableMap<K,T>,
2.46 - public WritableMap<K,T>
2.47 + class ReadWriteMap : public ReadMap<K,T>,
2.48 + public WriteMap<K,T>
2.49 {
2.50 public:
2.51 /// Map's key type.
2.52 @@ -64,67 +61,39 @@
2.53 /// Sets the value associated with a key.
2.54 void set(const KeyType &k,const ValueType &t) {}
2.55
2.56 - /// Copy contsructor. (optional)
2.57 - ReadWritableMap(const ReadWritableMap&) {}
2.58 - /// Assignment operator. (optional)
2.59 - ReadWritableMap& operator=(const ReadWritableMap&) {return *this;}
2.60 -
2.61 - /// Facility to define a map with an other value type (optional)
2.62 - template<typename T1>
2.63 - struct rebind {
2.64 - /// The type of a map with the given value type
2.65 - typedef ReadWritableMap<K,T1> other;
2.66 - };
2.67 - /// @brief Constructor that copies all keys from the other map and
2.68 - /// assigns to them a default value (optional)
2.69 - template<typename T1>
2.70 - ReadWritableMap(const ReadWritableMap<K,T1> &map, const ValueType &v) {}
2.71 -
2.72 - ReadWritableMap() {}
2.73 + ///Default constructor
2.74 + ReadWriteMap() {}
2.75 };
2.76
2.77
2.78 ///Dereferable map concept
2.79 template<typename K, typename T>
2.80 - class DereferableMap : public ReadWritableMap<K,T>
2.81 + class ReferenceMap : public ReadWriteMap<K,T>
2.82 {
2.83 public:
2.84 /// Map's key type.
2.85 typedef K KeyType;
2.86 /// Map's value type. (The type of objects associated with the keys).
2.87 typedef T ValueType;
2.88 - /// Map's reference type. (Reference to an object associated with a key)
2.89 +
2.90 + protected:
2.91 + ValueType tmp;
2.92 + public:
2.93 typedef ValueType& ReferenceType;
2.94 /// Map's const reference type.
2.95 typedef const ValueType& ConstReferenceType;
2.96
2.97 ///Returns a reference to the value associated to a key.
2.98 - ReferenceType operator[](const KeyType &i);
2.99 + ReferenceType operator[](const KeyType &i) { return tmp; }
2.100 ///Returns a const reference to the value associated to a key.
2.101 - ConstReferenceType operator[](const KeyType &i) const;
2.102 + ConstReferenceType operator[](const KeyType &i) const
2.103 + { return tmp; }
2.104 /// Sets the value associated with a key.
2.105 void set(const KeyType &k,const ValueType &t) { operator[](k)=t; }
2.106
2.107 - /// Copy contsructor. (optional)
2.108 - DereferableMap(const DereferableMap&) {}
2.109 - /// Assignment operator. (optional)
2.110 - DereferableMap& operator=(const DereferableMap&) {return *this;}
2.111 -
2.112 - /// Facility to define a map with an other value type (optional)
2.113 - template<typename T1>
2.114 - struct rebind {
2.115 - /// The type of a map with the given value type
2.116 - typedef DereferableMap<K,T1> other;
2.117 - };
2.118 - /// @brief Constructor that copies all keys from the other map and
2.119 - /// assigns to them a default value (optional)
2.120 - template<typename T1>
2.121 - DereferableMap(const DereferableMap<K,T1> &map, const ValueType &v) {}
2.122 -
2.123 - DereferableMap() {}
2.124 + ///Default constructor
2.125 + ReferenceMap() {}
2.126 };
2.127 -
2.128 -
2.129 - }
2.130 -}
2.131 + } //namespace skeleton
2.132 +} //namespace hugo
2.133 #endif // HUGO_MAPSKELETON_H