diff --git a/lemon/path.h b/lemon/path.h --- a/lemon/path.h +++ b/lemon/path.h @@ -27,7 +27,6 @@ #include #include -#include #include #include @@ -896,6 +895,182 @@ Arc* arcs; }; + /////////////////////////////////////////////////////////////////////// + // Additional utilities + /////////////////////////////////////////////////////////////////////// + + namespace _path_bits { + + template + struct RevTagIndicator { + static const bool value = false; + }; + + template + struct RevTagIndicator< + Digraph, + typename enable_if::type + > { + static const bool value = true; + }; + + template + struct PathCopySelector { + static void copy(Target& target, const Source& source) { + target.clear(); + for (typename Source::ArcIt it(source); it != INVALID; ++it) { + target.addBack(it); + } + } + }; + + template + struct PathCopySelector< + Target, Source, BuildEnable, + typename enable_if::type> { + static void copy(Target& target, const Source& source) { + target.clear(); + for (typename Source::RevArcIt it(source); it != INVALID; ++it) { + target.addFront(it); + } + } + }; + + template + struct PathCopySelector< + Target, Source, + typename enable_if::type, RevEnable> { + static void copy(Target& target, const Source& source) { + target.clear(); + target.build(source); + } + }; + + template + struct PathCopySelector< + Target, Source, + typename enable_if::type, + typename enable_if::type> { + static void copy(Target& target, const Source& source) { + target.clear(); + target.buildRev(source); + } + }; + + } + + + /// \brief Make a copy of a path. + /// + /// This function makes a copy of a path. + template + void copyPath(Target& target, const Source& source) { + checkConcept, Source>(); + _path_bits::PathCopySelector::copy(target, source); + } + + /// \brief Check the consistency of a path. + /// + /// This function checks that the target of each arc is the same + /// as the source of the next one. + /// + template + bool checkPath(const Digraph& digraph, const Path& path) { + typename Path::ArcIt it(path); + if (it == INVALID) return true; + typename Digraph::Node node = digraph.target(it); + ++it; + while (it != INVALID) { + if (digraph.source(it) != node) return false; + node = digraph.target(it); + ++it; + } + return true; + } + + /// \brief The source of a path + /// + /// This function returns the source of the given path. + template + typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) { + return digraph.source(path.front()); + } + + /// \brief The target of a path + /// + /// This function returns the target of the given path. + template + typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) { + return digraph.target(path.back()); + } + + /// \brief Class which helps to iterate through the nodes of a path + /// + /// In a sense, the path can be treated as a list of arcs. The + /// lemon path type stores only this list. As a consequence, it + /// cannot enumerate the nodes in the path and the zero length paths + /// cannot have a source node. + /// + /// This class implements the node iterator of a path structure. To + /// provide this feature, the underlying digraph should be passed to + /// the constructor of the iterator. + template + class PathNodeIt { + private: + const typename Path::Digraph *_digraph; + typename Path::ArcIt _it; + typename Path::Digraph::Node _nd; + + public: + + typedef typename Path::Digraph Digraph; + typedef typename Digraph::Node Node; + + /// Default constructor + PathNodeIt() {} + /// Invalid constructor + PathNodeIt(Invalid) + : _digraph(0), _it(INVALID), _nd(INVALID) {} + /// Constructor + PathNodeIt(const Digraph& digraph, const Path& path) + : _digraph(&digraph), _it(path) { + _nd = (_it != INVALID ? _digraph->source(_it) : INVALID); + } + /// Constructor + PathNodeIt(const Digraph& digraph, const Path& path, const Node& src) + : _digraph(&digraph), _it(path), _nd(src) {} + + ///Conversion to Digraph::Node + operator Node() const { + return _nd; + } + + /// Next node + PathNodeIt& operator++() { + if (_it == INVALID) _nd = INVALID; + else { + _nd = _digraph->target(_it); + ++_it; + } + return *this; + } + + /// Comparison operator + bool operator==(const PathNodeIt& n) const { + return _it == n._it && _nd == n._nd; + } + /// Comparison operator + bool operator!=(const PathNodeIt& n) const { + return _it != n._it || _nd != n._nd; + } + /// Comparison operator + bool operator<(const PathNodeIt& n) const { + return (_it < n._it && _nd != INVALID); + } + + }; + ///@} } // namespace lemon