Changeset - r878:d6052a9c4e8d
« 844:a6eb96
880:b89e46 »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Backed out changeset a6eb9698c321 (#360, #51)
0 2 0
default
2 files changed with 4 insertions and 55 deletions:
lemon/bellman_ford.h
4
54
test/bellman_ford_test.cc
1
↑ Collapse diff ↑
lemon/bellman_ford.h
Ignore white space 12 line context
... ... 
@@ -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 operation traits for the BellmanFord algorithm class.


			




	
	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
	
	
		
    /// \brief Value type for the algorithm.


			




	
	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.

			




        

    

    

    

        

            

                

                    test/bellman_ford_test.cc
                

                

                  
                  
                  
                  Ignore white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -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)