1.1 --- a/lemon/path.h Thu Jan 24 16:49:10 2008 +0000
1.2 +++ b/lemon/path.h Thu Jan 24 17:36:45 2008 +0000
1.3 @@ -27,7 +27,6 @@
1.4 #include <vector>
1.5 #include <algorithm>
1.6
1.7 -#include <lemon/path_utils.h>
1.8 #include <lemon/error.h>
1.9 #include <lemon/bits/invalid.h>
1.10
1.11 @@ -896,6 +895,182 @@
1.12 Arc* arcs;
1.13 };
1.14
1.15 + ///////////////////////////////////////////////////////////////////////
1.16 + // Additional utilities
1.17 + ///////////////////////////////////////////////////////////////////////
1.18 +
1.19 + namespace _path_bits {
1.20 +
1.21 + template <typename Path, typename Enable = void>
1.22 + struct RevTagIndicator {
1.23 + static const bool value = false;
1.24 + };
1.25 +
1.26 + template <typename Digraph>
1.27 + struct RevTagIndicator<
1.28 + Digraph,
1.29 + typename enable_if<typename Digraph::RevTag, void>::type
1.30 + > {
1.31 + static const bool value = true;
1.32 + };
1.33 +
1.34 + template <typename Target, typename Source,
1.35 + typename BuildEnable = void, typename RevEnable = void>
1.36 + struct PathCopySelector {
1.37 + static void copy(Target& target, const Source& source) {
1.38 + target.clear();
1.39 + for (typename Source::ArcIt it(source); it != INVALID; ++it) {
1.40 + target.addBack(it);
1.41 + }
1.42 + }
1.43 + };
1.44 +
1.45 + template <typename Target, typename Source, typename BuildEnable>
1.46 + struct PathCopySelector<
1.47 + Target, Source, BuildEnable,
1.48 + typename enable_if<typename Source::RevPathTag, void>::type> {
1.49 + static void copy(Target& target, const Source& source) {
1.50 + target.clear();
1.51 + for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
1.52 + target.addFront(it);
1.53 + }
1.54 + }
1.55 + };
1.56 +
1.57 + template <typename Target, typename Source, typename RevEnable>
1.58 + struct PathCopySelector<
1.59 + Target, Source,
1.60 + typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
1.61 + static void copy(Target& target, const Source& source) {
1.62 + target.clear();
1.63 + target.build(source);
1.64 + }
1.65 + };
1.66 +
1.67 + template <typename Target, typename Source>
1.68 + struct PathCopySelector<
1.69 + Target, Source,
1.70 + typename enable_if<typename Target::BuildTag, void>::type,
1.71 + typename enable_if<typename Source::RevPathTag, void>::type> {
1.72 + static void copy(Target& target, const Source& source) {
1.73 + target.clear();
1.74 + target.buildRev(source);
1.75 + }
1.76 + };
1.77 +
1.78 + }
1.79 +
1.80 +
1.81 + /// \brief Make a copy of a path.
1.82 + ///
1.83 + /// This function makes a copy of a path.
1.84 + template <typename Target, typename Source>
1.85 + void copyPath(Target& target, const Source& source) {
1.86 + checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
1.87 + _path_bits::PathCopySelector<Target, Source>::copy(target, source);
1.88 + }
1.89 +
1.90 + /// \brief Check the consistency of a path.
1.91 + ///
1.92 + /// This function checks that the target of each arc is the same
1.93 + /// as the source of the next one.
1.94 + ///
1.95 + template <typename Digraph, typename Path>
1.96 + bool checkPath(const Digraph& digraph, const Path& path) {
1.97 + typename Path::ArcIt it(path);
1.98 + if (it == INVALID) return true;
1.99 + typename Digraph::Node node = digraph.target(it);
1.100 + ++it;
1.101 + while (it != INVALID) {
1.102 + if (digraph.source(it) != node) return false;
1.103 + node = digraph.target(it);
1.104 + ++it;
1.105 + }
1.106 + return true;
1.107 + }
1.108 +
1.109 + /// \brief The source of a path
1.110 + ///
1.111 + /// This function returns the source of the given path.
1.112 + template <typename Digraph, typename Path>
1.113 + typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1.114 + return digraph.source(path.front());
1.115 + }
1.116 +
1.117 + /// \brief The target of a path
1.118 + ///
1.119 + /// This function returns the target of the given path.
1.120 + template <typename Digraph, typename Path>
1.121 + typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1.122 + return digraph.target(path.back());
1.123 + }
1.124 +
1.125 + /// \brief Class which helps to iterate through the nodes of a path
1.126 + ///
1.127 + /// In a sense, the path can be treated as a list of arcs. The
1.128 + /// lemon path type stores only this list. As a consequence, it
1.129 + /// cannot enumerate the nodes in the path and the zero length paths
1.130 + /// cannot have a source node.
1.131 + ///
1.132 + /// This class implements the node iterator of a path structure. To
1.133 + /// provide this feature, the underlying digraph should be passed to
1.134 + /// the constructor of the iterator.
1.135 + template <typename Path>
1.136 + class PathNodeIt {
1.137 + private:
1.138 + const typename Path::Digraph *_digraph;
1.139 + typename Path::ArcIt _it;
1.140 + typename Path::Digraph::Node _nd;
1.141 +
1.142 + public:
1.143 +
1.144 + typedef typename Path::Digraph Digraph;
1.145 + typedef typename Digraph::Node Node;
1.146 +
1.147 + /// Default constructor
1.148 + PathNodeIt() {}
1.149 + /// Invalid constructor
1.150 + PathNodeIt(Invalid)
1.151 + : _digraph(0), _it(INVALID), _nd(INVALID) {}
1.152 + /// Constructor
1.153 + PathNodeIt(const Digraph& digraph, const Path& path)
1.154 + : _digraph(&digraph), _it(path) {
1.155 + _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
1.156 + }
1.157 + /// Constructor
1.158 + PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
1.159 + : _digraph(&digraph), _it(path), _nd(src) {}
1.160 +
1.161 + ///Conversion to Digraph::Node
1.162 + operator Node() const {
1.163 + return _nd;
1.164 + }
1.165 +
1.166 + /// Next node
1.167 + PathNodeIt& operator++() {
1.168 + if (_it == INVALID) _nd = INVALID;
1.169 + else {
1.170 + _nd = _digraph->target(_it);
1.171 + ++_it;
1.172 + }
1.173 + return *this;
1.174 + }
1.175 +
1.176 + /// Comparison operator
1.177 + bool operator==(const PathNodeIt& n) const {
1.178 + return _it == n._it && _nd == n._nd;
1.179 + }
1.180 + /// Comparison operator
1.181 + bool operator!=(const PathNodeIt& n) const {
1.182 + return _it != n._it || _nd != n._nd;
1.183 + }
1.184 + /// Comparison operator
1.185 + bool operator<(const PathNodeIt& n) const {
1.186 + return (_it < n._it && _nd != INVALID);
1.187 + }
1.188 +
1.189 + };
1.190 +
1.191 ///@}
1.192
1.193 } // namespace lemon