1.1 --- a/lemon/concepts/path.h Fri Jan 05 10:59:18 2007 +0000
1.2 +++ b/lemon/concepts/path.h Mon Jan 08 10:39:59 2007 +0000
1.3 @@ -26,23 +26,28 @@
1.4 #define LEMON_CONCEPT_PATH_H
1.5
1.6 #include <lemon/bits/invalid.h>
1.7 +#include <lemon/bits/utility.h>
1.8 #include <lemon/concept_check.h>
1.9
1.10 namespace lemon {
1.11 namespace concepts {
1.12 +
1.13 /// \addtogroup concept
1.14 /// @{
1.15
1.16 -
1.17 - //! \brief A skeleton structure for representing directed paths in a graph.
1.18 - //!
1.19 - //! A skeleton structure for representing directed paths in a graph.
1.20 - //! \param _Graph The graph type in which the path is.
1.21 - //!
1.22 - //! In a sense, the path can be treated as a graph, for it has \c NodeIt
1.23 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.24 - //! and \c Edge of the original graph.
1.25 - template<typename _Graph>
1.26 + /// \brief A skeleton structure for representing directed paths in
1.27 + /// a graph.
1.28 + ///
1.29 + /// A skeleton structure for representing directed paths in a
1.30 + /// graph.
1.31 + /// \param _Graph The graph type in which the path is.
1.32 + ///
1.33 + /// In a sense, the path can be treated as a list of edges. The
1.34 + /// lemon path type stores just this list. As a consequence it
1.35 + /// cannot enumerate the nodes in the path and the zero length
1.36 + /// paths cannot store the source.
1.37 + ///
1.38 + template <typename _Graph>
1.39 class Path {
1.40 public:
1.41
1.42 @@ -50,20 +55,22 @@
1.43 typedef _Graph Graph;
1.44 /// Edge type of the underlying graph.
1.45 typedef typename Graph::Edge Edge;
1.46 - /// Node type of the underlying graph.
1.47 - typedef typename Graph::Node Node;
1.48
1.49 - class NodeIt;
1.50 class EdgeIt;
1.51
1.52 - /// \param _g The graph in which the path is.
1.53 - ///
1.54 - Path(const Graph &_g) {
1.55 - ignore_unused_variable_warning(_g);
1.56 - }
1.57 + /// \brief Default constructor
1.58 + Path() {}
1.59 +
1.60 + /// \brief Template constructor
1.61 + template <typename CPath>
1.62 + Path(const CPath& cpath) {}
1.63 +
1.64 + /// \brief Template assigment
1.65 + template <typename CPath>
1.66 + Path& operator=(const CPath& cpath) {}
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 + int length() const { return 0;}
1.71
1.72 /// Returns whether the path is empty.
1.73 bool empty() const { return true;}
1.74 @@ -71,71 +78,19 @@
1.75 /// Resets the path to an empty path.
1.76 void clear() {}
1.77
1.78 - /// \brief Starting point of the path.
1.79 + /// \brief Lemon style iterator for path edges
1.80 ///
1.81 - /// Starting point of the path.
1.82 - /// Returns INVALID if the path is empty.
1.83 - Node target() const {return INVALID;}
1.84 - /// \brief End point of the path.
1.85 - ///
1.86 - /// End point of the path.
1.87 - /// Returns INVALID if the path is empty.
1.88 - Node source() const {return INVALID;}
1.89 -
1.90 - /// \brief The target of an edge.
1.91 - ///
1.92 - /// Returns node iterator pointing to the target node of the
1.93 - /// given edge iterator.
1.94 - NodeIt target(const EdgeIt&) const {return INVALID;}
1.95 -
1.96 - /// \brief The source of an edge.
1.97 - ///
1.98 - /// Returns node iterator pointing to the source node of the
1.99 - /// given edge iterator.
1.100 - NodeIt source(const EdgeIt&) const {return INVALID;}
1.101 -
1.102 - /// \brief Iterator class to iterate on the nodes of the paths
1.103 - ///
1.104 - /// This class is used to iterate on the nodes of the paths
1.105 - ///
1.106 - /// Of course it converts to Graph::Node.
1.107 - class NodeIt {
1.108 - public:
1.109 - /// Default constructor
1.110 - NodeIt() {}
1.111 - /// Invalid constructor
1.112 - NodeIt(Invalid) {}
1.113 - /// Constructor with starting point
1.114 - NodeIt(const Path &) {}
1.115 -
1.116 - ///Conversion to Graph::Node
1.117 - operator Node() const { return INVALID; }
1.118 - /// Next node
1.119 - NodeIt& operator++() {return *this;}
1.120 -
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 true;}
1.125 - /// Comparison operator
1.126 - bool operator<(const NodeIt&) const {return false;}
1.127 -
1.128 - };
1.129 -
1.130 - /// \brief Iterator class to iterate on the edges of the paths
1.131 - ///
1.132 - /// This class is used to iterate on the edges of the paths
1.133 - ///
1.134 - /// Of course it converts to Graph::Edge
1.135 + /// This class is used to iterate on the edges of the paths.
1.136 class EdgeIt {
1.137 public:
1.138 /// Default constructor
1.139 EdgeIt() {}
1.140 /// Invalid constructor
1.141 EdgeIt(Invalid) {}
1.142 - /// Constructor with starting point
1.143 + /// Constructor for first edge
1.144 EdgeIt(const Path &) {}
1.145
1.146 + /// Conversion to Edge
1.147 operator Edge() const { return INVALID; }
1.148
1.149 /// Next edge
1.150 @@ -150,143 +105,205 @@
1.151
1.152 };
1.153
1.154 + template <typename _Path>
1.155 + struct Constraints {
1.156 + void constraints() {
1.157 + Path<Graph> pc;
1.158 + _Path p, pp(pc);
1.159 + int l = p.length();
1.160 + int e = p.empty();
1.161 + p.clear();
1.162
1.163 - friend class Builder;
1.164 + p = pc;
1.165
1.166 - /// \brief Class to build paths
1.167 + typename _Path::EdgeIt id, ii(INVALID), i(p);
1.168 +
1.169 + ++i;
1.170 + typename Graph::Edge ed = i;
1.171 +
1.172 + e = (i == ii);
1.173 + e = (i != ii);
1.174 + e = (i < ii);
1.175 +
1.176 + ignore_unused_variable_warning(l);
1.177 + ignore_unused_variable_warning(pp);
1.178 + ignore_unused_variable_warning(e);
1.179 + ignore_unused_variable_warning(id);
1.180 + ignore_unused_variable_warning(ii);
1.181 + ignore_unused_variable_warning(ed);
1.182 + }
1.183 + };
1.184 +
1.185 + };
1.186 +
1.187 + namespace _path_bits {
1.188 +
1.189 + template <typename _Graph, typename _Path, typename RevPathTag = void>
1.190 + struct PathDumperConstraints {
1.191 + void constraints() {
1.192 + int l = p.length();
1.193 + int e = p.empty();
1.194 +
1.195 + typename _Path::EdgeIt id, ii(INVALID), i(p);
1.196 +
1.197 + ++i;
1.198 + typename _Graph::Edge ed = i;
1.199 +
1.200 + e = (i == ii);
1.201 + e = (i != ii);
1.202 + e = (i < ii);
1.203 +
1.204 + ignore_unused_variable_warning(l);
1.205 + ignore_unused_variable_warning(e);
1.206 + ignore_unused_variable_warning(id);
1.207 + ignore_unused_variable_warning(ii);
1.208 + ignore_unused_variable_warning(ed);
1.209 + }
1.210 + _Path& p;
1.211 + };
1.212 +
1.213 + template <typename _Graph, typename _Path>
1.214 + struct PathDumperConstraints<
1.215 + _Graph, _Path,
1.216 + typename enable_if<typename _Path::RevPathTag, void>::type
1.217 + > {
1.218 + void constraints() {
1.219 + int l = p.length();
1.220 + int e = p.empty();
1.221 +
1.222 + typename _Path::RevIt id, ii(INVALID), i(p);
1.223 +
1.224 + ++i;
1.225 + typename _Graph::Edge ed = i;
1.226 +
1.227 + e = (i == ii);
1.228 + e = (i != ii);
1.229 + e = (i < ii);
1.230 +
1.231 + ignore_unused_variable_warning(l);
1.232 + ignore_unused_variable_warning(e);
1.233 + ignore_unused_variable_warning(id);
1.234 + ignore_unused_variable_warning(ii);
1.235 + ignore_unused_variable_warning(ed);
1.236 + }
1.237 + _Path& p;
1.238 + };
1.239 +
1.240 + }
1.241 +
1.242 +
1.243 + /// \brief A skeleton structure for path dumpers.
1.244 + ///
1.245 + /// A skeleton structure for path dumpers. The path dumpers are
1.246 + /// the generalization of the paths. The path dumpers can
1.247 + /// enumerate the edges of the path wheter in forward or in
1.248 + /// backward order. In most time these classes are not used
1.249 + /// directly rather it used to assign a dumped class to a real
1.250 + /// path type.
1.251 + ///
1.252 + /// The main purpose of this concept is that the shortest path
1.253 + /// algorithms can enumerate easily the edges in reverse order.
1.254 + /// If we would like to give back a real path from these
1.255 + /// algorithms then we should create a temporarly path object. In
1.256 + /// Lemon such algorithms gives back a path dumper what can
1.257 + /// assigned to a real path and the dumpers can be implemented as
1.258 + /// an adaptor class to the predecessor map.
1.259 +
1.260 + /// \param _Graph The graph type in which the path is.
1.261 + ///
1.262 + /// The paths can be constructed from any path type by a
1.263 + /// template constructor or a template assignment operator.
1.264 + ///
1.265 + template <typename _Graph>
1.266 + class PathDumper {
1.267 + public:
1.268 +
1.269 + /// Type of the underlying graph.
1.270 + typedef _Graph Graph;
1.271 + /// Edge type of the underlying graph.
1.272 + typedef typename Graph::Edge Edge;
1.273 +
1.274 + /// Length of the path ie. the number of edges in the path.
1.275 + int length() const { return 0;}
1.276 +
1.277 + /// Returns whether the path is empty.
1.278 + bool empty() const { return true;}
1.279 +
1.280 + /// \brief Forward or reverse dumping
1.281 ///
1.282 - /// This class is used to fill a path with edges.
1.283 + /// If the RevPathTag is defined and true then reverse dumping
1.284 + /// is provided in the path proxy. In this case instead of the
1.285 + /// EdgeIt the RevIt iterator should be implemented in the
1.286 + /// proxy.
1.287 + typedef False RevPathTag;
1.288 +
1.289 + /// \brief Lemon style iterator for path edges
1.290 ///
1.291 - /// You can push new edges to the front and to the back of the path in
1.292 - /// arbitrary order then you should commit these changes to the graph.
1.293 + /// This class is used to iterate on the edges of the paths.
1.294 + class EdgeIt {
1.295 + public:
1.296 + /// Default constructor
1.297 + EdgeIt() {}
1.298 + /// Invalid constructor
1.299 + EdgeIt(Invalid) {}
1.300 + /// Constructor for first edge
1.301 + EdgeIt(const PathDumper&) {}
1.302 +
1.303 + /// Conversion to Edge
1.304 + operator Edge() const { return INVALID; }
1.305 +
1.306 + /// Next edge
1.307 + EdgeIt& operator++() {return *this;}
1.308 +
1.309 + /// Comparison operator
1.310 + bool operator==(const EdgeIt&) const {return true;}
1.311 + /// Comparison operator
1.312 + bool operator!=(const EdgeIt&) const {return true;}
1.313 + /// Comparison operator
1.314 + bool operator<(const EdgeIt&) const {return false;}
1.315 +
1.316 + };
1.317 +
1.318 + /// \brief Lemon style iterator for path edges
1.319 ///
1.320 - /// While the builder is active (after the first modifying
1.321 - /// operation and until the call of \ref commit()) the
1.322 - /// underlining Path is in a "transitional" state (operations on
1.323 - /// it have undefined result).
1.324 - class Builder {
1.325 + /// This class is used to iterate on the edges of the paths in
1.326 + /// reverse direction.
1.327 + class RevIt {
1.328 public:
1.329 + /// Default constructor
1.330 + RevIt() {}
1.331 + /// Invalid constructor
1.332 + RevIt(Invalid) {}
1.333 + /// Constructor for first edge
1.334 + RevIt(const PathDumper &) {}
1.335
1.336 - /// Constructor
1.337 + /// Conversion to Edge
1.338 + operator Edge() const { return INVALID; }
1.339
1.340 - /// Constructor
1.341 - /// \param _path the path you want to fill in.
1.342 - ///
1.343 + /// Next edge
1.344 + RevIt& operator++() {return *this;}
1.345
1.346 - Builder(Path &_path) { ignore_unused_variable_warning(_path); }
1.347 + /// Comparison operator
1.348 + bool operator==(const RevIt&) const {return true;}
1.349 + /// Comparison operator
1.350 + bool operator!=(const RevIt&) const {return true;}
1.351 + /// Comparison operator
1.352 + bool operator<(const RevIt&) const {return false;}
1.353
1.354 - /// Sets the starting node of the path.
1.355 -
1.356 - /// Sets the starting node of the path. Edge added to the path
1.357 - /// afterwards have to be incident to this node.
1.358 - /// You \em must start building an empty path with these functions.
1.359 - /// (And you \em must \em not use it later).
1.360 - /// \sa pushFront()
1.361 - /// \sa pushBack()
1.362 - void setStartNode(const Node &) {}
1.363 -
1.364 - ///Push a new edge to the front of the path
1.365 -
1.366 - ///Push a new edge to the front of the path.
1.367 - ///If the path is empty, you \em must call \ref setStartNode() before
1.368 - ///the first use of \ref pushFront().
1.369 - void pushFront(const Edge&) {}
1.370 -
1.371 - ///Push a new edge to the back of the path
1.372 -
1.373 - ///Push a new edge to the back of the path.
1.374 - ///If the path is empty, you \em must call \ref setStartNode() before
1.375 - ///the first use of \ref pushBack().
1.376 - void pushBack(const Edge&) {}
1.377 -
1.378 - ///Commit the changes to the path.
1.379 -
1.380 - ///Commit the changes to the path.
1.381 - ///
1.382 - void commit() {}
1.383 -
1.384 - ///Reserve (front) storage for the builder in advance.
1.385 -
1.386 - ///If you know a reasonable upper bound on the number of the edges
1.387 - ///to add to the front of the path,
1.388 - ///using this function you may speed up the building.
1.389 - void reserveFront(size_t) {}
1.390 - ///Reserve (back) storage for the builder in advance.
1.391 -
1.392 - ///If you know a reasonable upper bound on the number of the edges
1.393 - ///to add to the back of the path,
1.394 - ///using this function you may speed up the building.
1.395 - void reserveBack(size_t) {}
1.396 };
1.397
1.398 template <typename _Path>
1.399 struct Constraints {
1.400 - void constraints() {
1.401 - typedef typename _Path::Node Node;
1.402 - typedef typename _Path::NodeIt NodeIt;
1.403 - typedef typename Graph::Node GraphNode;
1.404 -
1.405 - typedef typename _Path::Edge Edge;
1.406 - typedef typename _Path::EdgeIt EdgeIt;
1.407 - typedef typename Graph::Edge GraphEdge;
1.408 -
1.409 - typedef typename _Path::Builder Builder;
1.410 -
1.411 - path = _Path(graph);
1.412 -
1.413 - bool b = cpath.empty();
1.414 - int l = cpath.length();
1.415 -
1.416 - Node gn;
1.417 - Edge ge;
1.418 - gn = cpath.source();
1.419 - gn = cpath.target();
1.420 -
1.421 - NodeIt nit;
1.422 - EdgeIt eit(INVALID);
1.423 - nit = path.source(eit);
1.424 - nit = path.target(eit);
1.425 -
1.426 - nit = NodeIt();
1.427 - nit = NodeIt(cpath);
1.428 - nit = INVALID;
1.429 - gn = nit;
1.430 - ++nit;
1.431 - b = nit == nit;
1.432 - b = nit != nit;
1.433 - b = nit < nit;
1.434 -
1.435 - eit = EdgeIt();
1.436 - eit = EdgeIt(cpath);
1.437 - eit = INVALID;
1.438 - ge = eit;
1.439 - ++eit;
1.440 - b = eit == eit;
1.441 - b = eit != eit;
1.442 - b = eit < eit;
1.443 -
1.444 - size_t st = 0;
1.445 -
1.446 - Builder builder(path);
1.447 - builder.setStartNode(gn);
1.448 - builder.pushFront(ge);
1.449 - builder.pushBack(ge);
1.450 - builder.commit();
1.451 - builder.reserveFront(st);
1.452 - builder.reserveBack(st);
1.453 -
1.454 - ignore_unused_variable_warning(l);
1.455 - ignore_unused_variable_warning(b);
1.456 - }
1.457 -
1.458 - const Graph& graph;
1.459 - const _Path& cpath;
1.460 - _Path& path;
1.461 + void constraints() {
1.462 + function_requires<_path_bits::
1.463 + PathDumperConstraints<Graph, _Path> >();
1.464 + }
1.465 };
1.466
1.467 };
1.468
1.469 - ///@}
1.470 +
1.471 + ///@}
1.472 }
1.473
1.474 } // namespace lemon