lemon/path.h
changeset 99 dbaa96cc1013
parent 97 ee1324c91288
child 100 4f754b4cf82b
equal deleted inserted replaced
1:cac7ce604998 2:a2bcdf1591b3
    25 #define LEMON_PATH_H
    25 #define LEMON_PATH_H
    26 
    26 
    27 #include <vector>
    27 #include <vector>
    28 #include <algorithm>
    28 #include <algorithm>
    29 
    29 
    30 #include <lemon/path_utils.h>
       
    31 #include <lemon/error.h>
    30 #include <lemon/error.h>
    32 #include <lemon/bits/invalid.h>
    31 #include <lemon/bits/invalid.h>
    33 
    32 
    34 namespace lemon {
    33 namespace lemon {
    35 
    34 
   894   private:
   893   private:
   895     int len;
   894     int len;
   896     Arc* arcs;
   895     Arc* arcs;
   897   };
   896   };
   898 
   897 
       
   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   
   899   ///@}
  1074   ///@}
   900 
  1075 
   901 } // namespace lemon
  1076 } // namespace lemon
   902 
  1077 
   903 #endif // LEMON_PATH_H
  1078 #endif // LEMON_PATH_H