1.1 --- a/lemon/Makefile.am Wed Jan 23 16:26:41 2008 +0100
1.2 +++ b/lemon/Makefile.am Thu Jan 24 11:31:19 2008 +0000
1.3 @@ -17,6 +17,8 @@
1.4 lemon_HEADERS += \
1.5 lemon/dim2.h \
1.6 lemon/maps.h \
1.7 + lemon/path.h \
1.8 + lemon/path_utils.h \
1.9 lemon/random.h \
1.10 lemon/list_graph.h \
1.11 lemon/tolerance.h
1.12 @@ -38,4 +40,5 @@
1.13 lemon/concepts/digraph.h \
1.14 lemon/concepts/graph.h \
1.15 lemon/concepts/maps.h \
1.16 + lemon/concepts/path.h \
1.17 lemon/concepts/graph_components.h
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/concepts/path.h Thu Jan 24 11:31:19 2008 +0000
2.3 @@ -0,0 +1,307 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +///\ingroup concept
2.23 +///\file
2.24 +///\brief Classes for representing paths in digraphs.
2.25 +///
2.26 +///\todo Iterators have obsolete style
2.27 +
2.28 +#ifndef LEMON_CONCEPT_PATH_H
2.29 +#define LEMON_CONCEPT_PATH_H
2.30 +
2.31 +#include <lemon/bits/invalid.h>
2.32 +#include <lemon/bits/utility.h>
2.33 +#include <lemon/concept_check.h>
2.34 +
2.35 +namespace lemon {
2.36 + namespace concepts {
2.37 +
2.38 + /// \addtogroup concept
2.39 + /// @{
2.40 +
2.41 + /// \brief A skeleton structure for representing directed paths in
2.42 + /// a digraph.
2.43 + ///
2.44 + /// A skeleton structure for representing directed paths in a
2.45 + /// digraph.
2.46 + /// \param _Digraph The digraph type in which the path is.
2.47 + ///
2.48 + /// In a sense, the path can be treated as a list of arcs. The
2.49 + /// lemon path type stores just this list. As a consequence it
2.50 + /// cannot enumerate the nodes in the path and the zero length
2.51 + /// paths cannot store the source.
2.52 + ///
2.53 + template <typename _Digraph>
2.54 + class Path {
2.55 + public:
2.56 +
2.57 + /// Type of the underlying digraph.
2.58 + typedef _Digraph Digraph;
2.59 + /// Arc type of the underlying digraph.
2.60 + typedef typename Digraph::Arc Arc;
2.61 +
2.62 + class ArcIt;
2.63 +
2.64 + /// \brief Default constructor
2.65 + Path() {}
2.66 +
2.67 + /// \brief Template constructor
2.68 + template <typename CPath>
2.69 + Path(const CPath& cpath) {}
2.70 +
2.71 + /// \brief Template assigment
2.72 + template <typename CPath>
2.73 + Path& operator=(const CPath& cpath) {}
2.74 +
2.75 + /// Length of the path ie. the number of arcs in the path.
2.76 + int length() const { return 0;}
2.77 +
2.78 + /// Returns whether the path is empty.
2.79 + bool empty() const { return true;}
2.80 +
2.81 + /// Resets the path to an empty path.
2.82 + void clear() {}
2.83 +
2.84 + /// \brief Lemon style iterator for path arcs
2.85 + ///
2.86 + /// This class is used to iterate on the arcs of the paths.
2.87 + class ArcIt {
2.88 + public:
2.89 + /// Default constructor
2.90 + ArcIt() {}
2.91 + /// Invalid constructor
2.92 + ArcIt(Invalid) {}
2.93 + /// Constructor for first arc
2.94 + ArcIt(const Path &) {}
2.95 +
2.96 + /// Conversion to Arc
2.97 + operator Arc() const { return INVALID; }
2.98 +
2.99 + /// Next arc
2.100 + ArcIt& operator++() {return *this;}
2.101 +
2.102 + /// Comparison operator
2.103 + bool operator==(const ArcIt&) const {return true;}
2.104 + /// Comparison operator
2.105 + bool operator!=(const ArcIt&) const {return true;}
2.106 + /// Comparison operator
2.107 + bool operator<(const ArcIt&) const {return false;}
2.108 +
2.109 + };
2.110 +
2.111 + template <typename _Path>
2.112 + struct Constraints {
2.113 + void constraints() {
2.114 + Path<Digraph> pc;
2.115 + _Path p, pp(pc);
2.116 + int l = p.length();
2.117 + int e = p.empty();
2.118 + p.clear();
2.119 +
2.120 + p = pc;
2.121 +
2.122 + typename _Path::ArcIt id, ii(INVALID), i(p);
2.123 +
2.124 + ++i;
2.125 + typename Digraph::Arc ed = i;
2.126 +
2.127 + e = (i == ii);
2.128 + e = (i != ii);
2.129 + e = (i < ii);
2.130 +
2.131 + ignore_unused_variable_warning(l);
2.132 + ignore_unused_variable_warning(pp);
2.133 + ignore_unused_variable_warning(e);
2.134 + ignore_unused_variable_warning(id);
2.135 + ignore_unused_variable_warning(ii);
2.136 + ignore_unused_variable_warning(ed);
2.137 + }
2.138 + };
2.139 +
2.140 + };
2.141 +
2.142 + namespace _path_bits {
2.143 +
2.144 + template <typename _Digraph, typename _Path, typename RevPathTag = void>
2.145 + struct PathDumperConstraints {
2.146 + void constraints() {
2.147 + int l = p.length();
2.148 + int e = p.empty();
2.149 +
2.150 + typename _Path::ArcIt id, i(p);
2.151 +
2.152 + ++i;
2.153 + typename _Digraph::Arc ed = i;
2.154 +
2.155 + e = (i == INVALID);
2.156 + e = (i != INVALID);
2.157 +
2.158 + ignore_unused_variable_warning(l);
2.159 + ignore_unused_variable_warning(e);
2.160 + ignore_unused_variable_warning(id);
2.161 + ignore_unused_variable_warning(ed);
2.162 + }
2.163 + _Path& p;
2.164 + };
2.165 +
2.166 + template <typename _Digraph, typename _Path>
2.167 + struct PathDumperConstraints<
2.168 + _Digraph, _Path,
2.169 + typename enable_if<typename _Path::RevPathTag, void>::type
2.170 + > {
2.171 + void constraints() {
2.172 + int l = p.length();
2.173 + int e = p.empty();
2.174 +
2.175 + typename _Path::RevArcIt id, i(p);
2.176 +
2.177 + ++i;
2.178 + typename _Digraph::Arc ed = i;
2.179 +
2.180 + e = (i == INVALID);
2.181 + e = (i != INVALID);
2.182 +
2.183 + ignore_unused_variable_warning(l);
2.184 + ignore_unused_variable_warning(e);
2.185 + ignore_unused_variable_warning(id);
2.186 + ignore_unused_variable_warning(ed);
2.187 + }
2.188 + _Path& p;
2.189 + };
2.190 +
2.191 + }
2.192 +
2.193 +
2.194 + /// \brief A skeleton structure for path dumpers.
2.195 + ///
2.196 + /// A skeleton structure for path dumpers. The path dumpers are
2.197 + /// the generalization of the paths. The path dumpers can
2.198 + /// enumerate the arcs of the path wheter in forward or in
2.199 + /// backward order. In most time these classes are not used
2.200 + /// directly rather it used to assign a dumped class to a real
2.201 + /// path type.
2.202 + ///
2.203 + /// The main purpose of this concept is that the shortest path
2.204 + /// algorithms can enumerate easily the arcs in reverse order.
2.205 + /// If we would like to give back a real path from these
2.206 + /// algorithms then we should create a temporarly path object. In
2.207 + /// Lemon such algorithms gives back a path dumper what can
2.208 + /// assigned to a real path and the dumpers can be implemented as
2.209 + /// an adaptor class to the predecessor map.
2.210 +
2.211 + /// \param _Digraph The digraph type in which the path is.
2.212 + ///
2.213 + /// The paths can be constructed from any path type by a
2.214 + /// template constructor or a template assignment operator.
2.215 + ///
2.216 + template <typename _Digraph>
2.217 + class PathDumper {
2.218 + public:
2.219 +
2.220 + /// Type of the underlying digraph.
2.221 + typedef _Digraph Digraph;
2.222 + /// Arc type of the underlying digraph.
2.223 + typedef typename Digraph::Arc Arc;
2.224 +
2.225 + /// Length of the path ie. the number of arcs in the path.
2.226 + int length() const { return 0;}
2.227 +
2.228 + /// Returns whether the path is empty.
2.229 + bool empty() const { return true;}
2.230 +
2.231 + /// \brief Forward or reverse dumping
2.232 + ///
2.233 + /// If the RevPathTag is defined and true then reverse dumping
2.234 + /// is provided in the path dumper. In this case instead of the
2.235 + /// ArcIt the RevArcIt iterator should be implemented in the
2.236 + /// dumper.
2.237 + typedef False RevPathTag;
2.238 +
2.239 + /// \brief Lemon style iterator for path arcs
2.240 + ///
2.241 + /// This class is used to iterate on the arcs of the paths.
2.242 + class ArcIt {
2.243 + public:
2.244 + /// Default constructor
2.245 + ArcIt() {}
2.246 + /// Invalid constructor
2.247 + ArcIt(Invalid) {}
2.248 + /// Constructor for first arc
2.249 + ArcIt(const PathDumper&) {}
2.250 +
2.251 + /// Conversion to Arc
2.252 + operator Arc() const { return INVALID; }
2.253 +
2.254 + /// Next arc
2.255 + ArcIt& operator++() {return *this;}
2.256 +
2.257 + /// Comparison operator
2.258 + bool operator==(const ArcIt&) const {return true;}
2.259 + /// Comparison operator
2.260 + bool operator!=(const ArcIt&) const {return true;}
2.261 + /// Comparison operator
2.262 + bool operator<(const ArcIt&) const {return false;}
2.263 +
2.264 + };
2.265 +
2.266 + /// \brief Lemon style iterator for path arcs
2.267 + ///
2.268 + /// This class is used to iterate on the arcs of the paths in
2.269 + /// reverse direction.
2.270 + class RevArcIt {
2.271 + public:
2.272 + /// Default constructor
2.273 + RevArcIt() {}
2.274 + /// Invalid constructor
2.275 + RevArcIt(Invalid) {}
2.276 + /// Constructor for first arc
2.277 + RevArcIt(const PathDumper &) {}
2.278 +
2.279 + /// Conversion to Arc
2.280 + operator Arc() const { return INVALID; }
2.281 +
2.282 + /// Next arc
2.283 + RevArcIt& operator++() {return *this;}
2.284 +
2.285 + /// Comparison operator
2.286 + bool operator==(const RevArcIt&) const {return true;}
2.287 + /// Comparison operator
2.288 + bool operator!=(const RevArcIt&) const {return true;}
2.289 + /// Comparison operator
2.290 + bool operator<(const RevArcIt&) const {return false;}
2.291 +
2.292 + };
2.293 +
2.294 + template <typename _Path>
2.295 + struct Constraints {
2.296 + void constraints() {
2.297 + function_requires<_path_bits::
2.298 + PathDumperConstraints<Digraph, _Path> >();
2.299 + }
2.300 + };
2.301 +
2.302 + };
2.303 +
2.304 +
2.305 + ///@}
2.306 + }
2.307 +
2.308 +} // namespace lemon
2.309 +
2.310 +#endif // LEMON_CONCEPT_PATH_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/path.h Thu Jan 24 11:31:19 2008 +0000
3.3 @@ -0,0 +1,903 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2008
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +///\ingroup paths
3.23 +///\file
3.24 +///\brief Classes for representing paths in digraphs.
3.25 +///
3.26 +
3.27 +#ifndef LEMON_PATH_H
3.28 +#define LEMON_PATH_H
3.29 +
3.30 +#include <vector>
3.31 +#include <algorithm>
3.32 +
3.33 +#include <lemon/path_utils.h>
3.34 +#include <lemon/error.h>
3.35 +#include <lemon/bits/invalid.h>
3.36 +
3.37 +namespace lemon {
3.38 +
3.39 + /// \addtogroup paths
3.40 + /// @{
3.41 +
3.42 +
3.43 + /// \brief A structure for representing directed paths in a digraph.
3.44 + ///
3.45 + /// A structure for representing directed path in a digraph.
3.46 + /// \param Digraph The digraph type in which the path is.
3.47 + ///
3.48 + /// In a sense, the path can be treated as a list of arcs. The
3.49 + /// lemon path type stores just this list. As a consequence it
3.50 + /// cannot enumerate the nodes in the path and the zero length paths
3.51 + /// cannot store the source.
3.52 + ///
3.53 + /// This implementation is a back and front insertable and erasable
3.54 + /// path type. It can be indexed in O(1) time. The front and back
3.55 + /// insertion and erasure is amortized O(1) time. The
3.56 + /// impelementation is based on two opposite organized vectors.
3.57 + template <typename _Digraph>
3.58 + class Path {
3.59 + public:
3.60 +
3.61 + typedef _Digraph Digraph;
3.62 + typedef typename Digraph::Arc Arc;
3.63 +
3.64 + /// \brief Default constructor
3.65 + ///
3.66 + /// Default constructor
3.67 + Path() {}
3.68 +
3.69 + /// \brief Template copy constructor
3.70 + ///
3.71 + /// This path can be initialized with any other path type. It just
3.72 + /// makes a copy of the given path.
3.73 + template <typename CPath>
3.74 + Path(const CPath& cpath) {
3.75 + copyPath(*this, cpath);
3.76 + }
3.77 +
3.78 + /// \brief Template copy assignment
3.79 + ///
3.80 + /// This path can be initialized with any other path type. It just
3.81 + /// makes a copy of the given path.
3.82 + template <typename CPath>
3.83 + Path& operator=(const CPath& cpath) {
3.84 + copyPath(*this, cpath);
3.85 + return *this;
3.86 + }
3.87 +
3.88 + /// \brief Lemon style iterator for path arcs
3.89 + ///
3.90 + /// This class is used to iterate on the arcs of the paths.
3.91 + class ArcIt {
3.92 + friend class Path;
3.93 + public:
3.94 + /// \brief Default constructor
3.95 + ArcIt() {}
3.96 + /// \brief Invalid constructor
3.97 + ArcIt(Invalid) : path(0), idx(-1) {}
3.98 + /// \brief Initializate the constructor to the first arc of path
3.99 + ArcIt(const Path &_path)
3.100 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
3.101 +
3.102 + private:
3.103 +
3.104 + ArcIt(const Path &_path, int _idx)
3.105 + : path(&_path), idx(_idx) {}
3.106 +
3.107 + public:
3.108 +
3.109 + /// \brief Conversion to Arc
3.110 + operator const Arc&() const {
3.111 + return path->nth(idx);
3.112 + }
3.113 +
3.114 + /// \brief Next arc
3.115 + ArcIt& operator++() {
3.116 + ++idx;
3.117 + if (idx >= path->length()) idx = -1;
3.118 + return *this;
3.119 + }
3.120 +
3.121 + /// \brief Comparison operator
3.122 + bool operator==(const ArcIt& e) const { return idx==e.idx; }
3.123 + /// \brief Comparison operator
3.124 + bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
3.125 + /// \brief Comparison operator
3.126 + bool operator<(const ArcIt& e) const { return idx<e.idx; }
3.127 +
3.128 + private:
3.129 + const Path *path;
3.130 + int idx;
3.131 + };
3.132 +
3.133 + /// \brief Length of the path.
3.134 + int length() const { return head.size() + tail.size(); }
3.135 + /// \brief Returns whether the path is empty.
3.136 + bool empty() const { return head.empty() && tail.empty(); }
3.137 +
3.138 + /// \brief Resets the path to an empty path.
3.139 + void clear() { head.clear(); tail.clear(); }
3.140 +
3.141 + /// \brief Gives back the nth arc.
3.142 + ///
3.143 + /// \pre n is in the [0..length() - 1] range
3.144 + const Arc& nth(int n) const {
3.145 + return n < int(head.size()) ? *(head.rbegin() + n) :
3.146 + *(tail.begin() + (n - head.size()));
3.147 + }
3.148 +
3.149 + /// \brief Initializes arc iterator to point to the nth arc
3.150 + ///
3.151 + /// \pre n is in the [0..length() - 1] range
3.152 + ArcIt nthIt(int n) const {
3.153 + return ArcIt(*this, n);
3.154 + }
3.155 +
3.156 + /// \brief Gives back the first arc of the path
3.157 + const Arc& front() const {
3.158 + return head.empty() ? tail.front() : head.back();
3.159 + }
3.160 +
3.161 + /// \brief Add a new arc before the current path
3.162 + void addFront(const Arc& arc) {
3.163 + head.push_back(arc);
3.164 + }
3.165 +
3.166 + /// \brief Erase the first arc of the path
3.167 + void eraseFront() {
3.168 + if (!head.empty()) {
3.169 + head.pop_back();
3.170 + } else {
3.171 + head.clear();
3.172 + int halfsize = tail.size() / 2;
3.173 + head.resize(halfsize);
3.174 + std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
3.175 + head.rbegin());
3.176 + std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
3.177 + tail.resize(tail.size() - halfsize - 1);
3.178 + }
3.179 + }
3.180 +
3.181 + /// \brief Gives back the last arc of the path
3.182 + const Arc& back() const {
3.183 + return tail.empty() ? head.front() : tail.back();
3.184 + }
3.185 +
3.186 + /// \brief Add a new arc behind the current path
3.187 + void addBack(const Arc& arc) {
3.188 + tail.push_back(arc);
3.189 + }
3.190 +
3.191 + /// \brief Erase the last arc of the path
3.192 + void eraseBack() {
3.193 + if (!tail.empty()) {
3.194 + tail.pop_back();
3.195 + } else {
3.196 + int halfsize = head.size() / 2;
3.197 + tail.resize(halfsize);
3.198 + std::copy(head.begin() + 1, head.begin() + halfsize + 1,
3.199 + tail.rbegin());
3.200 + std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
3.201 + head.resize(head.size() - halfsize - 1);
3.202 + }
3.203 + }
3.204 +
3.205 +
3.206 +
3.207 + typedef True BuildTag;
3.208 +
3.209 + template <typename CPath>
3.210 + void build(const CPath& path) {
3.211 + int len = path.length();
3.212 + tail.reserve(len);
3.213 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
3.214 + tail.push_back(it);
3.215 + }
3.216 + }
3.217 +
3.218 + template <typename CPath>
3.219 + void buildRev(const CPath& path) {
3.220 + int len = path.length();
3.221 + head.reserve(len);
3.222 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
3.223 + head.push_back(it);
3.224 + }
3.225 + }
3.226 +
3.227 + protected:
3.228 + typedef std::vector<Arc> Container;
3.229 + Container head, tail;
3.230 +
3.231 + };
3.232 +
3.233 + /// \brief A structure for representing directed paths in a digraph.
3.234 + ///
3.235 + /// A structure for representing directed path in a digraph.
3.236 + /// \param Digraph The digraph type in which the path is.
3.237 + ///
3.238 + /// In a sense, the path can be treated as a list of arcs. The
3.239 + /// lemon path type stores just this list. As a consequence it
3.240 + /// cannot enumerate the nodes in the path and the zero length paths
3.241 + /// cannot store the source.
3.242 + ///
3.243 + /// This implementation is a just back insertable and erasable path
3.244 + /// type. It can be indexed in O(1) time. The back insertion and
3.245 + /// erasure is amortized O(1) time. This implementation is faster
3.246 + /// then the \c Path type because it use just one vector for the
3.247 + /// arcs.
3.248 + template <typename _Digraph>
3.249 + class SimplePath {
3.250 + public:
3.251 +
3.252 + typedef _Digraph Digraph;
3.253 + typedef typename Digraph::Arc Arc;
3.254 +
3.255 + /// \brief Default constructor
3.256 + ///
3.257 + /// Default constructor
3.258 + SimplePath() {}
3.259 +
3.260 + /// \brief Template copy constructor
3.261 + ///
3.262 + /// This path can be initialized with any other path type. It just
3.263 + /// makes a copy of the given path.
3.264 + template <typename CPath>
3.265 + SimplePath(const CPath& cpath) {
3.266 + copyPath(*this, cpath);
3.267 + }
3.268 +
3.269 + /// \brief Template copy assignment
3.270 + ///
3.271 + /// This path can be initialized with any other path type. It just
3.272 + /// makes a copy of the given path.
3.273 + template <typename CPath>
3.274 + SimplePath& operator=(const CPath& cpath) {
3.275 + copyPath(*this, cpath);
3.276 + return *this;
3.277 + }
3.278 +
3.279 + /// \brief Iterator class to iterate on the arcs of the paths
3.280 + ///
3.281 + /// This class is used to iterate on the arcs of the paths
3.282 + ///
3.283 + /// Of course it converts to Digraph::Arc
3.284 + class ArcIt {
3.285 + friend class SimplePath;
3.286 + public:
3.287 + /// Default constructor
3.288 + ArcIt() {}
3.289 + /// Invalid constructor
3.290 + ArcIt(Invalid) : path(0), idx(-1) {}
3.291 + /// \brief Initializate the constructor to the first arc of path
3.292 + ArcIt(const SimplePath &_path)
3.293 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
3.294 +
3.295 + private:
3.296 +
3.297 + /// Constructor with starting point
3.298 + ArcIt(const SimplePath &_path, int _idx)
3.299 + : idx(_idx), path(&_path) {}
3.300 +
3.301 + public:
3.302 +
3.303 + ///Conversion to Digraph::Arc
3.304 + operator const Arc&() const {
3.305 + return path->nth(idx);
3.306 + }
3.307 +
3.308 + /// Next arc
3.309 + ArcIt& operator++() {
3.310 + ++idx;
3.311 + if (idx >= path->length()) idx = -1;
3.312 + return *this;
3.313 + }
3.314 +
3.315 + /// Comparison operator
3.316 + bool operator==(const ArcIt& e) const { return idx==e.idx; }
3.317 + /// Comparison operator
3.318 + bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
3.319 + /// Comparison operator
3.320 + bool operator<(const ArcIt& e) const { return idx<e.idx; }
3.321 +
3.322 + private:
3.323 + const SimplePath *path;
3.324 + int idx;
3.325 + };
3.326 +
3.327 + /// \brief Length of the path.
3.328 + int length() const { return data.size(); }
3.329 + /// \brief Returns whether the path is empty.
3.330 + bool empty() const { return data.empty(); }
3.331 +
3.332 + /// \brief Resets the path to an empty path.
3.333 + void clear() { data.clear(); }
3.334 +
3.335 + /// \brief Gives back the nth arc.
3.336 + ///
3.337 + /// \pre n is in the [0..length() - 1] range
3.338 + const Arc& nth(int n) const {
3.339 + return data[n];
3.340 + }
3.341 +
3.342 + /// \brief Initializes arc iterator to point to the nth arc.
3.343 + ArcIt nthIt(int n) const {
3.344 + return ArcIt(*this, n);
3.345 + }
3.346 +
3.347 + /// \brief Gives back the first arc of the path.
3.348 + const Arc& front() const {
3.349 + return data.front();
3.350 + }
3.351 +
3.352 + /// \brief Gives back the last arc of the path.
3.353 + const Arc& back() const {
3.354 + return data.back();
3.355 + }
3.356 +
3.357 + /// \brief Add a new arc behind the current path.
3.358 + void addBack(const Arc& arc) {
3.359 + data.push_back(arc);
3.360 + }
3.361 +
3.362 + /// \brief Erase the last arc of the path
3.363 + void eraseBack() {
3.364 + data.pop_back();
3.365 + }
3.366 +
3.367 + typedef True BuildTag;
3.368 +
3.369 + template <typename CPath>
3.370 + void build(const CPath& path) {
3.371 + int len = path.length();
3.372 + data.resize(len);
3.373 + int index = 0;
3.374 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
3.375 + data[index] = it;;
3.376 + ++index;
3.377 + }
3.378 + }
3.379 +
3.380 + template <typename CPath>
3.381 + void buildRev(const CPath& path) {
3.382 + int len = path.length();
3.383 + data.resize(len);
3.384 + int index = len;
3.385 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
3.386 + --index;
3.387 + data[index] = it;;
3.388 + }
3.389 + }
3.390 +
3.391 + protected:
3.392 + typedef std::vector<Arc> Container;
3.393 + Container data;
3.394 +
3.395 + };
3.396 +
3.397 + /// \brief A structure for representing directed paths in a digraph.
3.398 + ///
3.399 + /// A structure for representing directed path in a digraph.
3.400 + /// \param Digraph The digraph type in which the path is.
3.401 + ///
3.402 + /// In a sense, the path can be treated as a list of arcs. The
3.403 + /// lemon path type stores just this list. As a consequence it
3.404 + /// cannot enumerate the nodes in the path and the zero length paths
3.405 + /// cannot store the source.
3.406 + ///
3.407 + /// This implementation is a back and front insertable and erasable
3.408 + /// path type. It can be indexed in O(k) time, where k is the rank
3.409 + /// of the arc in the path. The length can be computed in O(n)
3.410 + /// time. The front and back insertion and erasure is O(1) time
3.411 + /// and it can be splited and spliced in O(1) time.
3.412 + template <typename _Digraph>
3.413 + class ListPath {
3.414 + public:
3.415 +
3.416 + typedef _Digraph Digraph;
3.417 + typedef typename Digraph::Arc Arc;
3.418 +
3.419 + protected:
3.420 +
3.421 + // the std::list<> is incompatible
3.422 + // hard to create invalid iterator
3.423 + struct Node {
3.424 + Arc arc;
3.425 + Node *next, *prev;
3.426 + };
3.427 +
3.428 + Node *first, *last;
3.429 +
3.430 + std::allocator<Node> alloc;
3.431 +
3.432 + public:
3.433 +
3.434 + /// \brief Default constructor
3.435 + ///
3.436 + /// Default constructor
3.437 + ListPath() : first(0), last(0) {}
3.438 +
3.439 + /// \brief Template copy constructor
3.440 + ///
3.441 + /// This path can be initialized with any other path type. It just
3.442 + /// makes a copy of the given path.
3.443 + template <typename CPath>
3.444 + ListPath(const CPath& cpath) : first(0), last(0) {
3.445 + copyPath(*this, cpath);
3.446 + }
3.447 +
3.448 + /// \brief Destructor of the path
3.449 + ///
3.450 + /// Destructor of the path
3.451 + ~ListPath() {
3.452 + clear();
3.453 + }
3.454 +
3.455 + /// \brief Template copy assignment
3.456 + ///
3.457 + /// This path can be initialized with any other path type. It just
3.458 + /// makes a copy of the given path.
3.459 + template <typename CPath>
3.460 + ListPath& operator=(const CPath& cpath) {
3.461 + copyPath(*this, cpath);
3.462 + return *this;
3.463 + }
3.464 +
3.465 + /// \brief Iterator class to iterate on the arcs of the paths
3.466 + ///
3.467 + /// This class is used to iterate on the arcs of the paths
3.468 + ///
3.469 + /// Of course it converts to Digraph::Arc
3.470 + class ArcIt {
3.471 + friend class ListPath;
3.472 + public:
3.473 + /// Default constructor
3.474 + ArcIt() {}
3.475 + /// Invalid constructor
3.476 + ArcIt(Invalid) : path(0), node(0) {}
3.477 + /// \brief Initializate the constructor to the first arc of path
3.478 + ArcIt(const ListPath &_path)
3.479 + : path(&_path), node(_path.first) {}
3.480 +
3.481 + protected:
3.482 +
3.483 + ArcIt(const ListPath &_path, Node *_node)
3.484 + : path(&_path), node(_node) {}
3.485 +
3.486 +
3.487 + public:
3.488 +
3.489 + ///Conversion to Digraph::Arc
3.490 + operator const Arc&() const {
3.491 + return node->arc;
3.492 + }
3.493 +
3.494 + /// Next arc
3.495 + ArcIt& operator++() {
3.496 + node = node->next;
3.497 + return *this;
3.498 + }
3.499 +
3.500 + /// Comparison operator
3.501 + bool operator==(const ArcIt& e) const { return node==e.node; }
3.502 + /// Comparison operator
3.503 + bool operator!=(const ArcIt& e) const { return node!=e.node; }
3.504 + /// Comparison operator
3.505 + bool operator<(const ArcIt& e) const { return node<e.node; }
3.506 +
3.507 + private:
3.508 + const ListPath *path;
3.509 + Node *node;
3.510 + };
3.511 +
3.512 + /// \brief Gives back the nth arc.
3.513 + ///
3.514 + /// Gives back the nth arc in O(n) time.
3.515 + /// \pre n is in the [0..length() - 1] range
3.516 + const Arc& nth(int n) const {
3.517 + Node *node = first;
3.518 + for (int i = 0; i < n; ++i) {
3.519 + node = node->next;
3.520 + }
3.521 + return node->arc;
3.522 + }
3.523 +
3.524 + /// \brief Initializes arc iterator to point to the nth arc.
3.525 + ArcIt nthIt(int n) const {
3.526 + Node *node = first;
3.527 + for (int i = 0; i < n; ++i) {
3.528 + node = node->next;
3.529 + }
3.530 + return ArcIt(*this, node);
3.531 + }
3.532 +
3.533 + /// \brief Length of the path.
3.534 + int length() const {
3.535 + int len = 0;
3.536 + Node *node = first;
3.537 + while (node != 0) {
3.538 + node = node->next;
3.539 + ++len;
3.540 + }
3.541 + return len;
3.542 + }
3.543 +
3.544 + /// \brief Returns whether the path is empty.
3.545 + bool empty() const { return first == 0; }
3.546 +
3.547 + /// \brief Resets the path to an empty path.
3.548 + void clear() {
3.549 + while (first != 0) {
3.550 + last = first->next;
3.551 + alloc.destroy(first);
3.552 + alloc.deallocate(first, 1);
3.553 + first = last;
3.554 + }
3.555 + }
3.556 +
3.557 + /// \brief Gives back the first arc of the path
3.558 + const Arc& front() const {
3.559 + return first->arc;
3.560 + }
3.561 +
3.562 + /// \brief Add a new arc before the current path
3.563 + void addFront(const Arc& arc) {
3.564 + Node *node = alloc.allocate(1);
3.565 + alloc.construct(node, Node());
3.566 + node->prev = 0;
3.567 + node->next = first;
3.568 + node->arc = arc;
3.569 + if (first) {
3.570 + first->prev = node;
3.571 + first = node;
3.572 + } else {
3.573 + first = last = node;
3.574 + }
3.575 + }
3.576 +
3.577 + /// \brief Erase the first arc of the path
3.578 + void eraseFront() {
3.579 + Node *node = first;
3.580 + first = first->next;
3.581 + if (first) {
3.582 + first->prev = 0;
3.583 + } else {
3.584 + last = 0;
3.585 + }
3.586 + alloc.destroy(node);
3.587 + alloc.deallocate(node, 1);
3.588 + }
3.589 +
3.590 + /// \brief Gives back the last arc of the path.
3.591 + const Arc& back() const {
3.592 + return last->arc;
3.593 + }
3.594 +
3.595 + /// \brief Add a new arc behind the current path.
3.596 + void addBack(const Arc& arc) {
3.597 + Node *node = alloc.allocate(1);
3.598 + alloc.construct(node, Node());
3.599 + node->next = 0;
3.600 + node->prev = last;
3.601 + node->arc = arc;
3.602 + if (last) {
3.603 + last->next = node;
3.604 + last = node;
3.605 + } else {
3.606 + last = first = node;
3.607 + }
3.608 + }
3.609 +
3.610 + /// \brief Erase the last arc of the path
3.611 + void eraseBack() {
3.612 + Node *node = last;
3.613 + last = last->prev;
3.614 + if (last) {
3.615 + last->next = 0;
3.616 + } else {
3.617 + first = 0;
3.618 + }
3.619 + alloc.destroy(node);
3.620 + alloc.deallocate(node, 1);
3.621 + }
3.622 +
3.623 + /// \brief Splicing the given path to the current path.
3.624 + ///
3.625 + /// It splices the \c tpath to the back of the current path and \c
3.626 + /// tpath becomes empty. The time complexity of this function is
3.627 + /// O(1).
3.628 + void spliceBack(ListPath& tpath) {
3.629 + if (first) {
3.630 + if (tpath.first) {
3.631 + last->next = tpath.first;
3.632 + tpath.first->prev = last;
3.633 + last = tpath.last;
3.634 + }
3.635 + } else {
3.636 + first = tpath.first;
3.637 + last = tpath.last;
3.638 + }
3.639 + tpath.first = tpath.last = 0;
3.640 + }
3.641 +
3.642 + /// \brief Splicing the given path to the current path.
3.643 + ///
3.644 + /// It splices the \c tpath before the current path and \c tpath
3.645 + /// becomes empty. The time complexity of this function
3.646 + /// is O(1).
3.647 + void spliceFront(ListPath& tpath) {
3.648 + if (first) {
3.649 + if (tpath.first) {
3.650 + first->prev = tpath.last;
3.651 + tpath.last->next = first;
3.652 + first = tpath.first;
3.653 + }
3.654 + } else {
3.655 + first = tpath.first;
3.656 + last = tpath.last;
3.657 + }
3.658 + tpath.first = tpath.last = 0;
3.659 + }
3.660 +
3.661 + /// \brief Splicing the given path into the current path.
3.662 + ///
3.663 + /// It splices the \c tpath into the current path before the
3.664 + /// position of \c it iterator and \c tpath becomes empty. The
3.665 + /// time complexity of this function is O(1). If the \c it is \c
3.666 + /// INVALID then it will splice behind the current path.
3.667 + void splice(ArcIt it, ListPath& tpath) {
3.668 + if (it.node) {
3.669 + if (tpath.first) {
3.670 + tpath.first->prev = it.node->prev;
3.671 + if (it.node->prev) {
3.672 + it.node->prev->next = tpath.first;
3.673 + } else {
3.674 + first = tpath.first;
3.675 + }
3.676 + it.node->prev = tpath.last;
3.677 + tpath.last->next = it.node;
3.678 + }
3.679 + } else {
3.680 + if (first) {
3.681 + if (tpath.first) {
3.682 + last->next = tpath.first;
3.683 + tpath.first->prev = last;
3.684 + last = tpath.last;
3.685 + }
3.686 + } else {
3.687 + first = tpath.first;
3.688 + last = tpath.last;
3.689 + }
3.690 + }
3.691 + tpath.first = tpath.last = 0;
3.692 + }
3.693 +
3.694 + /// \brief Spliting the current path.
3.695 + ///
3.696 + /// It splits the current path into two parts. The part before \c
3.697 + /// it iterator will remain in the current path and the part from
3.698 + /// the it will put into the \c tpath. If the \c tpath had arcs
3.699 + /// before the operation they will be removed first. The time
3.700 + /// complexity of this function is O(1) plus the clearing of \c
3.701 + /// tpath. If the \c it is \c INVALID then it just clears \c
3.702 + /// tpath.
3.703 + void split(ArcIt it, ListPath& tpath) {
3.704 + tpath.clear();
3.705 + if (it.node) {
3.706 + tpath.first = it.node;
3.707 + tpath.last = last;
3.708 + if (it.node->prev) {
3.709 + last = it.node->prev;
3.710 + last->next = 0;
3.711 + } else {
3.712 + first = last = 0;
3.713 + }
3.714 + it.node->prev = 0;
3.715 + }
3.716 + }
3.717 +
3.718 +
3.719 + typedef True BuildTag;
3.720 +
3.721 + template <typename CPath>
3.722 + void build(const CPath& path) {
3.723 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
3.724 + addBack(it);
3.725 + }
3.726 + }
3.727 +
3.728 + template <typename CPath>
3.729 + void buildRev(const CPath& path) {
3.730 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
3.731 + addFront(it);
3.732 + }
3.733 + }
3.734 +
3.735 + };
3.736 +
3.737 + /// \brief A structure for representing directed paths in a digraph.
3.738 + ///
3.739 + /// A structure for representing directed path in a digraph.
3.740 + /// \param Digraph The digraph type in which the path is.
3.741 + ///
3.742 + /// In a sense, the path can be treated as a list of arcs. The
3.743 + /// lemon path type stores just this list. As a consequence it
3.744 + /// cannot enumerate the nodes in the path and the zero length paths
3.745 + /// cannot store the source.
3.746 + ///
3.747 + /// This implementation is completly static, so it cannot be
3.748 + /// modified exclude the assign an other path. It is intented to be
3.749 + /// used when you want to store a large number of paths because it is
3.750 + /// the most memory efficient path type in the lemon.
3.751 + template <typename _Digraph>
3.752 + class StaticPath {
3.753 + public:
3.754 +
3.755 + typedef _Digraph Digraph;
3.756 + typedef typename Digraph::Arc Arc;
3.757 +
3.758 + /// \brief Default constructor
3.759 + ///
3.760 + /// Default constructor
3.761 + StaticPath() : len(0), arcs(0) {}
3.762 +
3.763 + /// \brief Template copy constructor
3.764 + ///
3.765 + /// This path can be initialized with any other path type. It just
3.766 + /// makes a copy of the given path.
3.767 + template <typename CPath>
3.768 + StaticPath(const CPath& cpath) : arcs(0) {
3.769 + copyPath(*this, cpath);
3.770 + }
3.771 +
3.772 + /// \brief Destructor of the path
3.773 + ///
3.774 + /// Destructor of the path
3.775 + ~StaticPath() {
3.776 + if (arcs) delete[] arcs;
3.777 + }
3.778 +
3.779 + /// \brief Template copy assignment
3.780 + ///
3.781 + /// This path can be initialized with any other path type. It just
3.782 + /// makes a copy of the given path.
3.783 + template <typename CPath>
3.784 + StaticPath& operator=(const CPath& cpath) {
3.785 + copyPath(*this, cpath);
3.786 + return *this;
3.787 + }
3.788 +
3.789 + /// \brief Iterator class to iterate on the arcs of the paths
3.790 + ///
3.791 + /// This class is used to iterate on the arcs of the paths
3.792 + ///
3.793 + /// Of course it converts to Digraph::Arc
3.794 + class ArcIt {
3.795 + friend class StaticPath;
3.796 + public:
3.797 + /// Default constructor
3.798 + ArcIt() {}
3.799 + /// Invalid constructor
3.800 + ArcIt(Invalid) : path(0), idx(-1) {}
3.801 + /// Initializate the constructor to the first arc of path
3.802 + ArcIt(const StaticPath &_path)
3.803 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
3.804 +
3.805 + private:
3.806 +
3.807 + /// Constructor with starting point
3.808 + ArcIt(const StaticPath &_path, int _idx)
3.809 + : idx(_idx), path(&_path) {}
3.810 +
3.811 + public:
3.812 +
3.813 + ///Conversion to Digraph::Arc
3.814 + operator const Arc&() const {
3.815 + return path->nth(idx);
3.816 + }
3.817 +
3.818 + /// Next arc
3.819 + ArcIt& operator++() {
3.820 + ++idx;
3.821 + if (idx >= path->length()) idx = -1;
3.822 + return *this;
3.823 + }
3.824 +
3.825 + /// Comparison operator
3.826 + bool operator==(const ArcIt& e) const { return idx==e.idx; }
3.827 + /// Comparison operator
3.828 + bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
3.829 + /// Comparison operator
3.830 + bool operator<(const ArcIt& e) const { return idx<e.idx; }
3.831 +
3.832 + private:
3.833 + const StaticPath *path;
3.834 + int idx;
3.835 + };
3.836 +
3.837 + /// \brief Gives back the nth arc.
3.838 + ///
3.839 + /// \pre n is in the [0..length() - 1] range
3.840 + const Arc& nth(int n) const {
3.841 + return arcs[n];
3.842 + }
3.843 +
3.844 + /// \brief Initializes arc iterator to point to the nth arc.
3.845 + ArcIt nthIt(int n) const {
3.846 + return ArcIt(*this, n);
3.847 + }
3.848 +
3.849 + /// \brief Gives back the length of the path.
3.850 + int length() const { return len; }
3.851 +
3.852 + /// \brief Returns true when the path is empty.
3.853 + int empty() const { return len == 0; }
3.854 +
3.855 + /// \break Erase all arc in the digraph.
3.856 + void clear() {
3.857 + len = 0;
3.858 + if (arcs) delete[] arcs;
3.859 + arcs = 0;
3.860 + }
3.861 +
3.862 + /// \brief Gives back the first arc of the path.
3.863 + const Arc& front() const {
3.864 + return arcs[0];
3.865 + }
3.866 +
3.867 + /// \brief Gives back the last arc of the path.
3.868 + const Arc& back() const {
3.869 + return arcs[len - 1];
3.870 + }
3.871 +
3.872 +
3.873 + typedef True BuildTag;
3.874 +
3.875 + template <typename CPath>
3.876 + void build(const CPath& path) {
3.877 + len = path.length();
3.878 + arcs = new Arc[len];
3.879 + int index = 0;
3.880 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
3.881 + arcs[index] = it;
3.882 + ++index;
3.883 + }
3.884 + }
3.885 +
3.886 + template <typename CPath>
3.887 + void buildRev(const CPath& path) {
3.888 + len = path.length();
3.889 + arcs = new Arc[len];
3.890 + int index = len;
3.891 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
3.892 + --index;
3.893 + arcs[index] = it;
3.894 + }
3.895 + }
3.896 +
3.897 + private:
3.898 + int len;
3.899 + Arc* arcs;
3.900 + };
3.901 +
3.902 + ///@}
3.903 +
3.904 +} // namespace lemon
3.905 +
3.906 +#endif // LEMON_PATH_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/path_utils.h Thu Jan 24 11:31:19 2008 +0000
4.3 @@ -0,0 +1,204 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2008
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +///\ingroup paths
4.23 +///\file
4.24 +///\brief Classes for representing paths in digraphs.
4.25 +///
4.26 +
4.27 +#ifndef LEMON_PATH_UTILS_H
4.28 +#define LEMON_PATH_UTILS_H
4.29 +
4.30 +#include <lemon/concepts/path.h>
4.31 +
4.32 +namespace lemon {
4.33 +
4.34 + namespace _path_bits {
4.35 +
4.36 + template <typename Path, typename Enable = void>
4.37 + struct RevTagIndicator {
4.38 + static const bool value = false;
4.39 + };
4.40 +
4.41 + template <typename Digraph>
4.42 + struct RevTagIndicator<
4.43 + Digraph,
4.44 + typename enable_if<typename Digraph::RevTag, void>::type
4.45 + > {
4.46 + static const bool value = true;
4.47 + };
4.48 +
4.49 + template <typename Target, typename Source,
4.50 + typename BuildEnable = void, typename RevEnable = void>
4.51 + struct PathCopySelector {
4.52 + static void copy(Target& target, const Source& source) {
4.53 + target.clear();
4.54 + for (typename Source::ArcIt it(source); it != INVALID; ++it) {
4.55 + target.addBack(it);
4.56 + }
4.57 + }
4.58 + };
4.59 +
4.60 + template <typename Target, typename Source, typename BuildEnable>
4.61 + struct PathCopySelector<
4.62 + Target, Source, BuildEnable,
4.63 + typename enable_if<typename Source::RevPathTag, void>::type> {
4.64 + static void copy(Target& target, const Source& source) {
4.65 + target.clear();
4.66 + for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
4.67 + target.addFront(it);
4.68 + }
4.69 + }
4.70 + };
4.71 +
4.72 + template <typename Target, typename Source, typename RevEnable>
4.73 + struct PathCopySelector<
4.74 + Target, Source,
4.75 + typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
4.76 + static void copy(Target& target, const Source& source) {
4.77 + target.clear();
4.78 + target.build(source);
4.79 + }
4.80 + };
4.81 +
4.82 + template <typename Target, typename Source>
4.83 + struct PathCopySelector<
4.84 + Target, Source,
4.85 + typename enable_if<typename Target::BuildTag, void>::type,
4.86 + typename enable_if<typename Source::RevPathTag, void>::type> {
4.87 + static void copy(Target& target, const Source& source) {
4.88 + target.clear();
4.89 + target.buildRev(source);
4.90 + }
4.91 + };
4.92 +
4.93 + }
4.94 +
4.95 +
4.96 + /// \brief Make of copy of a path.
4.97 + ///
4.98 + /// Make of copy of a path.
4.99 + template <typename Target, typename Source>
4.100 + void copyPath(Target& target, const Source& source) {
4.101 + checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
4.102 + _path_bits::PathCopySelector<Target, Source>::copy(target, source);
4.103 + }
4.104 +
4.105 + /// \brief Checks the path's consistency.
4.106 + ///
4.107 + /// Checks that each arc's target is the next's source.
4.108 + ///
4.109 + template <typename Digraph, typename Path>
4.110 + bool checkPath(const Digraph& digraph, const Path& path) {
4.111 + typename Path::ArcIt it(path);
4.112 + if (it == INVALID) return true;
4.113 + typename Digraph::Node node = digraph.target(it);
4.114 + ++it;
4.115 + while (it != INVALID) {
4.116 + if (digraph.source(it) != node) return false;
4.117 + node = digraph.target(it);
4.118 + ++it;
4.119 + }
4.120 + return true;
4.121 + }
4.122 +
4.123 + /// \brief Gives back the source of the path
4.124 + ///
4.125 + /// Gives back the source of the path.
4.126 + template <typename Digraph, typename Path>
4.127 + typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
4.128 + return digraph.source(path.front());
4.129 + }
4.130 +
4.131 + /// \brief Gives back the target of the path
4.132 + ///
4.133 + /// Gives back the target of the path.
4.134 + template <typename Digraph, typename Path>
4.135 + typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
4.136 + return digraph.target(path.back());
4.137 + }
4.138 +
4.139 + /// \brief Class which helps to iterate the nodes of a path
4.140 + ///
4.141 + /// In a sense, the path can be treated as a list of arcs. The
4.142 + /// lemon path type stores just this list. As a consequence it
4.143 + /// cannot enumerate the nodes in the path and the zero length paths
4.144 + /// cannot store the node.
4.145 + ///
4.146 + /// This class implements the node iterator of a path structure. To
4.147 + /// provide this feature, the underlying digraph should be given to
4.148 + /// the constructor of the iterator.
4.149 + template <typename Path>
4.150 + class PathNodeIt {
4.151 + private:
4.152 + const typename Path::Digraph *_digraph;
4.153 + typename Path::ArcIt _it;
4.154 + typename Path::Digraph::Node _nd;
4.155 +
4.156 + public:
4.157 +
4.158 + typedef typename Path::Digraph Digraph;
4.159 + typedef typename Digraph::Node Node;
4.160 +
4.161 + /// Default constructor
4.162 + PathNodeIt() {}
4.163 + /// Invalid constructor
4.164 + PathNodeIt(Invalid)
4.165 + : _digraph(0), _it(INVALID), _nd(INVALID) {}
4.166 + /// Constructor
4.167 + PathNodeIt(const Digraph& digraph, const Path& path)
4.168 + : _digraph(&digraph), _it(path) {
4.169 + _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
4.170 + }
4.171 + /// Constructor
4.172 + PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
4.173 + : _digraph(&digraph), _it(path), _nd(src) {}
4.174 +
4.175 + ///Conversion to Digraph::Node
4.176 + operator Node() const {
4.177 + return _nd;
4.178 + }
4.179 +
4.180 + /// Next node
4.181 + PathNodeIt& operator++() {
4.182 + if (_it == INVALID) _nd = INVALID;
4.183 + else {
4.184 + _nd = _digraph->target(_it);
4.185 + ++_it;
4.186 + }
4.187 + return *this;
4.188 + }
4.189 +
4.190 + /// Comparison operator
4.191 + bool operator==(const PathNodeIt& n) const {
4.192 + return _it == n._it && _nd == n._nd;
4.193 + }
4.194 + /// Comparison operator
4.195 + bool operator!=(const PathNodeIt& n) const {
4.196 + return _it != n._it || _nd != n._nd;
4.197 + }
4.198 + /// Comparison operator
4.199 + bool operator<(const PathNodeIt& n) const {
4.200 + return (_it < n._it && _nd != INVALID);
4.201 + }
4.202 +
4.203 + };
4.204 +
4.205 +}
4.206 +
4.207 +#endif
5.1 --- a/test/Makefile.am Wed Jan 23 16:26:41 2008 +0100
5.2 +++ b/test/Makefile.am Thu Jan 24 11:31:19 2008 +0000
5.3 @@ -11,6 +11,7 @@
5.4 test/dim_test \
5.5 test/graph_test \
5.6 test/random_test \
5.7 + test/path_test \
5.8 test/test_tools_fail \
5.9 test/test_tools_pass
5.10
5.11 @@ -20,6 +21,7 @@
5.12 test_digraph_test_SOURCES = test/digraph_test.cc
5.13 test_dim_test_SOURCES = test/dim_test.cc
5.14 test_graph_test_SOURCES = test/graph_test.cc
5.15 +test_path_test_SOURCES = test/path_test.cc
5.16 test_random_test_SOURCES = test/random_test.cc
5.17 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
5.18 test_test_tools_pass_SOURCES = test/test_tools_pass.cc
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/test/path_test.cc Thu Jan 24 11:31:19 2008 +0000
6.3 @@ -0,0 +1,44 @@
6.4 +/* -*- C++ -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library
6.7 + *
6.8 + * Copyright (C) 2003-2008
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +#include <string>
6.23 +#include <iostream>
6.24 +
6.25 +#include <lemon/concepts/path.h>
6.26 +#include <lemon/concepts/digraph.h>
6.27 +
6.28 +#include <lemon/path.h>
6.29 +#include <lemon/list_graph.h>
6.30 +
6.31 +#include "test_tools.h"
6.32 +
6.33 +using namespace std;
6.34 +using namespace lemon;
6.35 +
6.36 +void check_concepts() {
6.37 + checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >();
6.38 + checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >();
6.39 + checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >();
6.40 + checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >();
6.41 + checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >();
6.42 +}
6.43 +
6.44 +int main() {
6.45 + check_concepts();
6.46 + return 0;
6.47 +}