26 #include <lemon/list_graph.h> |
26 #include <lemon/list_graph.h> |
27 #include <lemon/bits/path_dump.h> |
27 #include <lemon/bits/path_dump.h> |
28 #include <lemon/core.h> |
28 #include <lemon/core.h> |
29 #include <lemon/error.h> |
29 #include <lemon/error.h> |
30 #include <lemon/maps.h> |
30 #include <lemon/maps.h> |
31 #include <lemon/tolerance.h> |
|
32 #include <lemon/path.h> |
31 #include <lemon/path.h> |
33 |
32 |
34 #include <limits> |
33 #include <limits> |
35 |
34 |
36 namespace lemon { |
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 /// This operation traits class defines all computational operations |
39 /// This operation traits class defines all computational operations |
41 /// and constants that are used in the Bellman-Ford algorithm. |
40 /// and constants that are used in the Bellman-Ford algorithm. |
42 /// The default implementation is based on the \c numeric_limits class. |
41 /// The default implementation is based on the \c numeric_limits class. |
43 /// If the numeric type does not have infinity value, then the maximum |
42 /// If the numeric type does not have infinity value, then the maximum |
44 /// value is used as extremal infinity value. |
43 /// value is used as extremal infinity value. |
45 /// |
|
46 /// \see BellmanFordToleranceOperationTraits |
|
47 template < |
44 template < |
48 typename V, |
45 typename V, |
49 bool has_inf = std::numeric_limits<V>::has_infinity> |
46 bool has_inf = std::numeric_limits<V>::has_infinity> |
50 struct BellmanFordDefaultOperationTraits { |
47 struct BellmanFordDefaultOperationTraits { |
51 /// \brief Value type for the algorithm. |
48 /// \e |
52 typedef V Value; |
49 typedef V Value; |
53 /// \brief Gives back the zero value of the type. |
50 /// \brief Gives back the zero value of the type. |
54 static Value zero() { |
51 static Value zero() { |
55 return static_cast<Value>(0); |
52 return static_cast<Value>(0); |
56 } |
53 } |
82 if (left == infinity() || right == infinity()) return infinity(); |
79 if (left == infinity() || right == infinity()) return infinity(); |
83 return left + right; |
80 return left + right; |
84 } |
81 } |
85 static bool less(const Value& left, const Value& right) { |
82 static bool less(const Value& left, const Value& right) { |
86 return left < right; |
83 return left < right; |
87 } |
|
88 }; |
|
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 } |
84 } |
133 }; |
85 }; |
134 |
86 |
135 /// \brief Default traits class of BellmanFord class. |
87 /// \brief Default traits class of BellmanFord class. |
136 /// |
88 /// |
153 |
105 |
154 /// \brief Operation traits for Bellman-Ford algorithm. |
106 /// \brief Operation traits for Bellman-Ford algorithm. |
155 /// |
107 /// |
156 /// It defines the used operations and the infinity value for the |
108 /// It defines the used operations and the infinity value for the |
157 /// given \c Value type. |
109 /// given \c Value type. |
158 /// \see BellmanFordDefaultOperationTraits, |
110 /// \see BellmanFordDefaultOperationTraits |
159 /// BellmanFordToleranceOperationTraits |
|
160 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
111 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
161 |
112 |
162 /// \brief The type of the map that stores the last arcs of the |
113 /// \brief The type of the map that stores the last arcs of the |
163 /// shortest paths. |
114 /// shortest paths. |
164 /// |
115 /// |
884 |
835 |
885 /// \brief Operation traits for Bellman-Ford algorithm. |
836 /// \brief Operation traits for Bellman-Ford algorithm. |
886 /// |
837 /// |
887 /// It defines the used operations and the infinity value for the |
838 /// It defines the used operations and the infinity value for the |
888 /// given \c Value type. |
839 /// given \c Value type. |
889 /// \see BellmanFordDefaultOperationTraits, |
840 /// \see BellmanFordDefaultOperationTraits |
890 /// BellmanFordToleranceOperationTraits |
|
891 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
841 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
892 |
842 |
893 /// \brief The type of the map that stores the last |
843 /// \brief The type of the map that stores the last |
894 /// arcs of the shortest paths. |
844 /// arcs of the shortest paths. |
895 /// |
845 /// |