Changes in / [959:38213abd2911:960:b89e46862dc2] in lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bellman_ford.h
r956 r960 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/tolerance.h>32 31 #include <lemon/path.h> 33 32 … … 36 35 namespace lemon { 37 36 38 /// \brief Default operation traits for the BellmanFord algorithm class.37 /// \brief Default OperationTraits for the BellmanFord algorithm class. 39 38 /// 40 39 /// This operation traits class defines all computational operations … … 43 42 /// If the numeric type does not have infinity value, then the maximum 44 43 /// value is used as extremal infinity value. 45 ///46 /// \see BellmanFordToleranceOperationTraits47 44 template < 48 45 typename V, 49 46 bool has_inf = std::numeric_limits<V>::has_infinity> 50 47 struct BellmanFordDefaultOperationTraits { 51 /// \ brief Value type for the algorithm.48 /// \e 52 49 typedef V Value; 53 50 /// \brief Gives back the zero value of the type. … … 85 82 static bool less(const Value& left, const Value& right) { 86 83 return left < right; 87 }88 };89 90 /// \brief Operation traits for the BellmanFord algorithm class91 /// using tolerance.92 ///93 /// This operation traits class defines all computational operations94 /// and constants that are used in the Bellman-Ford algorithm.95 /// The only difference between this implementation and96 /// \ref BellmanFordDefaultOperationTraits is that this class uses97 /// 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 Tolerance103 /// "Tolerance<V>".104 ///105 /// \see BellmanFordDefaultOperationTraits106 #ifdef DOXYGEN107 template <typename V, V eps>108 #else109 template <110 typename V,111 V eps = Tolerance<V>::def_epsilon>112 #endif113 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 than129 /// the second.130 static bool less(const Value& left, const Value& right) {131 return left + eps < right;132 84 } 133 85 }; … … 156 108 /// It defines the used operations and the infinity value for the 157 109 /// given \c Value type. 158 /// \see BellmanFordDefaultOperationTraits, 159 /// BellmanFordToleranceOperationTraits 110 /// \see BellmanFordDefaultOperationTraits 160 111 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 161 112 … … 887 838 /// It defines the used operations and the infinity value for the 888 839 /// given \c Value type. 889 /// \see BellmanFordDefaultOperationTraits, 890 /// BellmanFordToleranceOperationTraits 840 /// \see BellmanFordDefaultOperationTraits 891 841 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 892 842 -
test/bellman_ford_test.cc
r956 r960 105 105 ::SetDistMap<concepts::ReadWriteMap<Node,Value> > 106 106 ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> > 107 ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >108 107 ::Create bf_test(gr,length); 109 108
Note: See TracChangeset
for help on using the changeset viewer.