Changeset - r844:a6eb9698c321
« 836:c841ae
878:d6052a »
845:a5fc1e »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
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.
0 2 0
default
2 files changed with 55 insertions and 4 deletions:
lemon/bellman_ford.h
54
4
test/bellman_ford_test.cc
1
↑ Collapse diff ↑
lemon/bellman_ford.h
Ignore white space 12 line context
... ... 
@@ -25,30 +25,33 @@
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 OperationTraits for the BellmanFord algorithm class.


			




	
	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
	
	
		
    /// \e


			




	
	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.


			




	...
	...
	
		
@@ -81,12 +84,57 @@


			




	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>


			




	...
	...
	
		
@@ -104,13 +152,14 @@


			




	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


			




	...
	...
	
		
@@ -834,13 +883,14 @@


			




	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.

			




        

    

    

    

        

            

                

                    test/bellman_ford_test.cc
                

                

                  
                  
                  
                  Ignore white space
                  12 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -101,12 +101,13 @@


			




	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
	
		
    


			




        

    






    
    



    


    

     
    
0 comments (0 inline)