COIN-OR::LEMON - Graph Library

Changeset 917:a6eb9698c321 in lemon


Ignore:
Timestamp:
02/19/10 14:08:32 (14 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
918:a5fc1e1e5039, 958:d6052a9c4e8d
Phase:
public
Message:

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.

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/bellman_ford.h

    r891 r917  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
     31#include <lemon/tolerance.h>
    3132#include <lemon/path.h>
    3233
     
    3536namespace lemon {
    3637
    37   /// \brief Default OperationTraits for the BellmanFord algorithm class.
     38  /// \brief Default operation traits for the BellmanFord algorithm class.
    3839  /// 
    3940  /// This operation traits class defines all computational operations
     
    4243  /// If the numeric type does not have infinity value, then the maximum
    4344  /// value is used as extremal infinity value.
     45  ///
     46  /// \see BellmanFordToleranceOperationTraits
    4447  template <
    4548    typename V,
    4649    bool has_inf = std::numeric_limits<V>::has_infinity>
    4750  struct BellmanFordDefaultOperationTraits {
    48     /// \e
     51    /// \brief Value type for the algorithm.
    4952    typedef V Value;
    5053    /// \brief Gives back the zero value of the type.
     
    8588  };
    8689 
     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
    87135  /// \brief Default traits class of BellmanFord class.
    88136  ///
     
    108156    /// It defines the used operations and the infinity value for the
    109157    /// given \c Value type.
    110     /// \see BellmanFordDefaultOperationTraits
     158    /// \see BellmanFordDefaultOperationTraits,
     159    /// BellmanFordToleranceOperationTraits
    111160    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    112161 
     
    838887    /// It defines the used operations and the infinity value for the
    839888    /// given \c Value type.
    840     /// \see BellmanFordDefaultOperationTraits
     889    /// \see BellmanFordDefaultOperationTraits,
     890    /// BellmanFordToleranceOperationTraits
    841891    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    842892
  • test/bellman_ford_test.cc

    r838 r917  
    105105      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
    106106      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
     107      ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
    107108      ::Create bf_test(gr,length);
    108109
Note: See TracChangeset for help on using the changeset viewer.