# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 2009-08-02 13:24:46
# Node ID 9496ed797f20537523edb8a14c85979c629e35ad
# Parent  c9b9da1a90a022b261c4cc379373efba6256bc85

Improvements and unifications for BellmanFord (#51)

 - Rework the function type interface to fit to dijkstra().
 - Rename named template parameters (Def* -> Set*).
 - Rename some private member variables
   (to start with an underscore).
 - Simplify template parameter names.
 - Many unifications and improvements in the doc.

diff --git a/lemon/bellman_ford.h b/lemon/bellman_ford.h
--- a/lemon/bellman_ford.h
+++ b/lemon/bellman_ford.h
@@ -16,18 +16,18 @@
  *
  */
 
-#ifndef LEMON_BELMANN_FORD_H
-#define LEMON_BELMANN_FORD_H
+#ifndef LEMON_BELLMAN_FORD_H
+#define LEMON_BELLMAN_FORD_H
 
 /// \ingroup shortest_path
 /// \file
 /// \brief Bellman-Ford algorithm.
-///
 
 #include <lemon/bits/path_dump.h>
 #include <lemon/core.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>
+#include <lemon/path.h>
 
 #include <limits>
 
@@ -35,15 +35,17 @@
 
   /// \brief Default OperationTraits for the BellmanFord algorithm class.
   ///  
-  /// It defines all computational operations and constants which are
-  /// used in the Bellman-Ford algorithm. The default implementation
-  /// is based on the numeric_limits class. If the numeric type does not
-  /// have infinity value then the maximum value is used as extremal
-  /// infinity value.
+  /// This operation traits class defines all computational operations
+  /// and constants that are used in the Bellman-Ford algorithm.
+  /// The default implementation is based on the \c numeric_limits class.
+  /// If the numeric type does not have infinity value, then the maximum
+  /// value is used as extremal infinity value.
   template <
-    typename Value, 
-    bool has_infinity = std::numeric_limits<Value>::has_infinity>
+    typename V, 
+    bool has_inf = std::numeric_limits<V>::has_infinity>
   struct BellmanFordDefaultOperationTraits {
+    /// \e
+    typedef V Value;
     /// \brief Gives back the zero value of the type.
     static Value zero() {
       return static_cast<Value>(0);
@@ -56,14 +58,16 @@
     static Value plus(const Value& left, const Value& right) {
       return left + right;
     }
-    /// \brief Gives back true only if the first value less than the second.
+    /// \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 < right;
     }
   };
 
-  template <typename Value>
-  struct BellmanFordDefaultOperationTraits<Value, false> {
+  template <typename V>
+  struct BellmanFordDefaultOperationTraits<V, false> {
+    typedef V Value;
     static Value zero() {
       return static_cast<Value>(0);
     }
@@ -82,26 +86,26 @@
   /// \brief Default traits class of BellmanFord class.
   ///
   /// Default traits class of BellmanFord class.
-  /// \param _Digraph Digraph type.
-  /// \param _LegthMap Type of length map.
-  template<class _Digraph, class _LengthMap>
+  /// \param GR The type of the digraph.
+  /// \param LEN The type of the length map.
+  template<typename GR, typename LEN>
   struct BellmanFordDefaultTraits {
-    /// The digraph type the algorithm runs on. 
-    typedef _Digraph Digraph;
+    /// The type of the digraph the algorithm runs on. 
+    typedef GR Digraph;
 
     /// \brief The type of the map that stores the arc lengths.
     ///
     /// The type of the map that stores the arc lengths.
-    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef _LengthMap LengthMap;
+    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+    typedef LEN LengthMap;
 
-    // The type of the length of the arcs.
-    typedef typename _LengthMap::Value Value;
+    /// The type of the arc lengths.
+    typedef typename LEN::Value Value;
 
     /// \brief Operation traits for Bellman-Ford algorithm.
     ///
-    /// It defines the infinity type on the given Value type
-    /// and the used operation.
+    /// It defines the used operations and the infinity value for the
+    /// given \c Value type.
     /// \see BellmanFordDefaultOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
  
@@ -110,33 +114,31 @@
     /// 
     /// The type of the map that stores the last
     /// arcs of the shortest paths.
-    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///
-    typedef typename Digraph::template NodeMap<typename _Digraph::Arc> PredMap;
+    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 
-    /// \brief Instantiates a PredMap.
+    /// \brief Instantiates a \c PredMap.
     /// 
     /// This function instantiates a \ref PredMap. 
-    /// \param digraph is the digraph, to which we would like to define the PredMap.
-    static PredMap *createPredMap(const _Digraph& digraph) {
-      return new PredMap(digraph);
+    /// \param g is the digraph to which we would like to define the
+    /// \ref PredMap.
+    static PredMap *createPredMap(const GR& g) {
+      return new PredMap(g);
     }
 
-    /// \brief The type of the map that stores the dists of the nodes.
+    /// \brief The type of the map that stores the distances of the nodes.
     ///
-    /// The type of the map that stores the dists of the nodes.
-    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///
-    typedef typename Digraph::template NodeMap<typename _LengthMap::Value> 
-    DistMap;
+    /// The type of the map that stores the distances of the nodes.
+    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
 
-    /// \brief Instantiates a DistMap.
+    /// \brief Instantiates a \c DistMap.
     ///
     /// This function instantiates a \ref DistMap. 
-    /// \param digraph is the digraph, to which we would like to define the 
-    /// \ref DistMap
-    static DistMap *createDistMap(const _Digraph& digraph) {
-      return new DistMap(digraph);
+    /// \param g is the digraph to which we would like to define the 
+    /// \ref DistMap.
+    static DistMap *createDistMap(const GR& g) {
+      return new DistMap(g);
     }
 
   };
@@ -144,106 +146,109 @@
   /// \brief %BellmanFord algorithm class.
   ///
   /// \ingroup shortest_path
-  /// This class provides an efficient implementation of \c Bellman-Ford 
-  /// algorithm. The arc lengths are passed to the algorithm using a
+  /// This class provides an efficient implementation of the Bellman-Ford 
+  /// algorithm. The maximum time complexity of the algorithm is
+  /// <tt>O(ne)</tt>.
+  ///
+  /// The Bellman-Ford algorithm solves the single-source shortest path
+  /// problem when the arcs can have negative lengths, but the digraph
+  /// should not contain directed cycles with negative total length.
+  /// If all arc costs are non-negative, consider to use the Dijkstra
+  /// algorithm instead, since it is more efficient.
+  ///
+  /// The arc lengths are passed to the algorithm using a
   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
-  /// kind of length.
+  /// kind of length. The type of the length values is determined by the
+  /// \ref concepts::ReadMap::Value "Value" type of the length map.
   ///
-  /// The Bellman-Ford algorithm solves the shortest path from one node
-  /// problem when the arcs can have negative length but the digraph should
-  /// not contain cycles with negative sum of length. If we can assume
-  /// that all arc is non-negative in the digraph then the dijkstra algorithm
-  /// should be used rather.
+  /// There is also a \ref bellmanFord() "function-type interface" for the
+  /// Bellman-Ford algorithm, which is convenient in the simplier cases and
+  /// it can be used easier.
   ///
-  /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
-  ///
-  /// The type of the length is determined by the
-  /// \ref concepts::ReadMap::Value "Value" of the length map.
-  ///
-  /// \param _Digraph The digraph type the algorithm runs on. The default value
-  /// is \ref ListDigraph. The value of _Digraph is not used directly by
-  /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
-  /// \param _LengthMap This read-only ArcMap determines the lengths of the
-  /// arcs. The default map type is \ref concepts::Digraph::ArcMap 
-  /// "Digraph::ArcMap<int>".  The value of _LengthMap is not used directly 
-  /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.  
-  /// \param _Traits Traits class to set various data types used by the 
-  /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
-  /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>".  See \ref
-  /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
-  /// class.
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// The default type is \ref ListDigraph.
+  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
+  /// the lengths of the arcs. The default map type is
+  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 #ifdef DOXYGEN
-  template <typename _Digraph, typename _LengthMap, typename _Traits>
+  template <typename GR, typename LEN, typename TR>
 #else
-  template <typename _Digraph,
-	    typename _LengthMap=typename _Digraph::template ArcMap<int>,
-	    typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> >
+  template <typename GR=ListDigraph,
+            typename LEN=typename GR::template ArcMap<int>,
+            typename TR=BellmanFordDefaultTraits<GR,LEN> >
 #endif
   class BellmanFord {
   public:
 
-    typedef _Traits Traits;
     ///The type of the underlying digraph.
-    typedef typename _Traits::Digraph Digraph;
+    typedef typename TR::Digraph Digraph;
+    
+    /// \brief The type of the arc lengths.
+    typedef typename TR::LengthMap::Value Value;
+    /// \brief The type of the map that stores the arc lengths.
+    typedef typename TR::LengthMap LengthMap;
+    /// \brief The type of the map that stores the last
+    /// arcs of the shortest paths.
+    typedef typename TR::PredMap PredMap;
+    /// \brief The type of the map that stores the distances of the nodes.
+    typedef typename TR::DistMap DistMap;
+    /// The type of the paths.
+    typedef PredMapPath<Digraph, PredMap> Path;
+    ///\brief The \ref BellmanFordDefaultOperationTraits
+    /// "operation traits class" of the algorithm.
+    typedef typename TR::OperationTraits OperationTraits;
+
+    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
+    typedef TR Traits;
+
+  private:
 
     typedef typename Digraph::Node Node;
     typedef typename Digraph::NodeIt NodeIt;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::OutArcIt OutArcIt;
-    
-    /// \brief The type of the length of the arcs.
-    typedef typename _Traits::LengthMap::Value Value;
-    /// \brief The type of the map that stores the arc lengths.
-    typedef typename _Traits::LengthMap LengthMap;
-    /// \brief The type of the map that stores the last
-    /// arcs of the shortest paths.
-    typedef typename _Traits::PredMap PredMap;
-    /// \brief The type of the map that stores the dists of the nodes.
-    typedef typename _Traits::DistMap DistMap;
-    /// \brief The operation traits.
-    typedef typename _Traits::OperationTraits OperationTraits;
-  private:
-    /// Pointer to the underlying digraph.
-    const Digraph *digraph;
-    /// Pointer to the length map
-    const LengthMap *length;
-    ///Pointer to the map of predecessors arcs.
+
+    // Pointer to the underlying digraph.
+    const Digraph *_gr;
+    // Pointer to the length map
+    const LengthMap *_length;
+    // Pointer to the map of predecessors arcs.
     PredMap *_pred;
-    ///Indicates if \ref _pred is locally allocated (\c true) or not.
-    bool local_pred;
-    ///Pointer to the map of distances.
+    // Indicates if _pred is locally allocated (true) or not.
+    bool _local_pred;
+    // Pointer to the map of distances.
     DistMap *_dist;
-    ///Indicates if \ref _dist is locally allocated (\c true) or not.
-    bool local_dist;
+    // Indicates if _dist is locally allocated (true) or not.
+    bool _local_dist;
 
     typedef typename Digraph::template NodeMap<bool> MaskMap;
     MaskMap *_mask;
 
     std::vector<Node> _process;
 
-    /// Creates the maps if necessary.
+    // Creates the maps if necessary.
     void create_maps() {
       if(!_pred) {
-	local_pred = true;
-	_pred = Traits::createPredMap(*digraph);
+	_local_pred = true;
+	_pred = Traits::createPredMap(*_gr);
       }
       if(!_dist) {
-	local_dist = true;
-	_dist = Traits::createDistMap(*digraph);
+	_local_dist = true;
+	_dist = Traits::createDistMap(*_gr);
       }
-      _mask = new MaskMap(*digraph, false);
+      _mask = new MaskMap(*_gr, false);
     }
     
   public :
  
     typedef BellmanFord Create;
 
-    /// \name Named template parameters
+    /// \name Named Template Parameters
 
     ///@{
 
     template <class T>
-    struct DefPredMapTraits : public Traits {
+    struct SetPredMapTraits : public Traits {
       typedef T PredMap;
       static PredMap *createPredMap(const Digraph&) {
         LEMON_ASSERT(false, "PredMap is not initialized");
@@ -251,18 +256,20 @@
       }
     };
 
-    /// \brief \ref named-templ-param "Named parameter" for setting PredMap 
-    /// type
-    /// \ref named-templ-param "Named parameter" for setting PredMap type
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c PredMap type.
     ///
+    /// \ref named-templ-param "Named parameter" for setting
+    /// \c PredMap type.
+    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap 
-      : public BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > {
-      typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > Create;
+      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
+      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
     };
     
     template <class T>
-    struct DefDistMapTraits : public Traits {
+    struct SetDistMapTraits : public Traits {
       typedef T DistMap;
       static DistMap *createDistMap(const Digraph&) {
         LEMON_ASSERT(false, "DistMap is not initialized");
@@ -270,31 +277,33 @@
       }
     };
 
-    /// \brief \ref named-templ-param "Named parameter" for setting DistMap 
-    /// type
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c DistMap type.
     ///
-    /// \ref named-templ-param "Named parameter" for setting DistMap type
-    ///
+    /// \ref named-templ-param "Named parameter" for setting
+    /// \c DistMap type.
+    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap 
-      : public BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > {
-      typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > Create;
+      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
+      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
     };
-    
+
     template <class T>
-    struct DefOperationTraitsTraits : public Traits {
+    struct SetOperationTraitsTraits : public Traits {
       typedef T OperationTraits;
     };
     
     /// \brief \ref named-templ-param "Named parameter" for setting 
-    /// OperationTraits type
+    /// \c OperationTraits type.
     ///
-    /// \ref named-templ-param "Named parameter" for setting OperationTraits
-    /// type
+    /// \ref named-templ-param "Named parameter" for setting
+    /// \c OperationTraits type.
+    /// For more information see \ref BellmanFordDefaultOperationTraits.
     template <class T>
     struct SetOperationTraits
-      : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> > {
-      typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> >
+      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
+      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
       Create;
     };
     
@@ -308,85 +317,89 @@
     
     /// \brief Constructor.
     ///
-    /// \param _graph the digraph the algorithm will run on.
-    /// \param _length the length map used by the algorithm.
-    BellmanFord(const Digraph& _graph, const LengthMap& _length) :
-      digraph(&_graph), length(&_length),
-      _pred(0), local_pred(false),
-      _dist(0), local_dist(false), _mask(0) {}
+    /// Constructor.
+    /// \param g The digraph the algorithm runs on.
+    /// \param length The length map used by the algorithm.
+    BellmanFord(const Digraph& g, const LengthMap& length) :
+      _gr(&g), _length(&length),
+      _pred(0), _local_pred(false),
+      _dist(0), _local_dist(false), _mask(0) {}
     
     ///Destructor.
     ~BellmanFord() {
-      if(local_pred) delete _pred;
-      if(local_dist) delete _dist;
+      if(_local_pred) delete _pred;
+      if(_local_dist) delete _dist;
       if(_mask) delete _mask;
     }
 
     /// \brief Sets the length map.
     ///
     /// Sets the length map.
-    /// \return \c (*this)
-    BellmanFord &lengthMap(const LengthMap &m) {
-      length = &m;
+    /// \return <tt>(*this)</tt>
+    BellmanFord &lengthMap(const LengthMap &map) {
+      _length = &map;
       return *this;
     }
 
-    /// \brief Sets the map storing the predecessor arcs.
+    /// \brief Sets the map that stores the predecessor arcs.
     ///
-    /// Sets the map storing the predecessor arcs.
-    /// If you don't use this function before calling \ref run(),
-    /// it will allocate one. The destuctor deallocates this
-    /// automatically allocated map, of course.
-    /// \return \c (*this)
-    BellmanFord &predMap(PredMap &m) {
-      if(local_pred) {
+    /// Sets the map that stores the predecessor arcs.
+    /// If you don't use this function before calling \ref run()
+    /// or \ref init(), an instance will be allocated automatically.
+    /// The destructor deallocates this automatically allocated map,
+    /// of course.
+    /// \return <tt>(*this)</tt>
+    BellmanFord &predMap(PredMap &map) {
+      if(_local_pred) {
 	delete _pred;
-	local_pred=false;
+	_local_pred=false;
       }
-      _pred = &m;
+      _pred = &map;
       return *this;
     }
 
-    /// \brief Sets the map storing the distances calculated by the algorithm.
+    /// \brief Sets the map that stores the distances of the nodes.
     ///
-    /// Sets the map storing the distances calculated by the algorithm.
-    /// If you don't use this function before calling \ref run(),
-    /// it will allocate one. The destuctor deallocates this
-    /// automatically allocated map, of course.
-    /// \return \c (*this)
-    BellmanFord &distMap(DistMap &m) {
-      if(local_dist) {
+    /// Sets the map that stores the distances of the nodes calculated
+    /// by the algorithm.
+    /// If you don't use this function before calling \ref run()
+    /// or \ref init(), an instance will be allocated automatically.
+    /// The destructor deallocates this automatically allocated map,
+    /// of course.
+    /// \return <tt>(*this)</tt>
+    BellmanFord &distMap(DistMap &map) {
+      if(_local_dist) {
 	delete _dist;
-	local_dist=false;
+	_local_dist=false;
       }
-      _dist = &m;
+      _dist = &map;
       return *this;
     }
 
-    /// \name Execution control
-    /// The simplest way to execute the algorithm is to use
-    /// one of the member functions called \c run(...).
-    /// \n
-    /// If you need more control on the execution,
-    /// first you must call \ref init(), then you can add several source nodes
-    /// with \ref addSource().
-    /// Finally \ref start() will perform the actual path
-    /// computation.
+    /// \name Execution Control
+    /// The simplest way to execute the Bellman-Ford algorithm is to use
+    /// one of the member functions called \ref run().\n
+    /// If you need better control on the execution, you have to call
+    /// \ref init() first, then you can add several source nodes
+    /// with \ref addSource(). Finally the actual path computation can be
+    /// performed with \ref start(), \ref checkedStart() or
+    /// \ref limitedStart().
 
     ///@{
 
     /// \brief Initializes the internal data structures.
     /// 
-    /// Initializes the internal data structures.
+    /// Initializes the internal data structures. The optional parameter
+    /// is the initial distance of each node.
     void init(const Value value = OperationTraits::infinity()) {
       create_maps();
-      for (NodeIt it(*digraph); it != INVALID; ++it) {
+      for (NodeIt it(*_gr); it != INVALID; ++it) {
 	_pred->set(it, INVALID);
 	_dist->set(it, value);
       }
       _process.clear();
       if (OperationTraits::less(value, OperationTraits::infinity())) {
-	for (NodeIt it(*digraph); it != INVALID; ++it) {
+	for (NodeIt it(*_gr); it != INVALID; ++it) {
 	  _process.push_back(it);
 	  _mask->set(it, true);
 	}
@@ -395,9 +408,8 @@
     
     /// \brief Adds a new source node.
     ///
-    /// Adds a new source node. The optional second parameter is the 
-    /// initial distance of the node. It just sets the distance of the 
-    /// node to the given value.
+    /// This function adds a new source node. The optional second parameter
+    /// is the initial distance of the node.
     void addSource(Node source, Value dst = OperationTraits::zero()) {
       _dist->set(source, dst);
       if (!(*_mask)[source]) {
@@ -409,19 +421,22 @@
     /// \brief Executes one round from the Bellman-Ford algorithm.
     ///
     /// If the algoritm calculated the distances in the previous round
-    /// exactly for all at most \f$ k \f$ length path lengths then it will
-    /// calculate the distances exactly for all at most \f$ k + 1 \f$
-    /// length path lengths. With \f$ k \f$ iteration this function
-    /// calculates the at most \f$ k \f$ length path lengths.
+    /// exactly for the paths of at most \c k arcs, then this function
+    /// will calculate the distances exactly for the paths of at most
+    /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
+    /// calculates the shortest path distances exactly for the paths
+    /// consisting of at most \c k arcs.
     ///
     /// \warning The paths with limited arc number cannot be retrieved
-    /// easily with \ref path() or \ref predArc() functions. If you
-    /// need the shortest path and not just the distance you should store
-    /// after each iteration the \ref predMap() map and manually build
-    /// the path.
+    /// easily with \ref path() or \ref predArc() functions. If you also
+    /// need the shortest paths and not only the distances, you should
+    /// store the \ref predMap() "predecessor map" after each iteration
+    /// and build the path manually.
     ///
     /// \return \c true when the algorithm have not found more shorter
     /// paths.
+    ///
+    /// \see ActiveIt
     bool processNextRound() {
       for (int i = 0; i < int(_process.size()); ++i) {
 	_mask->set(_process[i], false);
@@ -432,9 +447,9 @@
 	values[i] = (*_dist)[_process[i]];
       }
       for (int i = 0; i < int(_process.size()); ++i) {
-	for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
-	  Node target = digraph->target(it);
-	  Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
+	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);
@@ -451,23 +466,28 @@
 
     /// \brief Executes one weak round from the Bellman-Ford algorithm.
     ///
-    /// If the algorithm calculated the distances in the
-    /// previous round at least for all at most k length paths then it will
-    /// calculate the distances at least for all at most k + 1 length paths.
-    /// This function does not make it possible to calculate strictly the
-    /// at most k length minimal paths, this is why it is
-    /// called just weak round.
-    /// \return \c true when the algorithm have not found more shorter paths.
+    /// If the algorithm calculated the distances in the previous round
+    /// at least for the paths of at most \c k arcs, then this function
+    /// will calculate the distances at least for the paths of at most
+    /// <tt>k+1</tt> arcs.
+    /// This function does not make it possible to calculate the shortest
+    /// path distances exactly for paths consisting of at most \c k arcs,
+    /// this is why it is called weak round.
+    ///
+    /// \return \c true when the algorithm have not found more shorter
+    /// paths.
+    ///
+    /// \see ActiveIt
     bool processNextWeakRound() {
       for (int i = 0; i < int(_process.size()); ++i) {
 	_mask->set(_process[i], false);
       }
       std::vector<Node> nextProcess;
       for (int i = 0; i < int(_process.size()); ++i) {
-	for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
-	  Node target = digraph->target(it);
+	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+	  Node target = _gr->target(it);
 	  Value relaxed = 
-	    OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
+	    OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
 	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
 	    _pred->set(target, it);
 	    _dist->set(target, relaxed);
@@ -484,16 +504,19 @@
 
     /// \brief Executes the algorithm.
     ///
-    /// \pre init() must be called and at least one node should be added
-    /// with addSource() before using this function.
+    /// Executes the algorithm.
     ///
-    /// This method runs the %BellmanFord algorithm from the root node(s)
-    /// in order to compute the shortest path to each node. The algorithm 
-    /// computes 
-    /// - The shortest path tree.
-    /// - The distance of each node from the root(s).
+    /// This method runs the Bellman-Ford algorithm from the root node(s)
+    /// in order to compute the shortest path to each node.
+    ///
+    /// The algorithm computes
+    /// - the shortest path tree (forest),
+    /// - the distance of each node from the root(s).
+    ///
+    /// \pre init() must be called and at least one root node should be
+    /// added with addSource() before using this function.
     void start() {
-      int num = countNodes(*digraph) - 1;
+      int num = countNodes(*_gr) - 1;
       for (int i = 0; i < num; ++i) {
 	if (processNextWeakRound()) break;
       }
@@ -501,83 +524,98 @@
 
     /// \brief Executes the algorithm and checks the negative cycles.
     ///
-    /// \pre init() must be called and at least one node should be added
-    /// with addSource() before using this function. 
+    /// Executes the algorithm and checks the negative cycles.
     ///
-    /// This method runs the %BellmanFord algorithm from the root node(s)
-    /// in order to compute the shortest path to each node. The algorithm 
-    /// computes 
-    /// - The shortest path tree.
-    /// - The distance of each node from the root(s).
+    /// This method runs the Bellman-Ford algorithm from the root node(s)
+    /// in order to compute the shortest path to each node and also checks
+    /// if the digraph contains cycles with negative total length.
+    ///
+    /// 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. 
     bool checkedStart() {
-      int num = countNodes(*digraph);
+      int num = countNodes(*_gr);
       for (int i = 0; i < num; ++i) {
 	if (processNextWeakRound()) return true;
       }
       return _process.empty();
     }
 
-    /// \brief Executes the algorithm with path length limit.
+    /// \brief Executes the algorithm with arc number limit.
     ///
-    /// \pre init() must be called and at least one node should be added
-    /// with addSource() before using this function.
+    /// Executes the algorithm with arc number limit.
     ///
-    /// This method runs the %BellmanFord algorithm from the root
-    /// node(s) in order to compute the shortest path lengths with at
-    /// most \c num arc.
+    /// This method runs the Bellman-Ford algorithm from the root node(s)
+    /// in order to compute the shortest path distance for each node
+    /// using only the paths consisting of at most \c num arcs.
+    ///
+    /// The algorithm computes
+    /// - the limited distance of each node from the root(s),
+    /// - the predecessor arc for each node.
     ///
     /// \warning The paths with limited arc number cannot be retrieved
-    /// easily with \ref path() or \ref predArc() functions. If you
-    /// need the shortest path and not just the distance you should store
-    /// after each iteration the \ref predMap() map and manually build
-    /// the path.
+    /// easily with \ref path() or \ref predArc() functions. If you also
+    /// need the shortest paths and not only the distances, you should
+    /// store the \ref predMap() "predecessor map" after each iteration
+    /// and build the path manually.
     ///
-    /// The algorithm computes
-    /// - The predecessor arc from each node.
-    /// - The limited distance of each node from the root(s).
+    /// \pre init() must be called and at least one root node should be
+    /// added with addSource() before using this function. 
     void limitedStart(int num) {
       for (int i = 0; i < num; ++i) {
 	if (processNextRound()) break;
       }
     }
     
-    /// \brief Runs %BellmanFord algorithm from node \c s.
+    /// \brief Runs the algorithm from the given root node.
     ///    
-    /// This method runs the %BellmanFord algorithm from a root node \c s
-    /// in order to compute the shortest path to each node. The algorithm 
-    /// computes
-    /// - The shortest path tree.
-    /// - The distance of each node from the root.
+    /// This method runs the Bellman-Ford algorithm from the given root
+    /// node \c s in order to compute the shortest path to each node.
     ///
-    /// \note d.run(s) is just a shortcut of the following code.
-    ///\code
-    ///  d.init();
-    ///  d.addSource(s);
-    ///  d.start();
-    ///\endcode
+    /// The algorithm computes
+    /// - the shortest path tree (forest),
+    /// - the distance of each node from the root(s).
+    ///
+    /// \note bf.run(s) is just a shortcut of the following code.
+    /// \code
+    ///   bf.init();
+    ///   bf.addSource(s);
+    ///   bf.start();
+    /// \endcode
     void run(Node s) {
       init();
       addSource(s);
       start();
     }
     
-    /// \brief Runs %BellmanFord algorithm with limited path length 
-    /// from node \c s.
+    /// \brief Runs the algorithm from the given root node with arc
+    /// number limit.
     ///    
-    /// This method runs the %BellmanFord algorithm from a root node \c s
-    /// in order to compute the shortest path with at most \c len arcs 
-    /// to each node. The algorithm computes
-    /// - The shortest path tree.
-    /// - The distance of each node from the root.
+    /// This method runs the Bellman-Ford algorithm from the given root
+    /// node \c s in order to compute the shortest path distance for each
+    /// node using only the paths consisting of at most \c num arcs.
     ///
-    /// \note d.run(s, num) is just a shortcut of the following code.
-    ///\code
-    ///  d.init();
-    ///  d.addSource(s);
-    ///  d.limitedStart(num);
-    ///\endcode
+    /// The algorithm computes
+    /// - the limited distance of each node from the root(s),
+    /// - the predecessor arc for each node.
+    ///
+    /// \warning The paths with limited arc number cannot be retrieved
+    /// easily with \ref path() or \ref predArc() functions. If you also
+    /// need the shortest paths and not only the distances, you should
+    /// store the \ref predMap() "predecessor map" after each iteration
+    /// and build the path manually.
+    ///
+    /// \note bf.run(s, num) is just a shortcut of the following code.
+    /// \code
+    ///   bf.init();
+    ///   bf.addSource(s);
+    ///   bf.limitedStart(num);
+    /// \endcode
     void run(Node s, int num) {
       init();
       addSource(s);
@@ -586,27 +624,19 @@
     
     ///@}
 
-    /// \name Query Functions
-    /// The result of the %BellmanFord algorithm can be obtained using these
-    /// functions.\n
-    /// Before the use of these functions,
-    /// either run() or start() must be called.
-    
-    ///@{
-
-    /// \brief Lemon iterator for get the active nodes.
+    /// \brief LEMON iterator for getting the active nodes.
     ///
-    /// Lemon iterator for get the active nodes. This class provides a
-    /// common style lemon iterator which gives back a subset of the
-    /// nodes. The iterated nodes are active in the algorithm after
-    /// the last phase so these should be checked in the next phase to
-    /// find augmenting arcs from these.
+    /// This class provides a common style LEMON iterator that traverses
+    /// the active nodes of the Bellman-Ford algorithm after the last
+    /// phase. These nodes should be checked in the next phase to
+    /// find augmenting arcs outgoing from them.
     class ActiveIt {
     public:
 
       /// \brief Constructor.
       ///
-      /// Constructor for get the nodeset of the variable. 
+      /// Constructor for getting the active nodes of the given BellmanFord
+      /// instance. 
       ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
       {
         _index = _algorithm->_process.size() - 1;
@@ -617,9 +647,9 @@
       /// Invalid constructor.
       ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
 
-      /// \brief Conversion to node.
+      /// \brief Conversion to \c Node.
       ///
-      /// Conversion to node.
+      /// Conversion to \c Node.
       operator Node() const { 
         return _index >= 0 ? _algorithm->_process[_index] : INVALID;
       }
@@ -646,394 +676,432 @@
       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.
+    
+    ///@{
 
-    typedef PredMapPath<Digraph, PredMap> Path;
+    /// \brief The shortest path to the given node.
+    ///    
+    /// Gives back the shortest path to the given node from the root(s).
+    ///
+    /// \warning \c t should be reached from the root(s).
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
+    Path path(Node t) const
+    {
+      return Path(*_gr, *_pred, t);
+    }
+	  
+    /// \brief The distance of the given node from the root(s).
+    ///
+    /// Returns the distance of the given node from the root(s).
+    ///
+    /// \warning If node \c v is not reached from the root(s), then
+    /// the return value of this function is undefined.
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
+    Value dist(Node v) const { return (*_dist)[v]; }
 
-    /// \brief Gives back the shortest path.
-    ///    
-    /// Gives back the shortest path.
-    /// \pre The \c t should be reachable from the source.
-    Path path(Node t) 
-    {
-      return Path(*digraph, *_pred, t);
+    /// \brief Returns the 'previous arc' of the shortest path tree for
+    /// the given node.
+    ///
+    /// This function returns the 'previous arc' of the shortest path
+    /// tree for node \c v, i.e. it returns the last arc of a
+    /// shortest path from a root to \c v. It is \c INVALID if \c v
+    /// is not reached from the root(s) or if \c v is a root.
+    ///
+    /// The shortest path tree used here is equal to the shortest path
+    /// tree used in \ref predNode() and \predMap().
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
+    Arc predArc(Node v) const { return (*_pred)[v]; }
+
+    /// \brief Returns the 'previous node' of the shortest path tree for
+    /// the given node.
+    ///
+    /// This function returns the 'previous node' of the shortest path
+    /// tree for node \c v, i.e. it returns the last but one node of
+    /// a shortest path from a root to \c v. It is \c INVALID if \c v
+    /// is not reached from the root(s) or if \c v is a root.
+    ///
+    /// The shortest path tree used here is equal to the shortest path
+    /// tree used in \ref predArc() and \predMap().
+    ///
+    /// \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]); 
+    }
+    
+    /// \brief Returns a const reference to the node map that stores the
+    /// distances of the nodes.
+    ///
+    /// Returns a const reference to the node map that stores the distances
+    /// of the nodes calculated by the algorithm.
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
+    const DistMap &distMap() const { return *_dist;}
+ 
+    /// \brief Returns a const reference to the node map that stores the
+    /// predecessor arcs.
+    ///
+    /// Returns a const reference to the node map that stores the predecessor
+    /// arcs, which form the shortest path tree (forest).
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
+    const PredMap &predMap() const { return *_pred; }
+ 
+    /// \brief Checks if a node is reached from the root(s).
+    ///
+    /// Returns \c true if \c v is reached from the root(s).
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
+    bool reached(Node v) const {
+      return (*_dist)[v] != OperationTraits::infinity();
     }
 
-
-    // TODO : implement negative cycle
-//     /// \brief Gives back a negative cycle.
-//     ///    
-//     /// This function gives back a negative cycle.
-//     /// If the algorithm have not found yet negative cycle it will give back
-//     /// an empty path.
-//     Path negativeCycle() {
-//       typename Digraph::template NodeMap<int> state(*digraph, 0);
-//       for (ActiveIt it(*this); it != INVALID; ++it) {
-//         if (state[it] == 0) {
-//           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
-//             if (state[t] == 0) {
-//               state[t] = 1;
-//             } else if (state[t] == 2) {
-//               break;
-//             } else {
-//               p.clear();
-//               typename Path::Builder b(p);
-//               b.setStartNode(t);
-//               b.pushFront(predArc(t));
-//               for(Node s = predNode(t); s != t; s = predNode(s)) {
-//                 b.pushFront(predArc(s));
-//               }
-//               b.commit();
-//               return true;
-//             }
-//           }
-//           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
-//             if (state[t] == 1) {
-//               state[t] = 2;
-//             } else {
-//               break;
-//             }
-//           }
-//         }
-//       }
-//       return false;
-//     }
-	  
-    /// \brief The distance of a node from the root.
-    ///
-    /// Returns the distance of a node from the root.
-    /// \pre \ref run() must be called before using this function.
-    /// \warning If node \c v in unreachable from the root the return value
-    /// of this funcion is undefined.
-    Value dist(Node v) const { return (*_dist)[v]; }
-
-    /// \brief Returns the 'previous arc' of the shortest path tree.
-    ///
-    /// For a node \c v it returns the 'previous arc' of the shortest path 
-    /// tree, i.e. it returns the last arc of a shortest path from the root 
-    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or 
-    /// if \c v=s. The shortest path tree used here is equal to the shortest 
-    /// path tree used in \ref predNode(). 
-    /// \pre \ref run() must be called before using
-    /// this function.
-    Arc predArc(Node v) const { return (*_pred)[v]; }
-
-    /// \brief Returns the 'previous node' of the shortest path tree.
-    ///
-    /// For a node \c v it returns the 'previous node' of the shortest path 
-    /// tree, i.e. it returns the last but one node from a shortest path from 
-    /// the root to \c /v. It is INVALID if \c v is unreachable from the root 
-    /// or if \c v=s. The shortest path tree used here is equal to the 
-    /// shortest path tree used in \ref predArc().  \pre \ref run() must be 
-    /// called before using this function.
-    Node predNode(Node v) const { 
-      return (*_pred)[v] == INVALID ? INVALID : digraph->source((*_pred)[v]); 
-    }
-    
-    /// \brief Returns a reference to the NodeMap of distances.
-    ///
-    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
-    /// be called before using this function.
-    const DistMap &distMap() const { return *_dist;}
- 
-    /// \brief Returns a reference to the shortest path tree map.
-    ///
-    /// Returns a reference to the NodeMap of the arcs of the
-    /// shortest path tree.
-    /// \pre \ref run() must be called before using this function.
-    const PredMap &predMap() const { return *_pred; }
- 
-    /// \brief Checks if a node is reachable from the root.
-    ///
-    /// Returns \c true if \c v is reachable from the root.
-    /// \pre \ref run() must be called before using this function.
-    ///
-    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
+    // TODO: implement negative cycle
+//    /// \brief Gives back a negative cycle.
+//    ///    
+//    /// This function gives back a negative cycle.
+//    /// If the algorithm have not found yet negative cycle it will give back
+//    /// an empty path.
+//    Path negativeCycle() {
+//      typename Digraph::template NodeMap<int> state(*digraph, 0);
+//      for (ActiveIt it(*this); it != INVALID; ++it) {
+//        if (state[it] == 0) {
+//          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
+//            if (state[t] == 0) {
+//              state[t] = 1;
+//            } else if (state[t] == 2) {
+//              break;
+//            } else {
+//              p.clear();
+//              typename Path::Builder b(p);
+//              b.setStartNode(t);
+//              b.pushFront(predArc(t));
+//              for(Node s = predNode(t); s != t; s = predNode(s)) {
+//                b.pushFront(predArc(s));
+//              }
+//              b.commit();
+//              return true;
+//            }
+//          }
+//          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
+//            if (state[t] == 1) {
+//              state[t] = 2;
+//            } else {
+//              break;
+//            }
+//          }
+//        }
+//      }
+//      return false;
+//    }
     
     ///@}
   };
  
-  /// \brief Default traits class of BellmanFord function.
+  /// \brief Default traits class of bellmanFord() function.
   ///
-  /// Default traits class of BellmanFord function.
-  /// \param _Digraph Digraph type.
-  /// \param _LengthMap Type of length map.
-  template <typename _Digraph, typename _LengthMap>
+  /// Default traits class of bellmanFord() function.
+  /// \tparam GR The type of the digraph.
+  /// \tparam LEN The type of the length map.
+  template <typename GR, typename LEN>
   struct BellmanFordWizardDefaultTraits {
-    /// \brief The digraph type the algorithm runs on. 
-    typedef _Digraph Digraph;
+    /// The type of the digraph the algorithm runs on. 
+    typedef GR Digraph;
 
     /// \brief The type of the map that stores the arc lengths.
     ///
     /// The type of the map that stores the arc lengths.
     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef _LengthMap LengthMap;
+    typedef LEN LengthMap;
 
-    /// \brief The value type of the length map.
-    typedef typename _LengthMap::Value Value;
+    /// The type of the arc lengths.
+    typedef typename LEN::Value Value;
 
     /// \brief Operation traits for Bellman-Ford algorithm.
     ///
-    /// It defines the infinity type on the given Value type
-    /// and the used operation.
+    /// It defines the used operations and the infinity value for the
+    /// given \c Value type.
     /// \see BellmanFordDefaultOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 
     /// \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 meet the \ref concepts::WriteMap "WriteMap" concept.
-    typedef NullMap <typename _Digraph::Node,typename _Digraph::Arc> PredMap;
+    /// The type of the map that stores the last arcs of the shortest paths.
+    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 
-    /// \brief Instantiates a PredMap.
+    /// \brief Instantiates a \c PredMap.
     /// 
-    /// This function instantiates a \ref PredMap. 
-    static PredMap *createPredMap(const _Digraph &) {
-      return new PredMap();
+    /// This function instantiates a \ref PredMap.
+    /// \param g is the digraph to which we would like to define the
+    /// \ref PredMap.
+    static PredMap *createPredMap(const GR &g) {
+      return new PredMap(g);
     }
-    /// \brief The type of the map that stores the dists of the nodes.
+
+    /// \brief The type of the map that stores the distances of the nodes.
     ///
-    /// The type of the map that stores the dists of the nodes.
-    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    typedef NullMap<typename Digraph::Node, Value> DistMap;
-    /// \brief Instantiates a DistMap.
+    /// The type of the map that stores the distances of the nodes.
+    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    typedef typename GR::template NodeMap<Value> DistMap;
+
+    /// \brief Instantiates a \c DistMap.
     ///
     /// This function instantiates a \ref DistMap. 
-    static DistMap *createDistMap(const _Digraph &) {
-      return new DistMap();
+    /// \param g is the digraph to which we would like to define the
+    /// \ref DistMap.
+    static DistMap *createDistMap(const GR &g) {
+      return new DistMap(g);
     }
+
+    ///The type of the shortest paths.
+
+    ///The type of the shortest paths.
+    ///It must meet the \ref concepts::Path "Path" concept.
+    typedef lemon::Path<Digraph> Path;
   };
   
-  /// \brief Default traits used by \ref BellmanFordWizard
+  /// \brief Default traits class used by BellmanFordWizard.
   ///
-  /// To make it easier to use BellmanFord algorithm
-  /// we have created a wizard class.
-  /// This \ref BellmanFordWizard class needs default traits,
-  /// as well as the \ref BellmanFord class.
-  /// The \ref BellmanFordWizardBase is a class to be the default traits of the
-  /// \ref BellmanFordWizard class.
-  /// \todo More named parameters are required...
-  template<class _Digraph,class _LengthMap>
+  /// Default traits class used by BellmanFordWizard.
+  /// \tparam GR The type of the digraph.
+  /// \tparam LEN The type of the length map.
+  template <typename GR, typename LEN>
   class BellmanFordWizardBase 
-    : public BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> {
+    : public BellmanFordWizardDefaultTraits<GR, LEN> {
 
-    typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base;
+    typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
   protected:
-    /// Type of the nodes in the digraph.
+    // Type of the nodes in the digraph.
     typedef typename Base::Digraph::Node Node;
 
-    /// Pointer to the underlying digraph.
+    // Pointer to the underlying digraph.
     void *_graph;
-    /// Pointer to the length map
+    // Pointer to the length map
     void *_length;
-    ///Pointer to the map of predecessors arcs.
+    // Pointer to the map of predecessors arcs.
     void *_pred;
-    ///Pointer to the map of distances.
+    // Pointer to the map of distances.
     void *_dist;
-    ///Pointer to the source node.
-    Node _source;
+    //Pointer to the shortest path to the target node.
+    void *_path;
+    //Pointer to the distance of the target node.
+    void *_di;
 
     public:
     /// Constructor.
     
-    /// This constructor does not require parameters, therefore it initiates
-    /// all of the attributes to default values (0, INVALID).
-    BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
-			   _dist(0), _source(INVALID) {}
+    /// This constructor does not require parameters, it initiates
+    /// all of the attributes to default values \c 0.
+    BellmanFordWizardBase() :
+      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
 
     /// Constructor.
     
-    /// This constructor requires some parameters,
-    /// listed in the parameters list.
-    /// Others are initiated to 0.
-    /// \param digraph is the initial value of  \ref _graph
-    /// \param length is the initial value of  \ref _length
-    /// \param source is the initial value of  \ref _source
-    BellmanFordWizardBase(const _Digraph& digraph, 
-			  const _LengthMap& length, 
-			  Node source = INVALID) :
-      _graph(reinterpret_cast<void*>(const_cast<_Digraph*>(&digraph))), 
-      _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))), 
-      _pred(0), _dist(0), _source(source) {}
+    /// 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))), 
+      _pred(0), _dist(0), _path(0), _di(0) {}
 
   };
   
-  /// A class to make the usage of BellmanFord algorithm easier
+  /// \brief Auxiliary class for the function-type interface of the
+  /// \ref BellmanFord "Bellman-Ford" algorithm.
+  ///
+  /// This auxiliary class is created to implement the
+  /// \ref bellmanFord() "function-type interface" of the
+  /// \ref BellmanFord "Bellman-Ford" algorithm.
+  /// It does not have own \ref run() method, it uses the
+  /// functions and features of the plain \ref BellmanFord.
+  ///
+  /// This class should only be used through the \ref bellmanFord()
+  /// function, which makes it easier to use the algorithm.
+  template<class TR>
+  class BellmanFordWizard : public TR {
+    typedef TR Base;
 
-  /// This class is created to make it easier to use BellmanFord algorithm.
-  /// It uses the functions and features of the plain \ref BellmanFord,
-  /// but it is much simpler to use it.
-  ///
-  /// Simplicity means that the way to change the types defined
-  /// in the traits class is based on functions that returns the new class
-  /// and not on templatable built-in classes.
-  /// When using the plain \ref BellmanFord
-  /// the new class with the modified type comes from
-  /// the original class by using the ::
-  /// operator. In the case of \ref BellmanFordWizard only
-  /// a function have to be called and it will
-  /// return the needed class.
-  ///
-  /// It does not have own \ref run method. When its \ref run method is called
-  /// it initiates a plain \ref BellmanFord class, and calls the \ref 
-  /// BellmanFord::run method of it.
-  template<class _Traits>
-  class BellmanFordWizard : public _Traits {
-    typedef _Traits Base;
-
-    ///The type of the underlying digraph.
-    typedef typename _Traits::Digraph Digraph;
+    typedef typename TR::Digraph Digraph;
 
     typedef typename Digraph::Node Node;
     typedef typename Digraph::NodeIt NodeIt;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::OutArcIt ArcIt;
     
-    ///The type of the map that stores the arc lengths.
-    typedef typename _Traits::LengthMap LengthMap;
-
-    ///The type of the length of the arcs.
+    typedef typename TR::LengthMap LengthMap;
     typedef typename LengthMap::Value Value;
-
-    ///\brief The type of the map that stores the last
-    ///arcs of the shortest paths.
-    typedef typename _Traits::PredMap PredMap;
-
-    ///The type of the map that stores the dists of the nodes.
-    typedef typename _Traits::DistMap DistMap;
+    typedef typename TR::PredMap PredMap;
+    typedef typename TR::DistMap DistMap;
+    typedef typename TR::Path Path;
 
   public:
     /// Constructor.
-    BellmanFordWizard() : _Traits() {}
+    BellmanFordWizard() : TR() {}
 
     /// \brief Constructor that requires parameters.
     ///
     /// Constructor that requires parameters.
     /// These parameters will be the default values for the traits class.
-    BellmanFordWizard(const Digraph& digraph, const LengthMap& length, 
-		      Node src = INVALID) 
-      : _Traits(digraph, length, src) {}
+    /// \param gr The digraph the algorithm runs on.
+    /// \param len The length map.
+    BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
+      : TR(gr, len) {}
 
     /// \brief Copy constructor
-    BellmanFordWizard(const _Traits &b) : _Traits(b) {}
+    BellmanFordWizard(const TR &b) : TR(b) {}
 
     ~BellmanFordWizard() {}
 
-    /// \brief Runs BellmanFord algorithm from a given node.
+    /// \brief Runs the Bellman-Ford algorithm from the given source node.
     ///    
-    /// Runs BellmanFord algorithm from a given node.
-    /// The node can be given by the \ref source function.
-    void run() {
-      LEMON_ASSERT(Base::_source != INVALID, "Source node is not given");
-      BellmanFord<Digraph,LengthMap,_Traits> 
+    /// 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), 
            *reinterpret_cast<const LengthMap*>(Base::_length));
       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-      bf.run(Base::_source);
+      bf.run(s);
     }
 
-    /// \brief Runs BellmanFord algorithm from the given node.
+    /// \brief Runs the Bellman-Ford algorithm to find the shortest path
+    /// between \c s and \c t.
     ///
-    /// Runs BellmanFord algorithm from the given node.
-    /// \param src is the given source.
-    void run(Node src) {
-      Base::_source = src;
-      run();
+    /// This method runs the Bellman-Ford algorithm from node \c s
+    /// in order to compute the shortest path to node \c t.
+    /// Actually, it computes the shortest path to each node, but using
+    /// this function you can retrieve the distance and the shortest path
+    /// for a single target node easier.
+    ///
+    /// \return \c true if \c t is reachable form \c s.
+    bool run(Node s, Node t) {
+      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));
+      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
+      bf.run(s);
+      if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
+      if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
+      return bf.reached(t);
     }
 
     template<class T>
-    struct DefPredMapBase : public Base {
+    struct SetPredMapBase : public Base {
       typedef T PredMap;
       static PredMap *createPredMap(const Digraph &) { return 0; };
-      DefPredMapBase(const _Traits &b) : _Traits(b) {}
+      SetPredMapBase(const TR &b) : TR(b) {}
     };
     
-    ///\brief \ref named-templ-param "Named parameter"
-    ///function for setting PredMap type
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// the predecessor map.
     ///
-    /// \ref named-templ-param "Named parameter"
-    ///function for setting PredMap type
-    ///
+    /// \ref named-templ-param "Named parameter" for setting
+    /// the map that stores the predecessor arcs of the nodes.
     template<class T>
-    BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 
-    {
+    BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
-      return BellmanFordWizard<DefPredMapBase<T> >(*this);
+      return BellmanFordWizard<SetPredMapBase<T> >(*this);
     }
     
     template<class T>
-    struct DefDistMapBase : public Base {
+    struct SetDistMapBase : public Base {
       typedef T DistMap;
       static DistMap *createDistMap(const Digraph &) { return 0; };
-      DefDistMapBase(const _Traits &b) : _Traits(b) {}
+      SetDistMapBase(const TR &b) : TR(b) {}
     };
     
-    ///\brief \ref named-templ-param "Named parameter"
-    ///function for setting DistMap type
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// the distance map.
     ///
-    /// \ref named-templ-param "Named parameter"
-    ///function for setting DistMap type
-    ///
+    /// \ref named-templ-param "Named parameter" for setting
+    /// the map that stores the distances of the nodes calculated
+    /// by the algorithm.
     template<class T>
-    BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
+    BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
-      return BellmanFordWizard<DefDistMapBase<T> >(*this);
+      return BellmanFordWizard<SetDistMapBase<T> >(*this);
     }
 
     template<class T>
-    struct DefOperationTraitsBase : public Base {
-      typedef T OperationTraits;
-      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
+    struct SetPathBase : public Base {
+      typedef T Path;
+      SetPathBase(const TR &b) : TR(b) {}
     };
-    
-    ///\brief \ref named-templ-param "Named parameter"
-    ///function for setting OperationTraits type
+
+    /// \brief \ref named-func-param "Named parameter" for getting
+    /// the shortest path to the target node.
     ///
-    /// \ref named-templ-param "Named parameter"
-    ///function for setting OperationTraits type
+    /// \ref named-func-param "Named parameter" for getting
+    /// the shortest path to the target node.
+    template<class T>
+    BellmanFordWizard<SetPathBase<T> > path(const T &t)
+    {
+      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
+      return BellmanFordWizard<SetPathBase<T> >(*this);
+    }
+
+    /// \brief \ref named-func-param "Named parameter" for getting
+    /// the distance of the target node.
     ///
-    template<class T>
-    BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
-      return BellmanFordWizard<DefDistMapBase<T> >(*this);
-    }
-    
-    /// \brief Sets the source node, from which the BellmanFord algorithm runs.
-    ///
-    /// Sets the source node, from which the BellmanFord algorithm runs.
-    /// \param src is the source node.
-    BellmanFordWizard<_Traits>& source(Node src) {
-      Base::_source = src;
+    /// \ref named-func-param "Named parameter" for getting
+    /// the distance of the target node.
+    BellmanFordWizard dist(const Value &d)
+    {
+      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
       return *this;
     }
     
   };
   
-  /// \brief Function type interface for BellmanFord algorithm.
+  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
+  /// algorithm.
   ///
   /// \ingroup shortest_path
-  /// Function type interface for BellmanFord algorithm.
+  /// Function type interface for the \ref BellmanFord "Bellman-Ford"
+  /// algorithm.
   ///
   /// This function also has several \ref named-templ-func-param 
   /// "named parameters", they are declared as the members of class 
   /// \ref BellmanFordWizard.
-  /// The following
-  /// example shows how to use these parameters.
-  ///\code
-  /// bellmanford(g,length,source).predMap(preds).run();
-  ///\endcode
+  /// The following examples show how to use these parameters.
+  /// \code
+  ///   // Compute shortest path from node s to each node
+  ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
+  ///
+  ///   // Compute shortest path from s to t
+  ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
+  /// \endcode
   /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
   /// to the end of the parameter list.
   /// \sa BellmanFordWizard
   /// \sa BellmanFord
-  template<class _Digraph, class _LengthMap>
-  BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
-  bellmanFord(const _Digraph& digraph,
-	      const _LengthMap& length, 
-	      typename _Digraph::Node source = INVALID) {
-    return BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
-      (digraph, length, source);
+  template<typename GR, typename LEN>
+  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
+  bellmanFord(const GR& digraph,
+	      const LEN& length)
+  {
+    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
   }
 
 } //END OF NAMESPACE LEMON