r968:b89e46862dc2
Thu, 18 Mar 2010 14:17:03
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -25,33 +25,30 @@ |
| 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> |
|
| 32 | 31 |
#include <lemon/path.h> |
| 33 | 32 |
|
| 34 | 33 |
#include <limits> |
| 35 | 34 |
|
| 36 | 35 |
namespace lemon {
|
| 37 | 36 |
|
| 38 |
/// \brief Default |
|
| 37 |
/// \brief Default OperationTraits for the BellmanFord algorithm class. |
|
| 39 | 38 |
/// |
| 40 | 39 |
/// This operation traits class defines all computational operations |
| 41 | 40 |
/// and constants that are used in the Bellman-Ford algorithm. |
| 42 | 41 |
/// The default implementation is based on the \c numeric_limits class. |
| 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 BellmanFordToleranceOperationTraits |
|
| 47 | 44 |
template < |
| 48 | 45 |
typename V, |
| 49 | 46 |
bool has_inf = std::numeric_limits<V>::has_infinity> |
| 50 | 47 |
struct BellmanFordDefaultOperationTraits {
|
| 51 |
/// \ |
|
| 48 |
/// \e |
|
| 52 | 49 |
typedef V Value; |
| 53 | 50 |
/// \brief Gives back the zero value of the type. |
| 54 | 51 |
static Value zero() {
|
| 55 | 52 |
return static_cast<Value>(0); |
| 56 | 53 |
} |
| 57 | 54 |
/// \brief Gives back the positive infinity value of the type. |
| ... | ... |
@@ -84,57 +81,12 @@ |
| 84 | 81 |
} |
| 85 | 82 |
static bool less(const Value& left, const Value& right) {
|
| 86 | 83 |
return left < right; |
| 87 | 84 |
} |
| 88 | 85 |
}; |
| 89 | 86 |
|
| 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 |
|
|
| 135 | 87 |
/// \brief Default traits class of BellmanFord class. |
| 136 | 88 |
/// |
| 137 | 89 |
/// Default traits class of BellmanFord class. |
| 138 | 90 |
/// \param GR The type of the digraph. |
| 139 | 91 |
/// \param LEN The type of the length map. |
| 140 | 92 |
template<typename GR, typename LEN> |
| ... | ... |
@@ -152,14 +104,13 @@ |
| 152 | 104 |
typedef typename LEN::Value Value; |
| 153 | 105 |
|
| 154 | 106 |
/// \brief Operation traits for Bellman-Ford algorithm. |
| 155 | 107 |
/// |
| 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 |
|
| 162 | 113 |
/// \brief The type of the map that stores the last arcs of the |
| 163 | 114 |
/// shortest paths. |
| 164 | 115 |
/// |
| 165 | 116 |
/// The type of the map that stores the last |
| ... | ... |
@@ -883,14 +834,13 @@ |
| 883 | 834 |
typedef typename LEN::Value Value; |
| 884 | 835 |
|
| 885 | 836 |
/// \brief Operation traits for Bellman-Ford algorithm. |
| 886 | 837 |
/// |
| 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 |
|
| 893 | 843 |
/// \brief The type of the map that stores the last |
| 894 | 844 |
/// arcs of the shortest paths. |
| 895 | 845 |
/// |
| 896 | 846 |
/// The type of the map that stores the last arcs of the shortest paths. |
| ... | ... |
@@ -101,13 +101,12 @@ |
| 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> > |
|
| 108 | 107 |
::Create bf_test(gr,length); |
| 109 | 108 |
|
| 110 | 109 |
LengthMap length_map; |
| 111 | 110 |
concepts::ReadWriteMap<Node,Arc> pred_map; |
| 112 | 111 |
concepts::ReadWriteMap<Node,Value> dist_map; |
| 113 | 112 |
|
0 comments (0 inline)