Changeset 880:b89e46862dc2 in lemon-main

Timestamp:

03/18/10 14:17:03 (15 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

879:38213abd2911 (diff), 878:d6052a9c4e8d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge backout of a6eb9698c321 (#360,#51)

Files:

• lemon/bellman_ford.h (modified) (56 diffs)
• lemon/bellman_ford.h (modified) (6 diffs)
• test/bellman_ford_test.cc (modified) (7 diffs)
• test/bellman_ford_test.cc (modified) (1 diff)

lemon/bellman_ford.h

@@ -1 @@
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
  *
- * This file is a part of LEMON, a generic C++ optimization library
+ * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -36 +36 @@
 
   /// \brief Default OperationTraits for the BellmanFord algorithm class.
-  ///  
+  ///
   /// This operation traits class defines all computational operations
   /// and constants that are used in the Bellman-Ford algorithm.
@@ -43 +43 @@
   /// value is used as extremal infinity value.
   template <
-    typename V, 
+    typename V,
     bool has_inf = std::numeric_limits<V>::has_infinity>
   struct BellmanFordDefaultOperationTraits {
@@ -84 +84 @@
     }
   };
-  
+
   /// \brief Default traits class of BellmanFord class.
   ///
@@ -92 +92 @@
   template<typename GR, typename LEN>
   struct BellmanFordDefaultTraits {
-    /// The type of the digraph the algorithm runs on. 
+    /// The type of the digraph the algorithm runs on.
     typedef GR Digraph;
 
@@ -110 +110 @@
     /// \see BellmanFordDefaultOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
- 
-    /// \brief The type of the map that stores the last arcs of the 
+
+    /// \brief The type of the map that stores the last arcs of the
     /// shortest paths.
-    /// 
+    ///
     /// The type of the map that stores the last
     /// arcs of the shortest paths.
@@ -120 +120 @@
 
     /// \brief Instantiates a \c PredMap.
-    /// 
-    /// This function instantiates a \ref PredMap. 
+    ///
+    /// This function instantiates a \ref PredMap.
     /// \param g is the digraph to which we would like to define the
     /// \ref PredMap.
@@ -136 +136 @@
     /// \brief Instantiates a \c DistMap.
     ///
-    /// This function instantiates a \ref DistMap. 
-    /// \param g is the digraph to which we would like to define the 
+    /// This function instantiates a \ref DistMap.
+    /// \param g is the digraph to which we would like to define the
     /// \ref DistMap.
     static DistMap *createDistMap(const GR& g) {
@@ -144 +144 @@
 
   };
-  
+
   /// \brief %BellmanFord algorithm class.
   ///
   /// \ingroup shortest_path
-  /// This class provides an efficient implementation of the Bellman-Ford 
+  /// This class provides an efficient implementation of the Bellman-Ford
   /// algorithm. The maximum time complexity of the algorithm is
   /// <tt>O(ne)</tt>.
@@ -159 +159 @@
   ///
   /// The arc lengths are passed to the algorithm using a
-  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
+  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
   /// kind of length. The type of the length values is determined by the
   /// \ref concepts::ReadMap::Value "Value" type of the length map.
@@ -189 +189 @@
     ///The type of the underlying digraph.
     typedef typename TR::Digraph Digraph;
-    
+
     /// \brief The type of the arc lengths.
     typedef typename TR::LengthMap::Value Value;
@@ -236 +236 @@
     void create_maps() {
       if(!_pred) {
-        _local_pred = true;
-        _pred = Traits::createPredMap(*_gr);
+        _local_pred = true;
+        _pred = Traits::createPredMap(*_gr);
       }
       if(!_dist) {
-        _local_dist = true;
-        _dist = Traits::createDistMap(*_gr);
+        _local_dist = true;
+        _dist = Traits::createDistMap(*_gr);
       }
       if(!_mask) {
@@ -247 +247 @@
       }
     }
-    
+
   public :
- 
+
     typedef BellmanFord Create;
 
@@ -272 +272 @@
     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
-    struct SetPredMap 
+    struct SetPredMap
       : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
       typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
     };
-    
+
     template <class T>
     struct SetDistMapTraits : public Traits {
@@ -293 +293 @@
     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
-    struct SetDistMap 
+    struct SetDistMap
       : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
       typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
@@ -302 +302 @@
       typedef T OperationTraits;
     };
-    
-    /// \brief \ref named-templ-param "Named parameter" for setting 
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
     /// \c OperationTraits type.
     ///
@@ -315 +315 @@
       Create;
     };
-    
+
     ///@}
 
   protected:
-    
+
     BellmanFord() {}
 
-  public:      
-    
+  public:
+
     /// \brief Constructor.
     ///
@@ -333 +333 @@
       _pred(0), _local_pred(false),
       _dist(0), _local_dist(false), _mask(0) {}
-    
+
     ///Destructor.
     ~BellmanFord() {
@@ -360 +360 @@
     BellmanFord &predMap(PredMap &map) {
       if(_local_pred) {
-        delete _pred;
-        _local_pred=false;
+        delete _pred;
+        _local_pred=false;
       }
       _pred = &map;
@@ -378 +378 @@
     BellmanFord &distMap(DistMap &map) {
       if(_local_dist) {
-        delete _dist;
-        _local_dist=false;
+        delete _dist;
+        _local_dist=false;
       }
       _dist = &map;
@@ -397 +397 @@
 
     /// \brief Initializes the internal data structures.
-    /// 
+    ///
     /// Initializes the internal data structures. The optional parameter
     /// is the initial distance of each node.
@@ -403 +403 @@
       create_maps();
       for (NodeIt it(*_gr); it != INVALID; ++it) {
-        _pred->set(it, INVALID);
-        _dist->set(it, value);
+        _pred->set(it, INVALID);
+        _dist->set(it, value);
       }
       _process.clear();
       if (OperationTraits::less(value, OperationTraits::infinity())) {
-        for (NodeIt it(*_gr); it != INVALID; ++it) {
-          _process.push_back(it);
-          _mask->set(it, true);
-        }
+        for (NodeIt it(*_gr); it != INVALID; ++it) {
+          _process.push_back(it);
+          _mask->set(it, true);
+        }
       } else {
-        for (NodeIt it(*_gr); it != INVALID; ++it) {
-          _mask->set(it, false);
-        }
-      }
-    }
-    
+        for (NodeIt it(*_gr); it != INVALID; ++it) {
+          _mask->set(it, false);
+        }
+      }
+    }
+
     /// \brief Adds a new source node.
     ///
@@ -426 +426 @@
       _dist->set(source, dst);
       if (!(*_mask)[source]) {
-        _process.push_back(source);
-        _mask->set(source, true);
+        _process.push_back(source);
+        _mask->set(source, true);
       }
     }
@@ -452 +452 @@
     bool processNextRound() {
       for (int i = 0; i < int(_process.size()); ++i) {
-        _mask->set(_process[i], false);
+        _mask->set(_process[i], false);
       }
       std::vector<Node> nextProcess;
       std::vector<Value> values(_process.size());
       for (int i = 0; i < int(_process.size()); ++i) {
-        values[i] = (*_dist)[_process[i]];
+        values[i] = (*_dist)[_process[i]];
       }
       for (int i = 0; i < int(_process.size()); ++i) {
-        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
-          Node target = _gr->target(it);
-          Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
-          if (OperationTraits::less(relaxed, (*_dist)[target])) {
-            _pred->set(target, it);
-            _dist->set(target, relaxed);
-            if (!(*_mask)[target]) {
-              _mask->set(target, true);
-              nextProcess.push_back(target);
-            }
-          }       
-        }
+        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+          Node target = _gr->target(it);
+          Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
+          if (OperationTraits::less(relaxed, (*_dist)[target])) {
+            _pred->set(target, it);
+            _dist->set(target, relaxed);
+            if (!(*_mask)[target]) {
+              _mask->set(target, true);
+              nextProcess.push_back(target);
+            }
+          }
+        }
       }
       _process.swap(nextProcess);
@@ -493 +493 @@
     bool processNextWeakRound() {
       for (int i = 0; i < int(_process.size()); ++i) {
-        _mask->set(_process[i], false);
+        _mask->set(_process[i], false);
       }
       std::vector<Node> nextProcess;
       for (int i = 0; i < int(_process.size()); ++i) {
-        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
-          Node target = _gr->target(it);
-          Value relaxed = 
-            OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
-          if (OperationTraits::less(relaxed, (*_dist)[target])) {
-            _pred->set(target, it);
-            _dist->set(target, relaxed);
-            if (!(*_mask)[target]) {
-              _mask->set(target, true);
-              nextProcess.push_back(target);
-            }
-          }       
-        }
+        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+          Node target = _gr->target(it);
+          Value relaxed =
+            OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
+          if (OperationTraits::less(relaxed, (*_dist)[target])) {
+            _pred->set(target, it);
+            _dist->set(target, relaxed);
+            if (!(*_mask)[target]) {
+              _mask->set(target, true);
+              nextProcess.push_back(target);
+            }
+          }
+        }
       }
       _process.swap(nextProcess);
@@ -531 +531 @@
       int num = countNodes(*_gr) - 1;
       for (int i = 0; i < num; ++i) {
-        if (processNextWeakRound()) break;
+        if (processNextWeakRound()) break;
       }
     }
@@ -543 +543 @@
     /// if the digraph contains cycles with negative total length.
     ///
-    /// The algorithm computes 
+    /// The algorithm computes
     /// - the shortest path tree (forest),
     /// - the distance of each node from the root(s).
-    /// 
+    ///
     /// \return \c false if there is a negative cycle in the digraph.
     ///
     /// \pre init() must be called and at least one root node should be
-    /// added with addSource() before using this function. 
+    /// added with addSource() before using this function.
     bool checkedStart() {
       int num = countNodes(*_gr);
       for (int i = 0; i < num; ++i) {
-        if (processNextWeakRound()) return true;
+        if (processNextWeakRound()) return true;
       }
       return _process.empty();
@@ -578 +578 @@
     ///
     /// \pre init() must be called and at least one root node should be
-    /// added with addSource() before using this function. 
+    /// added with addSource() before using this function.
     void limitedStart(int num) {
       for (int i = 0; i < num; ++i) {
-        if (processNextRound()) break;
-      }
-    }
-    
+        if (processNextRound()) break;
+      }
+    }
+
     /// \brief Runs the algorithm from the given root node.
-    ///    
+    ///
     /// This method runs the Bellman-Ford algorithm from the given root
     /// node \c s in order to compute the shortest path to each node.
@@ -605 +605 @@
       start();
     }
-    
+
     /// \brief Runs the algorithm from the given root node with arc
     /// number limit.
-    ///    
+    ///
     /// This method runs the Bellman-Ford algorithm from the given root
     /// node \c s in order to compute the shortest path distance for each
@@ -634 +634 @@
       limitedStart(num);
     }
-    
+
     ///@}
 
@@ -649 +649 @@
       ///
       /// Constructor for getting the active nodes of the given BellmanFord
-      /// instance. 
+      /// instance.
       ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
       {
@@ -663 +663 @@
       ///
       /// Conversion to \c Node.
-      operator Node() const { 
+      operator Node() const {
         return _index >= 0 ? _algorithm->_process[_index] : INVALID;
       }
@@ -672 +672 @@
       ActiveIt& operator++() {
         --_index;
-        return *this; 
-      }
-
-      bool operator==(const ActiveIt& it) const { 
-        return static_cast<Node>(*this) == static_cast<Node>(it); 
-      }
-      bool operator!=(const ActiveIt& it) const { 
-        return static_cast<Node>(*this) != static_cast<Node>(it); 
-      }
-      bool operator<(const ActiveIt& it) const { 
-        return static_cast<Node>(*this) < static_cast<Node>(it); 
-      }
-      
+        return *this;
+      }
+
+      bool operator==(const ActiveIt& it) const {
+        return static_cast<Node>(*this) == static_cast<Node>(it);
+      }
+      bool operator!=(const ActiveIt& it) const {
+        return static_cast<Node>(*this) != static_cast<Node>(it);
+      }
+      bool operator<(const ActiveIt& it) const {
+        return static_cast<Node>(*this) < static_cast<Node>(it);
+      }
+
     private:
       const BellmanFord* _algorithm;
       int _index;
     };
-    
+
     /// \name Query Functions
     /// The result of the Bellman-Ford algorithm can be obtained using these
     /// functions.\n
     /// Either \ref run() or \ref init() should be called before using them.
-    
+
     ///@{
 
     /// \brief The shortest path to the given node.
-    ///    
+    ///
     /// Gives back the shortest path to the given node from the root(s).
     ///
@@ -709 +709 @@
       return Path(*_gr, *_pred, t);
     }
-          
+
     /// \brief The distance of the given node from the root(s).
     ///
@@ -749 +749 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    Node predNode(Node v) const { 
-      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
-    }
-    
+    Node predNode(Node v) const {
+      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
+    }
+
     /// \brief Returns a const reference to the node map that stores the
     /// distances of the nodes.
@@ -762 +762 @@
     /// using this function.
     const DistMap &distMap() const { return *_dist;}
- 
+
     /// \brief Returns a const reference to the node map that stores the
     /// predecessor arcs.
@@ -772 +772 @@
     /// using this function.
     const PredMap &predMap() const { return *_pred; }
- 
+
     /// \brief Checks if a node is reached from the root(s).
     ///
@@ -784 +784 @@
 
     /// \brief Gives back a negative cycle.
-    ///    
+    ///
     /// This function gives back a directed cycle with negative total
     /// length if the algorithm has already found one.
@@ -811 +811 @@
       return cycle;
     }
-    
+
     ///@}
   };
- 
+
   /// \brief Default traits class of bellmanFord() function.
   ///
@@ -822 +822 @@
   template <typename GR, typename LEN>
   struct BellmanFordWizardDefaultTraits {
-    /// The type of the digraph the algorithm runs on. 
+    /// The type of the digraph the algorithm runs on.
     typedef GR Digraph;
 
@@ -843 +843 @@
     /// \brief The type of the map that stores the last
     /// arcs of the shortest paths.
-    /// 
+    ///
     /// The type of the map that stores the last arcs of the shortest paths.
     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
@@ -849 +849 @@
 
     /// \brief Instantiates a \c PredMap.
-    /// 
+    ///
     /// This function instantiates a \ref PredMap.
     /// \param g is the digraph to which we would like to define the
@@ -865 +865 @@
     /// \brief Instantiates a \c DistMap.
     ///
-    /// This function instantiates a \ref DistMap. 
+    /// This function instantiates a \ref DistMap.
     /// \param g is the digraph to which we would like to define the
     /// \ref DistMap.
@@ -878 +878 @@
     typedef lemon::Path<Digraph> Path;
   };
-  
+
   /// \brief Default traits class used by BellmanFordWizard.
   ///
@@ -885 +885 @@
   /// \tparam LEN The type of the length map.
   template <typename GR, typename LEN>
-  class BellmanFordWizardBase 
+  class BellmanFordWizardBase
     : public BellmanFordWizardDefaultTraits<GR, LEN> {
 
@@ -908 +908 @@
     public:
     /// Constructor.
-    
+
     /// This constructor does not require parameters, it initiates
     /// all of the attributes to default values \c 0.
@@ -915 +915 @@
 
     /// Constructor.
-    
+
     /// This constructor requires two parameters,
     /// others are initiated to \c 0.
     /// \param gr The digraph the algorithm runs on.
     /// \param len The length map.
-    BellmanFordWizardBase(const GR& gr, 
-                          const LEN& len) :
-      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
-      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
+    BellmanFordWizardBase(const GR& gr,
+                          const LEN& len) :
+      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
+      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
       _pred(0), _dist(0), _path(0), _di(0) {}
 
   };
-  
+
   /// \brief Auxiliary class for the function-type interface of the
   /// \ref BellmanFord "Bellman-Ford" algorithm.
@@ -952 +952 @@
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::OutArcIt ArcIt;
-    
+
     typedef typename TR::LengthMap LengthMap;
     typedef typename LengthMap::Value Value;
@@ -969 +969 @@
     /// \param gr The digraph the algorithm runs on.
     /// \param len The length map.
-    BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
+    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
       : TR(gr, len) {}
 
@@ -978 +978 @@
 
     /// \brief Runs the Bellman-Ford algorithm from the given source node.
-    ///    
+    ///
     /// This method runs the Bellman-Ford algorithm from the given source
     /// node in order to compute the shortest path to each node.
     void run(Node s) {
-      BellmanFord<Digraph,LengthMap,TR> 
-        bf(*reinterpret_cast<const Digraph*>(Base::_graph), 
+      BellmanFord<Digraph,LengthMap,TR>
+        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
            *reinterpret_cast<const LengthMap*>(Base::_length));
       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
@@ -1018 +1018 @@
       SetPredMapBase(const TR &b) : TR(b) {}
     };
-    
+
     /// \brief \ref named-templ-param "Named parameter" for setting
     /// the predecessor map.
@@ -1029 +1029 @@
       return BellmanFordWizard<SetPredMapBase<T> >(*this);
     }
-    
+
     template<class T>
     struct SetDistMapBase : public Base {
@@ -1036 +1036 @@
       SetDistMapBase(const TR &b) : TR(b) {}
     };
-    
+
     /// \brief \ref named-templ-param "Named parameter" for setting
     /// the distance map.
@@ -1077 +1077 @@
       return *this;
     }
-    
+
   };
-  
+
   /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
   /// algorithm.
@@ -1087 +1087 @@
   /// algorithm.
   ///
-  /// This function also has several \ref named-templ-func-param 
-  /// "named parameters", they are declared as the members of class 
+  /// This function also has several \ref named-templ-func-param
+  /// "named parameters", they are declared as the members of class
   /// \ref BellmanFordWizard.
   /// The following examples show how to use these parameters.
@@ -1105 +1105 @@
   BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
   bellmanFord(const GR& digraph,
-              const LEN& length)
+              const LEN& length)
   {
     return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);

lemon/bellman_ford.h

@@ -29 +29 @@
 #include <lemon/error.h>
 #include <lemon/maps.h>
-#include <lemon/tolerance.h>
 #include <lemon/path.h>
 
@@ -36 +35 @@
 namespace lemon {
 
-  /// \brief Default operation traits for the BellmanFord algorithm class.
+  /// \brief Default OperationTraits for the BellmanFord algorithm class.
   ///
   /// This operation traits class defines all computational operations
@@ -43 +42 @@
   /// If the numeric type does not have infinity value, then the maximum
   /// value is used as extremal infinity value.
-  ///
-  /// \see BellmanFordToleranceOperationTraits
   template <
     typename V,
     bool has_inf = std::numeric_limits<V>::has_infinity>
   struct BellmanFordDefaultOperationTraits {
-    /// \brief Value type for the algorithm.
+    /// \e
     typedef V Value;
     /// \brief Gives back the zero value of the type.
@@ -85 +82 @@
     static bool less(const Value& left, const Value& right) {
       return left < right;
-    }
-  };
-
-  /// \brief Operation traits for the BellmanFord algorithm class
-  /// using tolerance.
-  ///
-  /// This operation traits class defines all computational operations
-  /// and constants that are used in the Bellman-Ford algorithm.
-  /// The only difference between this implementation and
-  /// \ref BellmanFordDefaultOperationTraits is that this class uses
-  /// the \ref Tolerance "tolerance technique" in its \ref less()
-  /// function.
-  ///
-  /// \tparam V The value type.
-  /// \tparam eps The epsilon value for the \ref less() function.
-  /// By default, it is the epsilon value used by \ref Tolerance
-  /// "Tolerance<V>".
-  ///
-  /// \see BellmanFordDefaultOperationTraits
-#ifdef DOXYGEN
-  template <typename V, V eps>
-#else
-  template <
-    typename V,
-    V eps = Tolerance<V>::def_epsilon>
-#endif
-  struct BellmanFordToleranceOperationTraits {
-    /// \brief Value type for the algorithm.
-    typedef V Value;
-    /// \brief Gives back the zero value of the type.
-    static Value zero() {
-      return static_cast<Value>(0);
-    }
-    /// \brief Gives back the positive infinity value of the type.
-    static Value infinity() {
-      return std::numeric_limits<Value>::infinity();
-    }
-    /// \brief Gives back the sum of the given two elements.
-    static Value plus(const Value& left, const Value& right) {
-      return left + right;
-    }
-    /// \brief Gives back \c true only if the first value is less than
-    /// the second.
-    static bool less(const Value& left, const Value& right) {
-      return left + eps < right;
     }
   };
@@ -156 +108 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits,
-    /// BellmanFordToleranceOperationTraits
+    /// \see BellmanFordDefaultOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 
@@ -887 +838 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits,
-    /// BellmanFordToleranceOperationTraits
+    /// \see BellmanFordDefaultOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 

test/bellman_ford_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -98 +98 @@
     pp = const_bf_test.path(t);
     pp = const_bf_test.negativeCycle();
-    
+
     for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
   }
@@ -110 +110 @@
     concepts::ReadWriteMap<Node,Arc> pred_map;
     concepts::ReadWriteMap<Node,Value> dist_map;
-    
+
     bf_test
       .lengthMap(length_map)
@@ -189 +189 @@
   check(pathSource(gr, p) == s, "path() found a wrong path.");
   check(pathTarget(gr, p) == t, "path() found a wrong path.");
-  
+
   ListPath<Digraph> path;
   Value dist;
@@ -228 +228 @@
   SmartDigraph gr;
   IntArcMap length(gr);
-  
+
   Node n1 = gr.addNode();
   Node n2 = gr.addNode();
   Node n3 = gr.addNode();
   Node n4 = gr.addNode();
-  
+
   Arc a1 = gr.addArc(n1, n2);
   Arc a2 = gr.addArc(n2, n2);
-  
+
   length[a1] = 2;
   length[a2] = -1;
-  
+
   {
     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
@@ -247 +247 @@
           "Wrong negative cycle.");
   }
- 
+
   length[a2] = 0;
-  
+
   {
     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
@@ -256 +256 @@
           "Negative cycle should not be found.");
   }
-  
+
   length[gr.addArc(n1, n3)] = 5;
   length[gr.addArc(n4, n3)] = 1;
   length[gr.addArc(n2, n4)] = 2;
   length[gr.addArc(n3, n2)] = -4;
-  
+
   {
     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);

test/bellman_ford_test.cc

@@ -105 +105 @@
       ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
       ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
-      ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
       ::Create bf_test(gr,length);