alpar@96: /* -*- C++ -*-
alpar@96:  *
alpar@96:  * This file is a part of LEMON, a generic C++ optimization library
alpar@96:  *
alpar@96:  * Copyright (C) 2003-2008
alpar@96:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@96:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@96:  *
alpar@96:  * Permission to use, modify and distribute this software is granted
alpar@96:  * provided that this copyright notice appears in all copies. For
alpar@96:  * precise terms see the accompanying LICENSE file.
alpar@96:  *
alpar@96:  * This software is provided "AS IS" with no warranty of any kind,
alpar@96:  * express or implied, and with no claim as to its suitability for any
alpar@96:  * purpose.
alpar@96:  *
alpar@96:  */
alpar@96: 
alpar@96: ///\ingroup paths
alpar@96: ///\file
alpar@96: ///\brief Classes for representing paths in digraphs.
alpar@96: ///
alpar@96: 
alpar@96: #ifndef LEMON_PATH_UTILS_H
alpar@96: #define LEMON_PATH_UTILS_H
alpar@96: 
alpar@96: #include <lemon/concepts/path.h>
alpar@96: 
alpar@96: namespace lemon {
alpar@96: 
alpar@96:   namespace _path_bits {
alpar@96: 
alpar@96:     template <typename Path, typename Enable = void>
alpar@96:     struct RevTagIndicator {
alpar@96:       static const bool value = false;
alpar@96:     };
alpar@96: 
alpar@96:     template <typename Digraph>
alpar@96:     struct RevTagIndicator<
alpar@96:       Digraph, 
alpar@96:       typename enable_if<typename Digraph::RevTag, void>::type
alpar@96:     > {
alpar@96:       static const bool value = true;
alpar@96:     };
alpar@96: 
alpar@96:     template <typename Target, typename Source,
alpar@96:               typename BuildEnable = void, typename RevEnable = void>
alpar@96:     struct PathCopySelector {
alpar@96:       static void copy(Target& target, const Source& source) {
alpar@96:         target.clear();
alpar@96:         for (typename Source::ArcIt it(source); it != INVALID; ++it) {
alpar@96:           target.addBack(it);
alpar@96:         }
alpar@96:       }
alpar@96:     };
alpar@96: 
alpar@96:     template <typename Target, typename Source, typename BuildEnable>
alpar@96:     struct PathCopySelector<
alpar@96:       Target, Source, BuildEnable, 
alpar@96:       typename enable_if<typename Source::RevPathTag, void>::type> {
alpar@96:       static void copy(Target& target, const Source& source) {
alpar@96:         target.clear();
alpar@96:         for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
alpar@96:           target.addFront(it);
alpar@96:         }
alpar@96:       }
alpar@96:     };
alpar@96: 
alpar@96:     template <typename Target, typename Source, typename RevEnable>
alpar@96:     struct PathCopySelector<
alpar@96:       Target, Source, 
alpar@96:       typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
alpar@96:       static void copy(Target& target, const Source& source) {
alpar@96:         target.clear();
alpar@96:         target.build(source);
alpar@96:       }
alpar@96:     };
alpar@96: 
alpar@96:     template <typename Target, typename Source>
alpar@96:     struct PathCopySelector<
alpar@96:       Target, Source, 
alpar@96:       typename enable_if<typename Target::BuildTag, void>::type,
alpar@96:       typename enable_if<typename Source::RevPathTag, void>::type> {
alpar@96:       static void copy(Target& target, const Source& source) {
alpar@96:         target.clear();
alpar@96:         target.buildRev(source);
alpar@96:       }
alpar@96:     };
alpar@96: 
alpar@96:   }
alpar@96: 
alpar@96: 
alpar@97:   /// \brief Make a copy of a path.
alpar@96:   ///
alpar@97:   ///  This function makes a copy of a path.
alpar@96:   template <typename Target, typename Source>
alpar@96:   void copyPath(Target& target, const Source& source) {
alpar@96:     checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
alpar@96:     _path_bits::PathCopySelector<Target, Source>::copy(target, source);
alpar@96:   }
alpar@96: 
alpar@97:   /// \brief Check the consistency of a path.
alpar@96:   ///
alpar@97:   /// This function checks that the target of each arc is the same
alpar@97:   /// as the source of the next one. 
alpar@96:   /// 
alpar@96:   template <typename Digraph, typename Path>
alpar@96:   bool checkPath(const Digraph& digraph, const Path& path) {
alpar@96:     typename Path::ArcIt it(path);
alpar@96:     if (it == INVALID) return true;
alpar@96:     typename Digraph::Node node = digraph.target(it);
alpar@96:     ++it;
alpar@96:     while (it != INVALID) {
alpar@96:       if (digraph.source(it) != node) return false;
alpar@96:       node = digraph.target(it);
alpar@96:       ++it;
alpar@96:     }
alpar@96:     return true;
alpar@96:   }
alpar@96: 
alpar@97:   /// \brief The source of a path
alpar@96:   ///
alpar@97:   /// This function returns the source of the given path.
alpar@96:   template <typename Digraph, typename Path>
alpar@96:   typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
alpar@96:     return digraph.source(path.front());
alpar@96:   }
alpar@96: 
alpar@97:   /// \brief The target of a path
alpar@96:   ///
alpar@97:   /// This function returns the target of the given path.
alpar@96:   template <typename Digraph, typename Path>
alpar@96:   typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
alpar@96:     return digraph.target(path.back());
alpar@96:   }
alpar@96: 
alpar@97:   /// \brief Class which helps to iterate through the nodes of a path
alpar@96:   ///
alpar@96:   /// In a sense, the path can be treated as a list of arcs. The
alpar@97:   /// lemon path type stores only this list. As a consequence, it
alpar@96:   /// cannot enumerate the nodes in the path and the zero length paths
alpar@97:   /// cannot have a source node.
alpar@96:   ///
alpar@96:   /// This class implements the node iterator of a path structure. To
alpar@97:   /// provide this feature, the underlying digraph should be passed to
alpar@96:   /// the constructor of the iterator.
alpar@96:   template <typename Path>
alpar@96:   class PathNodeIt {
alpar@96:   private:
alpar@96:     const typename Path::Digraph *_digraph;
alpar@96:     typename Path::ArcIt _it;
alpar@96:     typename Path::Digraph::Node _nd;
alpar@96: 
alpar@96:   public:
alpar@96: 
alpar@96:     typedef typename Path::Digraph Digraph;
alpar@96:     typedef typename Digraph::Node Node;
alpar@96:     
alpar@96:     /// Default constructor
alpar@96:     PathNodeIt() {}
alpar@96:     /// Invalid constructor
alpar@96:     PathNodeIt(Invalid) 
alpar@96:       : _digraph(0), _it(INVALID), _nd(INVALID) {}
alpar@96:     /// Constructor
alpar@96:     PathNodeIt(const Digraph& digraph, const Path& path) 
alpar@96:       : _digraph(&digraph), _it(path) {
alpar@96:       _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
alpar@96:     }
alpar@96:     /// Constructor
alpar@96:     PathNodeIt(const Digraph& digraph, const Path& path, const Node& src) 
alpar@96:       : _digraph(&digraph), _it(path), _nd(src) {}
alpar@96: 
alpar@96:     ///Conversion to Digraph::Node
alpar@96:     operator Node() const {
alpar@96:       return _nd;
alpar@96:     }
alpar@96: 
alpar@96:     /// Next node
alpar@96:     PathNodeIt& operator++() {
alpar@96:       if (_it == INVALID) _nd = INVALID;
alpar@96:       else {
alpar@96: 	_nd = _digraph->target(_it);
alpar@96: 	++_it;
alpar@96:       }
alpar@96:       return *this;
alpar@96:     }
alpar@96: 
alpar@96:     /// Comparison operator
alpar@96:     bool operator==(const PathNodeIt& n) const { 
alpar@96:       return _it == n._it && _nd == n._nd; 
alpar@96:     }
alpar@96:     /// Comparison operator
alpar@96:     bool operator!=(const PathNodeIt& n) const { 
alpar@96:       return _it != n._it || _nd != n._nd; 
alpar@96:     }
alpar@96:     /// Comparison operator
alpar@96:     bool operator<(const PathNodeIt& n) const { 
alpar@96:       return (_it < n._it && _nd != INVALID);
alpar@96:     }
alpar@96:     
alpar@96:   };
alpar@96:   
alpar@96: }
alpar@96: 
alpar@96: #endif