author Peter Kovacs Fri, 19 Feb 2010 14:08:32 +0100 changeset 844 a6eb9698c321 parent 836 c841ae1aca29 child 845 a5fc1e1e5039 child 879 d6052a9c4e8d
Support tolerance technique for BellmanFord (#51)

A new operation traits class BellmanFordToleranceOperationTraits
is introduced, which uses the tolerance technique in its less()
function. This class can be used with the SetOperationTraits
named template parameter.
 lemon/bellman_ford.h file | annotate | diff | comparison | revisions test/bellman_ford_test.cc file | annotate | diff | comparison | revisions
     1.1 --- a/lemon/bellman_ford.h	Wed Feb 17 23:10:36 2010 +0100
1.2 +++ b/lemon/bellman_ford.h	Fri Feb 19 14:08:32 2010 +0100
1.3 @@ -28,24 +28,27 @@
1.4  #include <lemon/core.h>
1.5  #include <lemon/error.h>
1.6  #include <lemon/maps.h>
1.7 +#include <lemon/tolerance.h>
1.8  #include <lemon/path.h>
1.9
1.10  #include <limits>
1.11
1.12  namespace lemon {
1.13
1.14 -  /// \brief Default OperationTraits for the BellmanFord algorithm class.
1.15 +  /// \brief Default operation traits for the BellmanFord algorithm class.
1.16    ///
1.17    /// This operation traits class defines all computational operations
1.18    /// and constants that are used in the Bellman-Ford algorithm.
1.19    /// The default implementation is based on the \c numeric_limits class.
1.20    /// If the numeric type does not have infinity value, then the maximum
1.21    /// value is used as extremal infinity value.
1.22 +  ///
1.23 +  /// \see BellmanFordToleranceOperationTraits
1.24    template <
1.25      typename V,
1.26      bool has_inf = std::numeric_limits<V>::has_infinity>
1.27    struct BellmanFordDefaultOperationTraits {
1.28 -    /// \e
1.29 +    /// \brief Value type for the algorithm.
1.30      typedef V Value;
1.31      /// \brief Gives back the zero value of the type.
1.32      static Value zero() {
1.33 @@ -84,6 +87,51 @@
1.34      }
1.35    };
1.36
1.37 +  /// \brief Operation traits for the BellmanFord algorithm class
1.38 +  /// using tolerance.
1.39 +  ///
1.40 +  /// This operation traits class defines all computational operations
1.41 +  /// and constants that are used in the Bellman-Ford algorithm.
1.42 +  /// The only difference between this implementation and
1.43 +  /// \ref BellmanFordDefaultOperationTraits is that this class uses
1.44 +  /// the \ref Tolerance "tolerance technique" in its \ref less()
1.45 +  /// function.
1.46 +  ///
1.47 +  /// \tparam V The value type.
1.48 +  /// \tparam eps The epsilon value for the \ref less() function.
1.49 +  /// By default, it is the epsilon value used by \ref Tolerance
1.50 +  /// "Tolerance<V>".
1.51 +  ///
1.52 +  /// \see BellmanFordDefaultOperationTraits
1.53 +#ifdef DOXYGEN
1.54 +  template <typename V, V eps>
1.55 +#else
1.56 +  template <
1.57 +    typename V,
1.58 +    V eps = Tolerance<V>::def_epsilon>
1.59 +#endif
1.60 +  struct BellmanFordToleranceOperationTraits {
1.61 +    /// \brief Value type for the algorithm.
1.62 +    typedef V Value;
1.63 +    /// \brief Gives back the zero value of the type.
1.64 +    static Value zero() {
1.65 +      return static_cast<Value>(0);
1.66 +    }
1.67 +    /// \brief Gives back the positive infinity value of the type.
1.68 +    static Value infinity() {
1.69 +      return std::numeric_limits<Value>::infinity();
1.70 +    }
1.71 +    /// \brief Gives back the sum of the given two elements.
1.72 +    static Value plus(const Value& left, const Value& right) {
1.73 +      return left + right;
1.74 +    }
1.75 +    /// \brief Gives back \c true only if the first value is less than
1.76 +    /// the second.
1.77 +    static bool less(const Value& left, const Value& right) {
1.78 +      return left + eps < right;
1.79 +    }
1.80 +  };
1.81 +
1.82    /// \brief Default traits class of BellmanFord class.
1.83    ///
1.84    /// Default traits class of BellmanFord class.
1.85 @@ -107,7 +155,8 @@
1.86      ///
1.87      /// It defines the used operations and the infinity value for the
1.88      /// given \c Value type.
1.89 -    /// \see BellmanFordDefaultOperationTraits
1.90 +    /// \see BellmanFordDefaultOperationTraits,
1.91 +    /// BellmanFordToleranceOperationTraits
1.92      typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.93
1.94      /// \brief The type of the map that stores the last arcs of the
1.95 @@ -837,7 +886,8 @@
1.96      ///
1.97      /// It defines the used operations and the infinity value for the
1.98      /// given \c Value type.
1.99 -    /// \see BellmanFordDefaultOperationTraits
1.100 +    /// \see BellmanFordDefaultOperationTraits,
1.101 +    /// BellmanFordToleranceOperationTraits
1.102      typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.103
1.104      /// \brief The type of the map that stores the last

     2.1 --- a/test/bellman_ford_test.cc	Wed Feb 17 23:10:36 2010 +0100
2.2 +++ b/test/bellman_ford_test.cc	Fri Feb 19 14:08:32 2010 +0100
2.3 @@ -104,6 +104,7 @@