1.1 --- a/src/hugo/skeletons/graph.h Wed Sep 29 14:12:26 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,510 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/hugo/skeletons/graph.h - Part of HUGOlib, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef HUGO_SKELETON_GRAPH_H
1.21 -#define HUGO_SKELETON_GRAPH_H
1.22 -
1.23 -///\ingroup skeletons
1.24 -///\file
1.25 -///\brief Declaration of Graph.
1.26 -
1.27 -#include <hugo/invalid.h>
1.28 -#include <hugo/skeletons/maps.h>
1.29 -
1.30 -namespace hugo {
1.31 - namespace skeleton {
1.32 -
1.33 - /// \addtogroup skeletons
1.34 - /// @{
1.35 -
1.36 - /// An empty static graph class.
1.37 -
1.38 - /// This class provides all the common features of a graph structure,
1.39 - /// however completely without implementations and real data structures
1.40 - /// behind the interface.
1.41 - /// All graph algorithms should compile with this class, but it will not
1.42 - /// run properly, of course.
1.43 - ///
1.44 - /// It can be used for checking the interface compatibility,
1.45 - /// or it can serve as a skeleton of a new graph structure.
1.46 - ///
1.47 - /// Also, you will find here the full documentation of a certain graph
1.48 - /// feature, the documentation of a real graph imlementation
1.49 - /// like @ref ListGraph or
1.50 - /// @ref SmartGraph will just refer to this structure.
1.51 - class StaticGraph
1.52 - {
1.53 - public:
1.54 - /// Defalult constructor.
1.55 -
1.56 - /// Defalult constructor.
1.57 - ///
1.58 - StaticGraph() { }
1.59 - ///Copy consructor.
1.60 -
1.61 -// ///\todo It is not clear, what we expect from a copy constructor.
1.62 -// ///E.g. How to assign the nodes/edges to each other? What about maps?
1.63 -// StaticGraph(const StaticGraph& g) { }
1.64 -
1.65 - /// The base type of node iterators,
1.66 - /// or in other words, the trivial node iterator.
1.67 -
1.68 - /// This is the base type of each node iterator,
1.69 - /// thus each kind of node iterator converts to this.
1.70 - /// More precisely each kind of node iterator should be inherited
1.71 - /// from the trivial node iterator.
1.72 - class Node {
1.73 - public:
1.74 - /// Default constructor
1.75 -
1.76 - /// @warning The default constructor sets the iterator
1.77 - /// to an undefined value.
1.78 - Node() { }
1.79 - /// Copy constructor.
1.80 -
1.81 - /// Copy constructor.
1.82 - ///
1.83 - Node(const Node&) { }
1.84 -
1.85 - /// Invalid constructor \& conversion.
1.86 -
1.87 - /// This constructor initializes the iterator to be invalid.
1.88 - /// \sa Invalid for more details.
1.89 - Node(Invalid) { }
1.90 - /// Equality operator
1.91 -
1.92 - /// Two iterators are equal if and only if they point to the
1.93 - /// same object or both are invalid.
1.94 - bool operator==(Node) const { return true; }
1.95 -
1.96 - /// Inequality operator
1.97 -
1.98 - /// \sa operator==(Node n)
1.99 - ///
1.100 - bool operator!=(Node) const { return true; }
1.101 -
1.102 - ///Comparison operator.
1.103 -
1.104 - ///This is a strict ordering between the nodes.
1.105 - ///
1.106 - ///This ordering can be different from the order in which NodeIt
1.107 - ///goes through the nodes.
1.108 - ///\todo Possibly we don't need it.
1.109 - bool operator<(Node) const { return true; }
1.110 - };
1.111 -
1.112 - /// This iterator goes through each node.
1.113 -
1.114 - /// This iterator goes through each node.
1.115 - /// Its usage is quite simple, for example you can count the number
1.116 - /// of nodes in graph \c g of type \c Graph like this:
1.117 - /// \code
1.118 - /// int count=0;
1.119 - /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.120 - /// \endcode
1.121 - class NodeIt : public Node {
1.122 - public:
1.123 - /// Default constructor
1.124 -
1.125 - /// @warning The default constructor sets the iterator
1.126 - /// to an undefined value.
1.127 - NodeIt() { }
1.128 - /// Copy constructor.
1.129 -
1.130 - /// Copy constructor.
1.131 - ///
1.132 - NodeIt(const NodeIt&) { }
1.133 - /// Invalid constructor \& conversion.
1.134 -
1.135 - /// Initialize the iterator to be invalid.
1.136 - /// \sa Invalid for more details.
1.137 - NodeIt(Invalid) { }
1.138 - /// Sets the iterator to the first node.
1.139 -
1.140 - /// Sets the iterator to the first node of \c g.
1.141 - ///
1.142 - NodeIt(const StaticGraph& g) { }
1.143 - /// Node -> NodeIt conversion.
1.144 -
1.145 - /// Sets the iterator to the node of \c g pointed by the trivial
1.146 - /// iterator n.
1.147 - /// This feature necessitates that each time we
1.148 - /// iterate the edge-set, the iteration order is the same.
1.149 - NodeIt(const StaticGraph& g, const Node& n) { }
1.150 - /// Next node.
1.151 -
1.152 - /// Assign the iterator to the next node.
1.153 - ///
1.154 - NodeIt& operator++() { return *this; }
1.155 - };
1.156 -
1.157 -
1.158 - /// The base type of the edge iterators.
1.159 -
1.160 - /// The base type of the edge iterators.
1.161 - ///
1.162 - class Edge {
1.163 - public:
1.164 - /// Default constructor
1.165 -
1.166 - /// @warning The default constructor sets the iterator
1.167 - /// to an undefined value.
1.168 - Edge() { }
1.169 - /// Copy constructor.
1.170 -
1.171 - /// Copy constructor.
1.172 - ///
1.173 - Edge(const Edge&) { }
1.174 - /// Initialize the iterator to be invalid.
1.175 -
1.176 - /// Initialize the iterator to be invalid.
1.177 - ///
1.178 - Edge(Invalid) { }
1.179 - /// Equality operator
1.180 -
1.181 - /// Two iterators are equal if and only if they point to the
1.182 - /// same object or both are invalid.
1.183 - bool operator==(Edge) const { return true; }
1.184 - /// Inequality operator
1.185 -
1.186 - /// \sa operator==(Node n)
1.187 - ///
1.188 - bool operator!=(Edge) const { return true; }
1.189 - ///Comparison operator.
1.190 -
1.191 - ///This is a strict ordering between the nodes.
1.192 - ///
1.193 - ///This ordering can be different from the order in which NodeIt
1.194 - ///goes through the nodes.
1.195 - ///\todo Possibly we don't need it.
1.196 - bool operator<(Edge) const { return true; }
1.197 - };
1.198 -
1.199 - /// This iterator goes trough the outgoing edges of a node.
1.200 -
1.201 - /// This iterator goes trough the \e outgoing edges of a certain node
1.202 - /// of a graph.
1.203 - /// Its usage is quite simple, for example you can count the number
1.204 - /// of outgoing edges of a node \c n
1.205 - /// in graph \c g of type \c Graph as follows.
1.206 - /// \code
1.207 - /// int count=0;
1.208 - /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.209 - /// \endcode
1.210 -
1.211 - class OutEdgeIt : public Edge {
1.212 - public:
1.213 - /// Default constructor
1.214 -
1.215 - /// @warning The default constructor sets the iterator
1.216 - /// to an undefined value.
1.217 - OutEdgeIt() { }
1.218 - /// Copy constructor.
1.219 -
1.220 - /// Copy constructor.
1.221 - ///
1.222 - OutEdgeIt(const OutEdgeIt&) { }
1.223 - /// Initialize the iterator to be invalid.
1.224 -
1.225 - /// Initialize the iterator to be invalid.
1.226 - ///
1.227 - OutEdgeIt(Invalid) { }
1.228 - /// This constructor sets the iterator to first outgoing edge.
1.229 -
1.230 - /// This constructor set the iterator to the first outgoing edge of
1.231 - /// node
1.232 - ///@param n the node
1.233 - ///@param g the graph
1.234 - OutEdgeIt(const StaticGraph& g, const Node& n) { }
1.235 - /// Edge -> OutEdgeIt conversion
1.236 -
1.237 - /// Sets the iterator to the value of the trivial iterator \c e.
1.238 - /// This feature necessitates that each time we
1.239 - /// iterate the edge-set, the iteration order is the same.
1.240 - OutEdgeIt(const StaticGraph& g, const Edge& e) { }
1.241 - ///Next outgoing edge
1.242 -
1.243 - /// Assign the iterator to the next
1.244 - /// outgoing edge of the corresponding node.
1.245 - OutEdgeIt& operator++() { return *this; }
1.246 - };
1.247 -
1.248 - /// This iterator goes trough the incoming edges of a node.
1.249 -
1.250 - /// This iterator goes trough the \e incoming edges of a certain node
1.251 - /// of a graph.
1.252 - /// Its usage is quite simple, for example you can count the number
1.253 - /// of outgoing edges of a node \c n
1.254 - /// in graph \c g of type \c Graph as follows.
1.255 - /// \code
1.256 - /// int count=0;
1.257 - /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.258 - /// \endcode
1.259 -
1.260 - class InEdgeIt : public Edge {
1.261 - public:
1.262 - /// Default constructor
1.263 -
1.264 - /// @warning The default constructor sets the iterator
1.265 - /// to an undefined value.
1.266 - InEdgeIt() { }
1.267 - /// Copy constructor.
1.268 -
1.269 - /// Copy constructor.
1.270 - ///
1.271 - InEdgeIt(const InEdgeIt&) { }
1.272 - /// Initialize the iterator to be invalid.
1.273 -
1.274 - /// Initialize the iterator to be invalid.
1.275 - ///
1.276 - InEdgeIt(Invalid) { }
1.277 - /// This constructor sets the iterator to first incoming edge.
1.278 -
1.279 - /// This constructor set the iterator to the first incoming edge of
1.280 - /// node
1.281 - ///@param n the node
1.282 - ///@param g the graph
1.283 - InEdgeIt(const StaticGraph& g, const Node& n) { }
1.284 - /// Edge -> InEdgeIt conversion
1.285 -
1.286 - /// Sets the iterator to the value of the trivial iterator \c e.
1.287 - /// This feature necessitates that each time we
1.288 - /// iterate the edge-set, the iteration order is the same.
1.289 - InEdgeIt(const StaticGraph& g, const Edge& n) { }
1.290 - /// Next incoming edge
1.291 -
1.292 - /// Assign the iterator to the next inedge of the corresponding node.
1.293 - ///
1.294 - InEdgeIt& operator++() { return *this; }
1.295 - };
1.296 - /// This iterator goes through each edge.
1.297 -
1.298 - /// This iterator goes through each edge of a graph.
1.299 - /// Its usage is quite simple, for example you can count the number
1.300 - /// of edges in a graph \c g of type \c Graph as follows:
1.301 - /// \code
1.302 - /// int count=0;
1.303 - /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.304 - /// \endcode
1.305 - class EdgeIt : public Edge {
1.306 - public:
1.307 - /// Default constructor
1.308 -
1.309 - /// @warning The default constructor sets the iterator
1.310 - /// to an undefined value.
1.311 - EdgeIt() { }
1.312 - /// Copy constructor.
1.313 -
1.314 - /// Copy constructor.
1.315 - ///
1.316 - EdgeIt(const EdgeIt&) { }
1.317 - /// Initialize the iterator to be invalid.
1.318 -
1.319 - /// Initialize the iterator to be invalid.
1.320 - ///
1.321 - EdgeIt(Invalid) { }
1.322 - /// This constructor sets the iterator to first edge.
1.323 -
1.324 - /// This constructor set the iterator to the first edge of
1.325 - /// node
1.326 - ///@param g the graph
1.327 - EdgeIt(const StaticGraph& g) { }
1.328 - /// Edge -> EdgeIt conversion
1.329 -
1.330 - /// Sets the iterator to the value of the trivial iterator \c e.
1.331 - /// This feature necessitates that each time we
1.332 - /// iterate the edge-set, the iteration order is the same.
1.333 - EdgeIt(const StaticGraph&, const Edge&) { }
1.334 - ///Next edge
1.335 -
1.336 - /// Assign the iterator to the next
1.337 - /// edge of the corresponding node.
1.338 - EdgeIt& operator++() { return *this; }
1.339 - };
1.340 -
1.341 - /// First node of the graph.
1.342 -
1.343 - /// \retval i the first node.
1.344 - /// \return the first node.
1.345 - ///
1.346 - NodeIt& first(NodeIt& i) const { return i; }
1.347 -
1.348 - /// The first incoming edge.
1.349 -
1.350 - /// The first incoming edge.
1.351 - ///
1.352 - InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
1.353 - /// The first outgoing edge.
1.354 -
1.355 - /// The first outgoing edge.
1.356 - ///
1.357 - OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
1.358 - /// The first edge of the Graph.
1.359 -
1.360 - /// The first edge of the Graph.
1.361 - ///
1.362 - EdgeIt& first(EdgeIt& i) const { return i; }
1.363 -
1.364 - ///Gives back the head node of an edge.
1.365 -
1.366 - ///Gives back the head node of an edge.
1.367 - ///
1.368 - Node head(Edge) const { return INVALID; }
1.369 - ///Gives back the tail node of an edge.
1.370 -
1.371 - ///Gives back the tail node of an edge.
1.372 - ///
1.373 - Node tail(Edge) const { return INVALID; }
1.374 -
1.375 - ///Gives back the \e id of a node.
1.376 -
1.377 - ///\warning Not all graph structures provide this feature.
1.378 - ///
1.379 - ///\todo Should each graph provide \c id?
1.380 - int id(const Node&) const { return 0; }
1.381 - ///Gives back the \e id of an edge.
1.382 -
1.383 - ///\warning Not all graph structures provide this feature.
1.384 - ///
1.385 - ///\todo Should each graph provide \c id?
1.386 - int id(const Edge&) const { return 0; }
1.387 -
1.388 - ///\e
1.389 -
1.390 - ///\todo Should it be in the concept?
1.391 - ///
1.392 - int nodeNum() const { return 0; }
1.393 - ///\e
1.394 -
1.395 - ///\todo Should it be in the concept?
1.396 - ///
1.397 - int edgeNum() const { return 0; }
1.398 -
1.399 -
1.400 - ///Reference map of the nodes to type \c T.
1.401 -
1.402 - /// \ingroup skeletons
1.403 - ///Reference map of the nodes to type \c T.
1.404 - /// \sa Reference
1.405 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.406 - /// needs some extra attention!
1.407 - template<class T> class NodeMap : public ReferenceMap< Node, T >
1.408 - {
1.409 - public:
1.410 -
1.411 - ///\e
1.412 - NodeMap(const StaticGraph&) { }
1.413 - ///\e
1.414 - NodeMap(const StaticGraph&, T) { }
1.415 -
1.416 - ///Copy constructor
1.417 - template<typename TT> NodeMap(const NodeMap<TT>&) { }
1.418 - ///Assignment operator
1.419 - template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
1.420 - { return *this; }
1.421 - };
1.422 -
1.423 - ///Reference map of the edges to type \c T.
1.424 -
1.425 - /// \ingroup skeletons
1.426 - ///Reference map of the edges to type \c T.
1.427 - /// \sa Reference
1.428 - /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.429 - /// needs some extra attention!
1.430 - template<class T> class EdgeMap
1.431 - : public ReferenceMap<Edge,T>
1.432 - {
1.433 - public:
1.434 -
1.435 - ///\e
1.436 - EdgeMap(const StaticGraph&) { }
1.437 - ///\e
1.438 - EdgeMap(const StaticGraph&, T) { }
1.439 -
1.440 - ///Copy constructor
1.441 - template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
1.442 - ///Assignment operator
1.443 - template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
1.444 - { return *this; }
1.445 - };
1.446 - };
1.447 -
1.448 -
1.449 -
1.450 - /// An empty non-static graph class.
1.451 -
1.452 - /// This class provides everything that \ref StaticGraph
1.453 - /// with additional functionality which enables to build a
1.454 - /// graph from scratch.
1.455 - class ExtendableGraph : public StaticGraph
1.456 - {
1.457 - public:
1.458 - /// Defalult constructor.
1.459 -
1.460 - /// Defalult constructor.
1.461 - ///
1.462 - ExtendableGraph() { }
1.463 - ///Add a new node to the graph.
1.464 -
1.465 - /// \return the new node.
1.466 - ///
1.467 - Node addNode() { return INVALID; }
1.468 - ///Add a new edge to the graph.
1.469 -
1.470 - ///Add a new edge to the graph with tail node \c t
1.471 - ///and head node \c h.
1.472 - ///\return the new edge.
1.473 - Edge addEdge(Node h, Node t) { return INVALID; }
1.474 -
1.475 - /// Resets the graph.
1.476 -
1.477 - /// This function deletes all edges and nodes of the graph.
1.478 - /// It also frees the memory allocated to store them.
1.479 - /// \todo It might belong to \ref ErasableGraph.
1.480 - void clear() { }
1.481 - };
1.482 -
1.483 - /// An empty erasable graph class.
1.484 -
1.485 - /// This class is an extension of \ref ExtendableGraph. It also makes it
1.486 - /// possible to erase edges or nodes.
1.487 - class ErasableGraph : public ExtendableGraph
1.488 - {
1.489 - public:
1.490 - /// Defalult constructor.
1.491 -
1.492 - /// Defalult constructor.
1.493 - ///
1.494 - ErasableGraph() { }
1.495 - /// Deletes a node.
1.496 -
1.497 - /// Deletes node \c n node.
1.498 - ///
1.499 - void erase(Node n) { }
1.500 - /// Deletes an edge.
1.501 -
1.502 - /// Deletes edge \c e edge.
1.503 - ///
1.504 - void erase(Edge e) { }
1.505 - };
1.506 -
1.507 - // @}
1.508 - } //namespace skeleton
1.509 -} //namespace hugo
1.510 -
1.511 -
1.512 -
1.513 -#endif // HUGO_SKELETON_GRAPH_H