COIN-OR::LEMON - Graph Library

Changeset 98:c4582fc14f58 in lemon-main for lemon/path.h


Ignore:
Timestamp:
01/24/08 18:36:45 (12 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Merge path_utils.h into path.h

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/path.h

    r97 r98  
    2828#include <algorithm>
    2929
    30 #include <lemon/path_utils.h>
    3130#include <lemon/error.h>
    3231#include <lemon/bits/invalid.h>
     
    897896  };
    898897
     898  ///////////////////////////////////////////////////////////////////////
     899  // Additional utilities
     900  ///////////////////////////////////////////////////////////////////////
     901
     902  namespace _path_bits {
     903
     904    template <typename Path, typename Enable = void>
     905    struct RevTagIndicator {
     906      static const bool value = false;
     907    };
     908
     909    template <typename Digraph>
     910    struct RevTagIndicator<
     911      Digraph,
     912      typename enable_if<typename Digraph::RevTag, void>::type
     913    > {
     914      static const bool value = true;
     915    };
     916
     917    template <typename Target, typename Source,
     918              typename BuildEnable = void, typename RevEnable = void>
     919    struct PathCopySelector {
     920      static void copy(Target& target, const Source& source) {
     921        target.clear();
     922        for (typename Source::ArcIt it(source); it != INVALID; ++it) {
     923          target.addBack(it);
     924        }
     925      }
     926    };
     927
     928    template <typename Target, typename Source, typename BuildEnable>
     929    struct PathCopySelector<
     930      Target, Source, BuildEnable,
     931      typename enable_if<typename Source::RevPathTag, void>::type> {
     932      static void copy(Target& target, const Source& source) {
     933        target.clear();
     934        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
     935          target.addFront(it);
     936        }
     937      }
     938    };
     939
     940    template <typename Target, typename Source, typename RevEnable>
     941    struct PathCopySelector<
     942      Target, Source,
     943      typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
     944      static void copy(Target& target, const Source& source) {
     945        target.clear();
     946        target.build(source);
     947      }
     948    };
     949
     950    template <typename Target, typename Source>
     951    struct PathCopySelector<
     952      Target, Source,
     953      typename enable_if<typename Target::BuildTag, void>::type,
     954      typename enable_if<typename Source::RevPathTag, void>::type> {
     955      static void copy(Target& target, const Source& source) {
     956        target.clear();
     957        target.buildRev(source);
     958      }
     959    };
     960
     961  }
     962
     963
     964  /// \brief Make a copy of a path.
     965  ///
     966  ///  This function makes a copy of a path.
     967  template <typename Target, typename Source>
     968  void copyPath(Target& target, const Source& source) {
     969    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
     970    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
     971  }
     972
     973  /// \brief Check the consistency of a path.
     974  ///
     975  /// This function checks that the target of each arc is the same
     976  /// as the source of the next one.
     977  ///
     978  template <typename Digraph, typename Path>
     979  bool checkPath(const Digraph& digraph, const Path& path) {
     980    typename Path::ArcIt it(path);
     981    if (it == INVALID) return true;
     982    typename Digraph::Node node = digraph.target(it);
     983    ++it;
     984    while (it != INVALID) {
     985      if (digraph.source(it) != node) return false;
     986      node = digraph.target(it);
     987      ++it;
     988    }
     989    return true;
     990  }
     991
     992  /// \brief The source of a path
     993  ///
     994  /// This function returns the source of the given path.
     995  template <typename Digraph, typename Path>
     996  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
     997    return digraph.source(path.front());
     998  }
     999
     1000  /// \brief The target of a path
     1001  ///
     1002  /// This function returns the target of the given path.
     1003  template <typename Digraph, typename Path>
     1004  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
     1005    return digraph.target(path.back());
     1006  }
     1007
     1008  /// \brief Class which helps to iterate through the nodes of a path
     1009  ///
     1010  /// In a sense, the path can be treated as a list of arcs. The
     1011  /// lemon path type stores only this list. As a consequence, it
     1012  /// cannot enumerate the nodes in the path and the zero length paths
     1013  /// cannot have a source node.
     1014  ///
     1015  /// This class implements the node iterator of a path structure. To
     1016  /// provide this feature, the underlying digraph should be passed to
     1017  /// the constructor of the iterator.
     1018  template <typename Path>
     1019  class PathNodeIt {
     1020  private:
     1021    const typename Path::Digraph *_digraph;
     1022    typename Path::ArcIt _it;
     1023    typename Path::Digraph::Node _nd;
     1024
     1025  public:
     1026
     1027    typedef typename Path::Digraph Digraph;
     1028    typedef typename Digraph::Node Node;
     1029   
     1030    /// Default constructor
     1031    PathNodeIt() {}
     1032    /// Invalid constructor
     1033    PathNodeIt(Invalid)
     1034      : _digraph(0), _it(INVALID), _nd(INVALID) {}
     1035    /// Constructor
     1036    PathNodeIt(const Digraph& digraph, const Path& path)
     1037      : _digraph(&digraph), _it(path) {
     1038      _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
     1039    }
     1040    /// Constructor
     1041    PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
     1042      : _digraph(&digraph), _it(path), _nd(src) {}
     1043
     1044    ///Conversion to Digraph::Node
     1045    operator Node() const {
     1046      return _nd;
     1047    }
     1048
     1049    /// Next node
     1050    PathNodeIt& operator++() {
     1051      if (_it == INVALID) _nd = INVALID;
     1052      else {
     1053        _nd = _digraph->target(_it);
     1054        ++_it;
     1055      }
     1056      return *this;
     1057    }
     1058
     1059    /// Comparison operator
     1060    bool operator==(const PathNodeIt& n) const {
     1061      return _it == n._it && _nd == n._nd;
     1062    }
     1063    /// Comparison operator
     1064    bool operator!=(const PathNodeIt& n) const {
     1065      return _it != n._it || _nd != n._nd;
     1066    }
     1067    /// Comparison operator
     1068    bool operator<(const PathNodeIt& n) const {
     1069      return (_it < n._it && _nd != INVALID);
     1070    }
     1071   
     1072  };
     1073 
    8991074  ///@}
    9001075
Note: See TracChangeset for help on using the changeset viewer.