Changeset 917:a6eb9698c321 in lemon
- Timestamp:
- 02/19/10 14:08:32 (15 years ago)
- Branch:
- default
- Children:
- 918:a5fc1e1e5039, 958:d6052a9c4e8d
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bellman_ford.h
r891 r917 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/tolerance.h> 31 32 #include <lemon/path.h> 32 33 … … 35 36 namespace lemon { 36 37 37 /// \brief Default OperationTraits for the BellmanFord algorithm class.38 /// \brief Default operation traits for the BellmanFord algorithm class. 38 39 /// 39 40 /// This operation traits class defines all computational operations … … 42 43 /// If the numeric type does not have infinity value, then the maximum 43 44 /// value is used as extremal infinity value. 45 /// 46 /// \see BellmanFordToleranceOperationTraits 44 47 template < 45 48 typename V, 46 49 bool has_inf = std::numeric_limits<V>::has_infinity> 47 50 struct BellmanFordDefaultOperationTraits { 48 /// \ e51 /// \brief Value type for the algorithm. 49 52 typedef V Value; 50 53 /// \brief Gives back the zero value of the type. … … 85 88 }; 86 89 90 /// \brief Operation traits for the BellmanFord algorithm class 91 /// using tolerance. 92 /// 93 /// This operation traits class defines all computational operations 94 /// and constants that are used in the Bellman-Ford algorithm. 95 /// The only difference between this implementation and 96 /// \ref BellmanFordDefaultOperationTraits is that this class uses 97 /// the \ref Tolerance "tolerance technique" in its \ref less() 98 /// function. 99 /// 100 /// \tparam V The value type. 101 /// \tparam eps The epsilon value for the \ref less() function. 102 /// By default, it is the epsilon value used by \ref Tolerance 103 /// "Tolerance<V>". 104 /// 105 /// \see BellmanFordDefaultOperationTraits 106 #ifdef DOXYGEN 107 template <typename V, V eps> 108 #else 109 template < 110 typename V, 111 V eps = Tolerance<V>::def_epsilon> 112 #endif 113 struct BellmanFordToleranceOperationTraits { 114 /// \brief Value type for the algorithm. 115 typedef V Value; 116 /// \brief Gives back the zero value of the type. 117 static Value zero() { 118 return static_cast<Value>(0); 119 } 120 /// \brief Gives back the positive infinity value of the type. 121 static Value infinity() { 122 return std::numeric_limits<Value>::infinity(); 123 } 124 /// \brief Gives back the sum of the given two elements. 125 static Value plus(const Value& left, const Value& right) { 126 return left + right; 127 } 128 /// \brief Gives back \c true only if the first value is less than 129 /// the second. 130 static bool less(const Value& left, const Value& right) { 131 return left + eps < right; 132 } 133 }; 134 87 135 /// \brief Default traits class of BellmanFord class. 88 136 /// … … 108 156 /// It defines the used operations and the infinity value for the 109 157 /// given \c Value type. 110 /// \see BellmanFordDefaultOperationTraits 158 /// \see BellmanFordDefaultOperationTraits, 159 /// BellmanFordToleranceOperationTraits 111 160 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 112 161 … … 838 887 /// It defines the used operations and the infinity value for the 839 888 /// given \c Value type. 840 /// \see BellmanFordDefaultOperationTraits 889 /// \see BellmanFordDefaultOperationTraits, 890 /// BellmanFordToleranceOperationTraits 841 891 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 842 892 -
test/bellman_ford_test.cc
r838 r917 105 105 ::SetDistMap<concepts::ReadWriteMap<Node,Value> > 106 106 ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> > 107 ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> > 107 108 ::Create bf_test(gr,length); 108 109
Note: See TracChangeset
for help on using the changeset viewer.