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