1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concepts/path.h Tue Oct 24 17:19:16 2006 +0000
1.3 @@ -0,0 +1,294 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +///\ingroup concept
1.23 +///\file
1.24 +///\brief Classes for representing paths in graphs.
1.25 +///
1.26 +///\todo Iterators have obsolete style
1.27 +
1.28 +#ifndef LEMON_CONCEPT_PATH_H
1.29 +#define LEMON_CONCEPT_PATH_H
1.30 +
1.31 +#include <lemon/bits/invalid.h>
1.32 +#include <lemon/concept_check.h>
1.33 +
1.34 +namespace lemon {
1.35 + namespace concepts {
1.36 + /// \addtogroup concept
1.37 + /// @{
1.38 +
1.39 +
1.40 + //! \brief A skeleton structure for representing directed paths in a graph.
1.41 + //!
1.42 + //! A skeleton structure for representing directed paths in a graph.
1.43 + //! \param _Graph The graph type in which the path is.
1.44 + //!
1.45 + //! In a sense, the path can be treated as a graph, for it has \c NodeIt
1.46 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.47 + //! and \c Edge of the original graph.
1.48 + template<typename _Graph>
1.49 + class Path {
1.50 + public:
1.51 +
1.52 + /// Type of the underlying graph.
1.53 + typedef _Graph Graph;
1.54 + /// Edge type of the underlying graph.
1.55 + typedef typename Graph::Edge Edge;
1.56 + /// Node type of the underlying graph.
1.57 + typedef typename Graph::Node Node;
1.58 +
1.59 + class NodeIt;
1.60 + class EdgeIt;
1.61 +
1.62 + /// \param _g The graph in which the path is.
1.63 + ///
1.64 + Path(const Graph &_g) {
1.65 + ignore_unused_variable_warning(_g);
1.66 + }
1.67 +
1.68 + /// Length of the path ie. the number of edges in the path.
1.69 + int length() const {return 0;}
1.70 +
1.71 + /// Returns whether the path is empty.
1.72 + bool empty() const { return true;}
1.73 +
1.74 + /// Resets the path to an empty path.
1.75 + void clear() {}
1.76 +
1.77 + /// \brief Starting point of the path.
1.78 + ///
1.79 + /// Starting point of the path.
1.80 + /// Returns INVALID if the path is empty.
1.81 + Node target() const {return INVALID;}
1.82 + /// \brief End point of the path.
1.83 + ///
1.84 + /// End point of the path.
1.85 + /// Returns INVALID if the path is empty.
1.86 + Node source() const {return INVALID;}
1.87 +
1.88 + /// \brief The target of an edge.
1.89 + ///
1.90 + /// Returns node iterator pointing to the target node of the
1.91 + /// given edge iterator.
1.92 + NodeIt target(const EdgeIt&) const {return INVALID;}
1.93 +
1.94 + /// \brief The source of an edge.
1.95 + ///
1.96 + /// Returns node iterator pointing to the source node of the
1.97 + /// given edge iterator.
1.98 + NodeIt source(const EdgeIt&) const {return INVALID;}
1.99 +
1.100 + /// \brief Iterator class to iterate on the nodes of the paths
1.101 + ///
1.102 + /// This class is used to iterate on the nodes of the paths
1.103 + ///
1.104 + /// Of course it converts to Graph::Node.
1.105 + class NodeIt {
1.106 + public:
1.107 + /// Default constructor
1.108 + NodeIt() {}
1.109 + /// Invalid constructor
1.110 + NodeIt(Invalid) {}
1.111 + /// Constructor with starting point
1.112 + NodeIt(const Path &) {}
1.113 +
1.114 + ///Conversion to Graph::Node
1.115 + operator Node() const { return INVALID; }
1.116 + /// Next node
1.117 + NodeIt& operator++() {return *this;}
1.118 +
1.119 + /// Comparison operator
1.120 + bool operator==(const NodeIt&) const {return true;}
1.121 + /// Comparison operator
1.122 + bool operator!=(const NodeIt&) const {return true;}
1.123 + /// Comparison operator
1.124 + bool operator<(const NodeIt&) const {return false;}
1.125 +
1.126 + };
1.127 +
1.128 + /// \brief Iterator class to iterate on the edges of the paths
1.129 + ///
1.130 + /// This class is used to iterate on the edges of the paths
1.131 + ///
1.132 + /// Of course it converts to Graph::Edge
1.133 + class EdgeIt {
1.134 + public:
1.135 + /// Default constructor
1.136 + EdgeIt() {}
1.137 + /// Invalid constructor
1.138 + EdgeIt(Invalid) {}
1.139 + /// Constructor with starting point
1.140 + EdgeIt(const Path &) {}
1.141 +
1.142 + operator Edge() const { return INVALID; }
1.143 +
1.144 + /// Next edge
1.145 + EdgeIt& operator++() {return *this;}
1.146 +
1.147 + /// Comparison operator
1.148 + bool operator==(const EdgeIt&) const {return true;}
1.149 + /// Comparison operator
1.150 + bool operator!=(const EdgeIt&) const {return true;}
1.151 + /// Comparison operator
1.152 + bool operator<(const EdgeIt&) const {return false;}
1.153 +
1.154 + };
1.155 +
1.156 +
1.157 + friend class Builder;
1.158 +
1.159 + /// \brief Class to build paths
1.160 + ///
1.161 + /// This class is used to fill a path with edges.
1.162 + ///
1.163 + /// You can push new edges to the front and to the back of the path in
1.164 + /// arbitrary order then you should commit these changes to the graph.
1.165 + ///
1.166 + /// While the builder is active (after the first modifying
1.167 + /// operation and until the call of \ref commit()) the
1.168 + /// underlining Path is in a "transitional" state (operations on
1.169 + /// it have undefined result).
1.170 + class Builder {
1.171 + public:
1.172 +
1.173 + /// Constructor
1.174 +
1.175 + /// Constructor
1.176 + /// \param _path the path you want to fill in.
1.177 + ///
1.178 +
1.179 + Builder(Path &_path) { ignore_unused_variable_warning(_path); }
1.180 +
1.181 + /// Sets the starting node of the path.
1.182 +
1.183 + /// Sets the starting node of the path. Edge added to the path
1.184 + /// afterwards have to be incident to this node.
1.185 + /// You \em must start building an empty path with these functions.
1.186 + /// (And you \em must \em not use it later).
1.187 + /// \sa pushFront()
1.188 + /// \sa pushBack()
1.189 + void setStartNode(const Node &) {}
1.190 +
1.191 + ///Push a new edge to the front of the path
1.192 +
1.193 + ///Push a new edge to the front of the path.
1.194 + ///If the path is empty, you \em must call \ref setStartNode() before
1.195 + ///the first use of \ref pushFront().
1.196 + void pushFront(const Edge&) {}
1.197 +
1.198 + ///Push a new edge to the back of the path
1.199 +
1.200 + ///Push a new edge to the back of the path.
1.201 + ///If the path is empty, you \em must call \ref setStartNode() before
1.202 + ///the first use of \ref pushBack().
1.203 + void pushBack(const Edge&) {}
1.204 +
1.205 + ///Commit the changes to the path.
1.206 +
1.207 + ///Commit the changes to the path.
1.208 + ///
1.209 + void commit() {}
1.210 +
1.211 + ///Reserve (front) storage for the builder in advance.
1.212 +
1.213 + ///If you know a reasonable upper bound on the number of the edges
1.214 + ///to add to the front of the path,
1.215 + ///using this function you may speed up the building.
1.216 + void reserveFront(size_t) {}
1.217 + ///Reserve (back) storage for the builder in advance.
1.218 +
1.219 + ///If you know a reasonable upper bound on the number of the edges
1.220 + ///to add to the back of the path,
1.221 + ///using this function you may speed up the building.
1.222 + void reserveBack(size_t) {}
1.223 + };
1.224 +
1.225 + template <typename _Path>
1.226 + struct Constraints {
1.227 + void constraints() {
1.228 + typedef typename _Path::Node Node;
1.229 + typedef typename _Path::NodeIt NodeIt;
1.230 + typedef typename Graph::Node GraphNode;
1.231 +
1.232 + typedef typename _Path::Edge Edge;
1.233 + typedef typename _Path::EdgeIt EdgeIt;
1.234 + typedef typename Graph::Edge GraphEdge;
1.235 +
1.236 + typedef typename _Path::Builder Builder;
1.237 +
1.238 + path = _Path(graph);
1.239 +
1.240 + bool b = cpath.empty();
1.241 + int l = cpath.length();
1.242 +
1.243 + Node gn;
1.244 + Edge ge;
1.245 + gn = cpath.source();
1.246 + gn = cpath.target();
1.247 +
1.248 + NodeIt nit;
1.249 + EdgeIt eit(INVALID);
1.250 + nit = path.source(eit);
1.251 + nit = path.target(eit);
1.252 +
1.253 + nit = NodeIt();
1.254 + nit = NodeIt(cpath);
1.255 + nit = INVALID;
1.256 + gn = nit;
1.257 + ++nit;
1.258 + b = nit == nit;
1.259 + b = nit != nit;
1.260 + b = nit < nit;
1.261 +
1.262 + eit = EdgeIt();
1.263 + eit = EdgeIt(cpath);
1.264 + eit = INVALID;
1.265 + ge = eit;
1.266 + ++eit;
1.267 + b = eit == eit;
1.268 + b = eit != eit;
1.269 + b = eit < eit;
1.270 +
1.271 + size_t st = 0;
1.272 +
1.273 + Builder builder(path);
1.274 + builder.setStartNode(gn);
1.275 + builder.pushFront(ge);
1.276 + builder.pushBack(ge);
1.277 + builder.commit();
1.278 + builder.reserveFront(st);
1.279 + builder.reserveBack(st);
1.280 +
1.281 + ignore_unused_variable_warning(l);
1.282 + ignore_unused_variable_warning(b);
1.283 + }
1.284 +
1.285 + const Graph& graph;
1.286 + const _Path& cpath;
1.287 + _Path& path;
1.288 + };
1.289 +
1.290 + };
1.291 +
1.292 + ///@}
1.293 + }
1.294 +
1.295 +} // namespace lemon
1.296 +
1.297 +#endif // LEMON_CONCEPT_PATH_H