1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concepts/path.h Thu Jan 24 11:31:19 2008 +0000
1.3 @@ -0,0 +1,307 @@
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-2008
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 digraphs.
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/bits/utility.h>
1.33 +#include <lemon/concept_check.h>
1.34 +
1.35 +namespace lemon {
1.36 + namespace concepts {
1.37 +
1.38 + /// \addtogroup concept
1.39 + /// @{
1.40 +
1.41 + /// \brief A skeleton structure for representing directed paths in
1.42 + /// a digraph.
1.43 + ///
1.44 + /// A skeleton structure for representing directed paths in a
1.45 + /// digraph.
1.46 + /// \param _Digraph The digraph type in which the path is.
1.47 + ///
1.48 + /// In a sense, the path can be treated as a list of arcs. The
1.49 + /// lemon path type stores just this list. As a consequence it
1.50 + /// cannot enumerate the nodes in the path and the zero length
1.51 + /// paths cannot store the source.
1.52 + ///
1.53 + template <typename _Digraph>
1.54 + class Path {
1.55 + public:
1.56 +
1.57 + /// Type of the underlying digraph.
1.58 + typedef _Digraph Digraph;
1.59 + /// Arc type of the underlying digraph.
1.60 + typedef typename Digraph::Arc Arc;
1.61 +
1.62 + class ArcIt;
1.63 +
1.64 + /// \brief Default constructor
1.65 + Path() {}
1.66 +
1.67 + /// \brief Template constructor
1.68 + template <typename CPath>
1.69 + Path(const CPath& cpath) {}
1.70 +
1.71 + /// \brief Template assigment
1.72 + template <typename CPath>
1.73 + Path& operator=(const CPath& cpath) {}
1.74 +
1.75 + /// Length of the path ie. the number of arcs in the path.
1.76 + int length() const { return 0;}
1.77 +
1.78 + /// Returns whether the path is empty.
1.79 + bool empty() const { return true;}
1.80 +
1.81 + /// Resets the path to an empty path.
1.82 + void clear() {}
1.83 +
1.84 + /// \brief Lemon style iterator for path arcs
1.85 + ///
1.86 + /// This class is used to iterate on the arcs of the paths.
1.87 + class ArcIt {
1.88 + public:
1.89 + /// Default constructor
1.90 + ArcIt() {}
1.91 + /// Invalid constructor
1.92 + ArcIt(Invalid) {}
1.93 + /// Constructor for first arc
1.94 + ArcIt(const Path &) {}
1.95 +
1.96 + /// Conversion to Arc
1.97 + operator Arc() const { return INVALID; }
1.98 +
1.99 + /// Next arc
1.100 + ArcIt& operator++() {return *this;}
1.101 +
1.102 + /// Comparison operator
1.103 + bool operator==(const ArcIt&) const {return true;}
1.104 + /// Comparison operator
1.105 + bool operator!=(const ArcIt&) const {return true;}
1.106 + /// Comparison operator
1.107 + bool operator<(const ArcIt&) const {return false;}
1.108 +
1.109 + };
1.110 +
1.111 + template <typename _Path>
1.112 + struct Constraints {
1.113 + void constraints() {
1.114 + Path<Digraph> pc;
1.115 + _Path p, pp(pc);
1.116 + int l = p.length();
1.117 + int e = p.empty();
1.118 + p.clear();
1.119 +
1.120 + p = pc;
1.121 +
1.122 + typename _Path::ArcIt id, ii(INVALID), i(p);
1.123 +
1.124 + ++i;
1.125 + typename Digraph::Arc ed = i;
1.126 +
1.127 + e = (i == ii);
1.128 + e = (i != ii);
1.129 + e = (i < ii);
1.130 +
1.131 + ignore_unused_variable_warning(l);
1.132 + ignore_unused_variable_warning(pp);
1.133 + ignore_unused_variable_warning(e);
1.134 + ignore_unused_variable_warning(id);
1.135 + ignore_unused_variable_warning(ii);
1.136 + ignore_unused_variable_warning(ed);
1.137 + }
1.138 + };
1.139 +
1.140 + };
1.141 +
1.142 + namespace _path_bits {
1.143 +
1.144 + template <typename _Digraph, typename _Path, typename RevPathTag = void>
1.145 + struct PathDumperConstraints {
1.146 + void constraints() {
1.147 + int l = p.length();
1.148 + int e = p.empty();
1.149 +
1.150 + typename _Path::ArcIt id, i(p);
1.151 +
1.152 + ++i;
1.153 + typename _Digraph::Arc ed = i;
1.154 +
1.155 + e = (i == INVALID);
1.156 + e = (i != INVALID);
1.157 +
1.158 + ignore_unused_variable_warning(l);
1.159 + ignore_unused_variable_warning(e);
1.160 + ignore_unused_variable_warning(id);
1.161 + ignore_unused_variable_warning(ed);
1.162 + }
1.163 + _Path& p;
1.164 + };
1.165 +
1.166 + template <typename _Digraph, typename _Path>
1.167 + struct PathDumperConstraints<
1.168 + _Digraph, _Path,
1.169 + typename enable_if<typename _Path::RevPathTag, void>::type
1.170 + > {
1.171 + void constraints() {
1.172 + int l = p.length();
1.173 + int e = p.empty();
1.174 +
1.175 + typename _Path::RevArcIt id, i(p);
1.176 +
1.177 + ++i;
1.178 + typename _Digraph::Arc ed = i;
1.179 +
1.180 + e = (i == INVALID);
1.181 + e = (i != INVALID);
1.182 +
1.183 + ignore_unused_variable_warning(l);
1.184 + ignore_unused_variable_warning(e);
1.185 + ignore_unused_variable_warning(id);
1.186 + ignore_unused_variable_warning(ed);
1.187 + }
1.188 + _Path& p;
1.189 + };
1.190 +
1.191 + }
1.192 +
1.193 +
1.194 + /// \brief A skeleton structure for path dumpers.
1.195 + ///
1.196 + /// A skeleton structure for path dumpers. The path dumpers are
1.197 + /// the generalization of the paths. The path dumpers can
1.198 + /// enumerate the arcs of the path wheter in forward or in
1.199 + /// backward order. In most time these classes are not used
1.200 + /// directly rather it used to assign a dumped class to a real
1.201 + /// path type.
1.202 + ///
1.203 + /// The main purpose of this concept is that the shortest path
1.204 + /// algorithms can enumerate easily the arcs in reverse order.
1.205 + /// If we would like to give back a real path from these
1.206 + /// algorithms then we should create a temporarly path object. In
1.207 + /// Lemon such algorithms gives back a path dumper what can
1.208 + /// assigned to a real path and the dumpers can be implemented as
1.209 + /// an adaptor class to the predecessor map.
1.210 +
1.211 + /// \param _Digraph The digraph type in which the path is.
1.212 + ///
1.213 + /// The paths can be constructed from any path type by a
1.214 + /// template constructor or a template assignment operator.
1.215 + ///
1.216 + template <typename _Digraph>
1.217 + class PathDumper {
1.218 + public:
1.219 +
1.220 + /// Type of the underlying digraph.
1.221 + typedef _Digraph Digraph;
1.222 + /// Arc type of the underlying digraph.
1.223 + typedef typename Digraph::Arc Arc;
1.224 +
1.225 + /// Length of the path ie. the number of arcs in the path.
1.226 + int length() const { return 0;}
1.227 +
1.228 + /// Returns whether the path is empty.
1.229 + bool empty() const { return true;}
1.230 +
1.231 + /// \brief Forward or reverse dumping
1.232 + ///
1.233 + /// If the RevPathTag is defined and true then reverse dumping
1.234 + /// is provided in the path dumper. In this case instead of the
1.235 + /// ArcIt the RevArcIt iterator should be implemented in the
1.236 + /// dumper.
1.237 + typedef False RevPathTag;
1.238 +
1.239 + /// \brief Lemon style iterator for path arcs
1.240 + ///
1.241 + /// This class is used to iterate on the arcs of the paths.
1.242 + class ArcIt {
1.243 + public:
1.244 + /// Default constructor
1.245 + ArcIt() {}
1.246 + /// Invalid constructor
1.247 + ArcIt(Invalid) {}
1.248 + /// Constructor for first arc
1.249 + ArcIt(const PathDumper&) {}
1.250 +
1.251 + /// Conversion to Arc
1.252 + operator Arc() const { return INVALID; }
1.253 +
1.254 + /// Next arc
1.255 + ArcIt& operator++() {return *this;}
1.256 +
1.257 + /// Comparison operator
1.258 + bool operator==(const ArcIt&) const {return true;}
1.259 + /// Comparison operator
1.260 + bool operator!=(const ArcIt&) const {return true;}
1.261 + /// Comparison operator
1.262 + bool operator<(const ArcIt&) const {return false;}
1.263 +
1.264 + };
1.265 +
1.266 + /// \brief Lemon style iterator for path arcs
1.267 + ///
1.268 + /// This class is used to iterate on the arcs of the paths in
1.269 + /// reverse direction.
1.270 + class RevArcIt {
1.271 + public:
1.272 + /// Default constructor
1.273 + RevArcIt() {}
1.274 + /// Invalid constructor
1.275 + RevArcIt(Invalid) {}
1.276 + /// Constructor for first arc
1.277 + RevArcIt(const PathDumper &) {}
1.278 +
1.279 + /// Conversion to Arc
1.280 + operator Arc() const { return INVALID; }
1.281 +
1.282 + /// Next arc
1.283 + RevArcIt& operator++() {return *this;}
1.284 +
1.285 + /// Comparison operator
1.286 + bool operator==(const RevArcIt&) const {return true;}
1.287 + /// Comparison operator
1.288 + bool operator!=(const RevArcIt&) const {return true;}
1.289 + /// Comparison operator
1.290 + bool operator<(const RevArcIt&) const {return false;}
1.291 +
1.292 + };
1.293 +
1.294 + template <typename _Path>
1.295 + struct Constraints {
1.296 + void constraints() {
1.297 + function_requires<_path_bits::
1.298 + PathDumperConstraints<Digraph, _Path> >();
1.299 + }
1.300 + };
1.301 +
1.302 + };
1.303 +
1.304 +
1.305 + ///@}
1.306 + }
1.307 +
1.308 +} // namespace lemon
1.309 +
1.310 +#endif // LEMON_CONCEPT_PATH_H