Merge backout of a6eb9698c321 (#360,#51)
authorAlpar Juttner <alpar@cs.elte.hu>
Thu, 18 Mar 2010 14:17:03 +0100
changeset 880b89e46862dc2
parent 879 38213abd2911
parent 878 d6052a9c4e8d
child 881 87569cb5734d
Merge backout of a6eb9698c321 (#360,#51)
lemon/bellman_ford.h
test/bellman_ford_test.cc
     1.1 --- a/lemon/bellman_ford.h	Thu Mar 18 00:30:25 2010 +0100
     1.2 +++ b/lemon/bellman_ford.h	Thu Mar 18 14:17:03 2010 +0100
     1.3 @@ -28,27 +28,24 @@
     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 operation traits for the BellmanFord algorithm class.
    1.15 +  /// \brief Default OperationTraits 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 -    /// \brief Value type for the algorithm.
    1.29 +    /// \e
    1.30      typedef V Value;
    1.31      /// \brief Gives back the zero value of the type.
    1.32      static Value zero() {
    1.33 @@ -87,51 +84,6 @@
    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 @@ -155,8 +107,7 @@
    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 -    /// BellmanFordToleranceOperationTraits
    1.91 +    /// \see BellmanFordDefaultOperationTraits
    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 @@ -886,8 +837,7 @@
    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 -    /// BellmanFordToleranceOperationTraits
   1.101 +    /// \see BellmanFordDefaultOperationTraits
   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	Thu Mar 18 00:30:25 2010 +0100
     2.2 +++ b/test/bellman_ford_test.cc	Thu Mar 18 14:17:03 2010 +0100
     2.3 @@ -104,7 +104,6 @@
     2.4      BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
     2.5        ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
     2.6        ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
     2.7 -      ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
     2.8        ::Create bf_test(gr,length);
     2.9  
    2.10      LengthMap length_map;