diff --git a/lemon/path_utils.h b/lemon/path_utils.h new file mode 100644 --- /dev/null +++ b/lemon/path_utils.h @@ -0,0 +1,204 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +///\ingroup paths +///\file +///\brief Classes for representing paths in digraphs. +/// + +#ifndef LEMON_PATH_UTILS_H +#define LEMON_PATH_UTILS_H + +#include + +namespace lemon { + + 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 of copy of a path. + /// + /// Make of copy of a path. + template + void copyPath(Target& target, const Source& source) { + checkConcept, Source>(); + _path_bits::PathCopySelector::copy(target, source); + } + + /// \brief Checks the path's consistency. + /// + /// Checks that each arc's target is the next's source. + /// + 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 Gives back the source of the path + /// + /// Gives back the source of the path. + template + typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) { + return digraph.source(path.front()); + } + + /// \brief Gives back the target of the path + /// + /// Gives back the target of the path. + template + typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) { + return digraph.target(path.back()); + } + + /// \brief Class which helps to iterate the nodes of a path + /// + /// In a sense, the path can be treated as a list of arcs. The + /// lemon path type stores just this list. As a consequence it + /// cannot enumerate the nodes in the path and the zero length paths + /// cannot store the node. + /// + /// This class implements the node iterator of a path structure. To + /// provide this feature, the underlying digraph should be given 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); + } + + }; + +} + +#endif