r939:a6eb9698c321
Fri, 19 Feb 2010 14:08:32
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -23,34 +23,37 @@ |
| 23 | 23 |
/// \file |
| 24 | 24 |
/// \brief Bellman-Ford algorithm. |
| 25 | 25 |
|
| 26 | 26 |
#include <lemon/list_graph.h> |
| 27 | 27 |
#include <lemon/bits/path_dump.h> |
| 28 | 28 |
#include <lemon/core.h> |
| 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 |
|
| 33 | 34 |
#include <limits> |
| 34 | 35 |
|
| 35 | 36 |
namespace lemon {
|
| 36 | 37 |
|
| 37 |
/// \brief Default |
|
| 38 |
/// \brief Default operation traits for the BellmanFord algorithm class. |
|
| 38 | 39 |
/// |
| 39 | 40 |
/// This operation traits class defines all computational operations |
| 40 | 41 |
/// and constants that are used in the Bellman-Ford algorithm. |
| 41 | 42 |
/// The default implementation is based on the \c numeric_limits class. |
| 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 |
/// \ |
|
| 51 |
/// \brief Value type for the algorithm. |
|
| 49 | 52 |
typedef V Value; |
| 50 | 53 |
/// \brief Gives back the zero value of the type. |
| 51 | 54 |
static Value zero() {
|
| 52 | 55 |
return static_cast<Value>(0); |
| 53 | 56 |
} |
| 54 | 57 |
/// \brief Gives back the positive infinity value of the type. |
| 55 | 58 |
static Value infinity() {
|
| 56 | 59 |
return std::numeric_limits<Value>::infinity(); |
| ... | ... |
@@ -79,16 +82,61 @@ |
| 79 | 82 |
if (left == infinity() || right == infinity()) return infinity(); |
| 80 | 83 |
return left + right; |
| 81 | 84 |
} |
| 82 | 85 |
static bool less(const Value& left, const Value& right) {
|
| 83 | 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 | 135 |
/// \brief Default traits class of BellmanFord class. |
| 88 | 136 |
/// |
| 89 | 137 |
/// Default traits class of BellmanFord class. |
| 90 | 138 |
/// \param GR The type of the digraph. |
| 91 | 139 |
/// \param LEN The type of the length map. |
| 92 | 140 |
template<typename GR, typename LEN> |
| 93 | 141 |
struct BellmanFordDefaultTraits {
|
| 94 | 142 |
/// The type of the digraph the algorithm runs on. |
| ... | ... |
@@ -102,17 +150,18 @@ |
| 102 | 150 |
|
| 103 | 151 |
/// The type of the arc lengths. |
| 104 | 152 |
typedef typename LEN::Value Value; |
| 105 | 153 |
|
| 106 | 154 |
/// \brief Operation traits for Bellman-Ford algorithm. |
| 107 | 155 |
/// |
| 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 |
|
| 113 | 162 |
/// \brief The type of the map that stores the last arcs of the |
| 114 | 163 |
/// shortest paths. |
| 115 | 164 |
/// |
| 116 | 165 |
/// The type of the map that stores the last |
| 117 | 166 |
/// arcs of the shortest paths. |
| 118 | 167 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
| ... | ... |
@@ -832,17 +881,18 @@ |
| 832 | 881 |
|
| 833 | 882 |
/// The type of the arc lengths. |
| 834 | 883 |
typedef typename LEN::Value Value; |
| 835 | 884 |
|
| 836 | 885 |
/// \brief Operation traits for Bellman-Ford algorithm. |
| 837 | 886 |
/// |
| 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 |
|
| 843 | 893 |
/// \brief The type of the map that stores the last |
| 844 | 894 |
/// arcs of the shortest paths. |
| 845 | 895 |
/// |
| 846 | 896 |
/// The type of the map that stores the last arcs of the shortest paths. |
| 847 | 897 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
| 848 | 898 |
typedef typename GR::template NodeMap<typename GR::Arc> PredMap; |
| ... | ... |
@@ -99,16 +99,17 @@ |
| 99 | 99 |
pp = const_bf_test.negativeCycle(); |
| 100 | 100 |
|
| 101 | 101 |
for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
|
| 102 | 102 |
} |
| 103 | 103 |
{
|
| 104 | 104 |
BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
| 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 |
|
| 109 | 110 |
LengthMap length_map; |
| 110 | 111 |
concepts::ReadWriteMap<Node,Arc> pred_map; |
| 111 | 112 |
concepts::ReadWriteMap<Node,Value> dist_map; |
| 112 | 113 |
|
| 113 | 114 |
bf_test |
| 114 | 115 |
.lengthMap(length_map) |
0 comments (0 inline)