lemon/bellman_ford.h
changeset 858 9f6ed854d409
parent 825 75e6020b19b1
child 877 141f9c0db4a3
child 878 d6052a9c4e8d
equal deleted inserted replaced
7:8a846e759b5e 8:ad1fe6c84fef
    26 #include <lemon/list_graph.h>
    26 #include <lemon/list_graph.h>
    27 #include <lemon/bits/path_dump.h>
    27 #include <lemon/bits/path_dump.h>
    28 #include <lemon/core.h>
    28 #include <lemon/core.h>
    29 #include <lemon/error.h>
    29 #include <lemon/error.h>
    30 #include <lemon/maps.h>
    30 #include <lemon/maps.h>
       
    31 #include <lemon/tolerance.h>
    31 #include <lemon/path.h>
    32 #include <lemon/path.h>
    32 
    33 
    33 #include <limits>
    34 #include <limits>
    34 
    35 
    35 namespace lemon {
    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   /// This operation traits class defines all computational operations
    40   /// This operation traits class defines all computational operations
    40   /// and constants that are used in the Bellman-Ford algorithm.
    41   /// and constants that are used in the Bellman-Ford algorithm.
    41   /// The default implementation is based on the \c numeric_limits class.
    42   /// The default implementation is based on the \c numeric_limits class.
    42   /// If the numeric type does not have infinity value, then the maximum
    43   /// If the numeric type does not have infinity value, then the maximum
    43   /// value is used as extremal infinity value.
    44   /// value is used as extremal infinity value.
       
    45   ///
       
    46   /// \see BellmanFordToleranceOperationTraits
    44   template <
    47   template <
    45     typename V, 
    48     typename V, 
    46     bool has_inf = std::numeric_limits<V>::has_infinity>
    49     bool has_inf = std::numeric_limits<V>::has_infinity>
    47   struct BellmanFordDefaultOperationTraits {
    50   struct BellmanFordDefaultOperationTraits {
    48     /// \e
    51     /// \brief Value type for the algorithm.
    49     typedef V Value;
    52     typedef V Value;
    50     /// \brief Gives back the zero value of the type.
    53     /// \brief Gives back the zero value of the type.
    51     static Value zero() {
    54     static Value zero() {
    52       return static_cast<Value>(0);
    55       return static_cast<Value>(0);
    53     }
    56     }
    82     static bool less(const Value& left, const Value& right) {
    85     static bool less(const Value& left, const Value& right) {
    83       return left < right;
    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   /// \brief Default traits class of BellmanFord class.
   135   /// \brief Default traits class of BellmanFord class.
    88   ///
   136   ///
    89   /// Default traits class of BellmanFord class.
   137   /// Default traits class of BellmanFord class.
    90   /// \param GR The type of the digraph.
   138   /// \param GR The type of the digraph.
    91   /// \param LEN The type of the length map.
   139   /// \param LEN The type of the length map.
   105 
   153 
   106     /// \brief Operation traits for Bellman-Ford algorithm.
   154     /// \brief Operation traits for Bellman-Ford algorithm.
   107     ///
   155     ///
   108     /// It defines the used operations and the infinity value for the
   156     /// It defines the used operations and the infinity value for the
   109     /// given \c Value type.
   157     /// given \c Value type.
   110     /// \see BellmanFordDefaultOperationTraits
   158     /// \see BellmanFordDefaultOperationTraits,
       
   159     /// BellmanFordToleranceOperationTraits
   111     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   160     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   112  
   161  
   113     /// \brief The type of the map that stores the last arcs of the 
   162     /// \brief The type of the map that stores the last arcs of the 
   114     /// shortest paths.
   163     /// shortest paths.
   115     /// 
   164     /// 
   835 
   884 
   836     /// \brief Operation traits for Bellman-Ford algorithm.
   885     /// \brief Operation traits for Bellman-Ford algorithm.
   837     ///
   886     ///
   838     /// It defines the used operations and the infinity value for the
   887     /// It defines the used operations and the infinity value for the
   839     /// given \c Value type.
   888     /// given \c Value type.
   840     /// \see BellmanFordDefaultOperationTraits
   889     /// \see BellmanFordDefaultOperationTraits,
       
   890     /// BellmanFordToleranceOperationTraits
   841     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   891     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   842 
   892 
   843     /// \brief The type of the map that stores the last
   893     /// \brief The type of the map that stores the last
   844     /// arcs of the shortest paths.
   894     /// arcs of the shortest paths.
   845     /// 
   895     ///