Changeset 98:c4582fc14f58 in lemon for lemon/path.h
 Timestamp:
 01/24/08 18:36:45 (17 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/path.h
r97 r98 28 28 #include <algorithm> 29 29 30 #include <lemon/path_utils.h>31 30 #include <lemon/error.h> 32 31 #include <lemon/bits/invalid.h> … … 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
Note: See TracChangeset
for help on using the changeset viewer.