Improvements and unifications for BellmanFord (#51)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 02 Aug 2009 13:24:46 +0200
changeset 6979496ed797f20
parent 696 c9b9da1a90a0
child 698 f9746e45246e
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.
lemon/bellman_ford.h
     1.1 --- a/lemon/bellman_ford.h	Fri Jul 24 23:19:43 2009 +0200
     1.2 +++ b/lemon/bellman_ford.h	Sun Aug 02 13:24:46 2009 +0200
     1.3 @@ -16,18 +16,18 @@
     1.4   *
     1.5   */
     1.6  
     1.7 -#ifndef LEMON_BELMANN_FORD_H
     1.8 -#define LEMON_BELMANN_FORD_H
     1.9 +#ifndef LEMON_BELLMAN_FORD_H
    1.10 +#define LEMON_BELLMAN_FORD_H
    1.11  
    1.12  /// \ingroup shortest_path
    1.13  /// \file
    1.14  /// \brief Bellman-Ford algorithm.
    1.15 -///
    1.16  
    1.17  #include <lemon/bits/path_dump.h>
    1.18  #include <lemon/core.h>
    1.19  #include <lemon/error.h>
    1.20  #include <lemon/maps.h>
    1.21 +#include <lemon/path.h>
    1.22  
    1.23  #include <limits>
    1.24  
    1.25 @@ -35,15 +35,17 @@
    1.26  
    1.27    /// \brief Default OperationTraits for the BellmanFord algorithm class.
    1.28    ///  
    1.29 -  /// It defines all computational operations and constants which are
    1.30 -  /// used in the Bellman-Ford algorithm. The default implementation
    1.31 -  /// is based on the numeric_limits class. If the numeric type does not
    1.32 -  /// have infinity value then the maximum value is used as extremal
    1.33 -  /// infinity value.
    1.34 +  /// This operation traits class defines all computational operations
    1.35 +  /// and constants that are used in the Bellman-Ford algorithm.
    1.36 +  /// The default implementation is based on the \c numeric_limits class.
    1.37 +  /// If the numeric type does not have infinity value, then the maximum
    1.38 +  /// value is used as extremal infinity value.
    1.39    template <
    1.40 -    typename Value, 
    1.41 -    bool has_infinity = std::numeric_limits<Value>::has_infinity>
    1.42 +    typename V, 
    1.43 +    bool has_inf = std::numeric_limits<V>::has_infinity>
    1.44    struct BellmanFordDefaultOperationTraits {
    1.45 +    /// \e
    1.46 +    typedef V Value;
    1.47      /// \brief Gives back the zero value of the type.
    1.48      static Value zero() {
    1.49        return static_cast<Value>(0);
    1.50 @@ -56,14 +58,16 @@
    1.51      static Value plus(const Value& left, const Value& right) {
    1.52        return left + right;
    1.53      }
    1.54 -    /// \brief Gives back true only if the first value less than the second.
    1.55 +    /// \brief Gives back \c true only if the first value is less than
    1.56 +    /// the second.
    1.57      static bool less(const Value& left, const Value& right) {
    1.58        return left < right;
    1.59      }
    1.60    };
    1.61  
    1.62 -  template <typename Value>
    1.63 -  struct BellmanFordDefaultOperationTraits<Value, false> {
    1.64 +  template <typename V>
    1.65 +  struct BellmanFordDefaultOperationTraits<V, false> {
    1.66 +    typedef V Value;
    1.67      static Value zero() {
    1.68        return static_cast<Value>(0);
    1.69      }
    1.70 @@ -82,26 +86,26 @@
    1.71    /// \brief Default traits class of BellmanFord class.
    1.72    ///
    1.73    /// Default traits class of BellmanFord class.
    1.74 -  /// \param _Digraph Digraph type.
    1.75 -  /// \param _LegthMap Type of length map.
    1.76 -  template<class _Digraph, class _LengthMap>
    1.77 +  /// \param GR The type of the digraph.
    1.78 +  /// \param LEN The type of the length map.
    1.79 +  template<typename GR, typename LEN>
    1.80    struct BellmanFordDefaultTraits {
    1.81 -    /// The digraph type the algorithm runs on. 
    1.82 -    typedef _Digraph Digraph;
    1.83 +    /// The type of the digraph the algorithm runs on. 
    1.84 +    typedef GR Digraph;
    1.85  
    1.86      /// \brief The type of the map that stores the arc lengths.
    1.87      ///
    1.88      /// The type of the map that stores the arc lengths.
    1.89 -    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    1.90 -    typedef _LengthMap LengthMap;
    1.91 +    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    1.92 +    typedef LEN LengthMap;
    1.93  
    1.94 -    // The type of the length of the arcs.
    1.95 -    typedef typename _LengthMap::Value Value;
    1.96 +    /// The type of the arc lengths.
    1.97 +    typedef typename LEN::Value Value;
    1.98  
    1.99      /// \brief Operation traits for Bellman-Ford algorithm.
   1.100      ///
   1.101 -    /// It defines the infinity type on the given Value type
   1.102 -    /// and the used operation.
   1.103 +    /// It defines the used operations and the infinity value for the
   1.104 +    /// given \c Value type.
   1.105      /// \see BellmanFordDefaultOperationTraits
   1.106      typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   1.107   
   1.108 @@ -110,33 +114,31 @@
   1.109      /// 
   1.110      /// The type of the map that stores the last
   1.111      /// arcs of the shortest paths.
   1.112 -    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.113 -    ///
   1.114 -    typedef typename Digraph::template NodeMap<typename _Digraph::Arc> PredMap;
   1.115 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.116 +    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   1.117  
   1.118 -    /// \brief Instantiates a PredMap.
   1.119 +    /// \brief Instantiates a \c PredMap.
   1.120      /// 
   1.121      /// This function instantiates a \ref PredMap. 
   1.122 -    /// \param digraph is the digraph, to which we would like to define the PredMap.
   1.123 -    static PredMap *createPredMap(const _Digraph& digraph) {
   1.124 -      return new PredMap(digraph);
   1.125 +    /// \param g is the digraph to which we would like to define the
   1.126 +    /// \ref PredMap.
   1.127 +    static PredMap *createPredMap(const GR& g) {
   1.128 +      return new PredMap(g);
   1.129      }
   1.130  
   1.131 -    /// \brief The type of the map that stores the dists of the nodes.
   1.132 +    /// \brief The type of the map that stores the distances of the nodes.
   1.133      ///
   1.134 -    /// The type of the map that stores the dists of the nodes.
   1.135 -    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.136 -    ///
   1.137 -    typedef typename Digraph::template NodeMap<typename _LengthMap::Value> 
   1.138 -    DistMap;
   1.139 +    /// The type of the map that stores the distances of the nodes.
   1.140 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.141 +    typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
   1.142  
   1.143 -    /// \brief Instantiates a DistMap.
   1.144 +    /// \brief Instantiates a \c DistMap.
   1.145      ///
   1.146      /// This function instantiates a \ref DistMap. 
   1.147 -    /// \param digraph is the digraph, to which we would like to define the 
   1.148 -    /// \ref DistMap
   1.149 -    static DistMap *createDistMap(const _Digraph& digraph) {
   1.150 -      return new DistMap(digraph);
   1.151 +    /// \param g is the digraph to which we would like to define the 
   1.152 +    /// \ref DistMap.
   1.153 +    static DistMap *createDistMap(const GR& g) {
   1.154 +      return new DistMap(g);
   1.155      }
   1.156  
   1.157    };
   1.158 @@ -144,106 +146,109 @@
   1.159    /// \brief %BellmanFord algorithm class.
   1.160    ///
   1.161    /// \ingroup shortest_path
   1.162 -  /// This class provides an efficient implementation of \c Bellman-Ford 
   1.163 -  /// algorithm. The arc lengths are passed to the algorithm using a
   1.164 +  /// This class provides an efficient implementation of the Bellman-Ford 
   1.165 +  /// algorithm. The maximum time complexity of the algorithm is
   1.166 +  /// <tt>O(ne)</tt>.
   1.167 +  ///
   1.168 +  /// The Bellman-Ford algorithm solves the single-source shortest path
   1.169 +  /// problem when the arcs can have negative lengths, but the digraph
   1.170 +  /// should not contain directed cycles with negative total length.
   1.171 +  /// If all arc costs are non-negative, consider to use the Dijkstra
   1.172 +  /// algorithm instead, since it is more efficient.
   1.173 +  ///
   1.174 +  /// The arc lengths are passed to the algorithm using a
   1.175    /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
   1.176 -  /// kind of length.
   1.177 +  /// kind of length. The type of the length values is determined by the
   1.178 +  /// \ref concepts::ReadMap::Value "Value" type of the length map.
   1.179    ///
   1.180 -  /// The Bellman-Ford algorithm solves the shortest path from one node
   1.181 -  /// problem when the arcs can have negative length but the digraph should
   1.182 -  /// not contain cycles with negative sum of length. If we can assume
   1.183 -  /// that all arc is non-negative in the digraph then the dijkstra algorithm
   1.184 -  /// should be used rather.
   1.185 +  /// There is also a \ref bellmanFord() "function-type interface" for the
   1.186 +  /// Bellman-Ford algorithm, which is convenient in the simplier cases and
   1.187 +  /// it can be used easier.
   1.188    ///
   1.189 -  /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
   1.190 -  ///
   1.191 -  /// The type of the length is determined by the
   1.192 -  /// \ref concepts::ReadMap::Value "Value" of the length map.
   1.193 -  ///
   1.194 -  /// \param _Digraph The digraph type the algorithm runs on. The default value
   1.195 -  /// is \ref ListDigraph. The value of _Digraph is not used directly by
   1.196 -  /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
   1.197 -  /// \param _LengthMap This read-only ArcMap determines the lengths of the
   1.198 -  /// arcs. The default map type is \ref concepts::Digraph::ArcMap 
   1.199 -  /// "Digraph::ArcMap<int>".  The value of _LengthMap is not used directly 
   1.200 -  /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.  
   1.201 -  /// \param _Traits Traits class to set various data types used by the 
   1.202 -  /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
   1.203 -  /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>".  See \ref
   1.204 -  /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
   1.205 -  /// class.
   1.206 +  /// \tparam GR The type of the digraph the algorithm runs on.
   1.207 +  /// The default type is \ref ListDigraph.
   1.208 +  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
   1.209 +  /// the lengths of the arcs. The default map type is
   1.210 +  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   1.211  #ifdef DOXYGEN
   1.212 -  template <typename _Digraph, typename _LengthMap, typename _Traits>
   1.213 +  template <typename GR, typename LEN, typename TR>
   1.214  #else
   1.215 -  template <typename _Digraph,
   1.216 -	    typename _LengthMap=typename _Digraph::template ArcMap<int>,
   1.217 -	    typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> >
   1.218 +  template <typename GR=ListDigraph,
   1.219 +            typename LEN=typename GR::template ArcMap<int>,
   1.220 +            typename TR=BellmanFordDefaultTraits<GR,LEN> >
   1.221  #endif
   1.222    class BellmanFord {
   1.223    public:
   1.224  
   1.225 -    typedef _Traits Traits;
   1.226      ///The type of the underlying digraph.
   1.227 -    typedef typename _Traits::Digraph Digraph;
   1.228 +    typedef typename TR::Digraph Digraph;
   1.229 +    
   1.230 +    /// \brief The type of the arc lengths.
   1.231 +    typedef typename TR::LengthMap::Value Value;
   1.232 +    /// \brief The type of the map that stores the arc lengths.
   1.233 +    typedef typename TR::LengthMap LengthMap;
   1.234 +    /// \brief The type of the map that stores the last
   1.235 +    /// arcs of the shortest paths.
   1.236 +    typedef typename TR::PredMap PredMap;
   1.237 +    /// \brief The type of the map that stores the distances of the nodes.
   1.238 +    typedef typename TR::DistMap DistMap;
   1.239 +    /// The type of the paths.
   1.240 +    typedef PredMapPath<Digraph, PredMap> Path;
   1.241 +    ///\brief The \ref BellmanFordDefaultOperationTraits
   1.242 +    /// "operation traits class" of the algorithm.
   1.243 +    typedef typename TR::OperationTraits OperationTraits;
   1.244 +
   1.245 +    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
   1.246 +    typedef TR Traits;
   1.247 +
   1.248 +  private:
   1.249  
   1.250      typedef typename Digraph::Node Node;
   1.251      typedef typename Digraph::NodeIt NodeIt;
   1.252      typedef typename Digraph::Arc Arc;
   1.253      typedef typename Digraph::OutArcIt OutArcIt;
   1.254 -    
   1.255 -    /// \brief The type of the length of the arcs.
   1.256 -    typedef typename _Traits::LengthMap::Value Value;
   1.257 -    /// \brief The type of the map that stores the arc lengths.
   1.258 -    typedef typename _Traits::LengthMap LengthMap;
   1.259 -    /// \brief The type of the map that stores the last
   1.260 -    /// arcs of the shortest paths.
   1.261 -    typedef typename _Traits::PredMap PredMap;
   1.262 -    /// \brief The type of the map that stores the dists of the nodes.
   1.263 -    typedef typename _Traits::DistMap DistMap;
   1.264 -    /// \brief The operation traits.
   1.265 -    typedef typename _Traits::OperationTraits OperationTraits;
   1.266 -  private:
   1.267 -    /// Pointer to the underlying digraph.
   1.268 -    const Digraph *digraph;
   1.269 -    /// Pointer to the length map
   1.270 -    const LengthMap *length;
   1.271 -    ///Pointer to the map of predecessors arcs.
   1.272 +
   1.273 +    // Pointer to the underlying digraph.
   1.274 +    const Digraph *_gr;
   1.275 +    // Pointer to the length map
   1.276 +    const LengthMap *_length;
   1.277 +    // Pointer to the map of predecessors arcs.
   1.278      PredMap *_pred;
   1.279 -    ///Indicates if \ref _pred is locally allocated (\c true) or not.
   1.280 -    bool local_pred;
   1.281 -    ///Pointer to the map of distances.
   1.282 +    // Indicates if _pred is locally allocated (true) or not.
   1.283 +    bool _local_pred;
   1.284 +    // Pointer to the map of distances.
   1.285      DistMap *_dist;
   1.286 -    ///Indicates if \ref _dist is locally allocated (\c true) or not.
   1.287 -    bool local_dist;
   1.288 +    // Indicates if _dist is locally allocated (true) or not.
   1.289 +    bool _local_dist;
   1.290  
   1.291      typedef typename Digraph::template NodeMap<bool> MaskMap;
   1.292      MaskMap *_mask;
   1.293  
   1.294      std::vector<Node> _process;
   1.295  
   1.296 -    /// Creates the maps if necessary.
   1.297 +    // Creates the maps if necessary.
   1.298      void create_maps() {
   1.299        if(!_pred) {
   1.300 -	local_pred = true;
   1.301 -	_pred = Traits::createPredMap(*digraph);
   1.302 +	_local_pred = true;
   1.303 +	_pred = Traits::createPredMap(*_gr);
   1.304        }
   1.305        if(!_dist) {
   1.306 -	local_dist = true;
   1.307 -	_dist = Traits::createDistMap(*digraph);
   1.308 +	_local_dist = true;
   1.309 +	_dist = Traits::createDistMap(*_gr);
   1.310        }
   1.311 -      _mask = new MaskMap(*digraph, false);
   1.312 +      _mask = new MaskMap(*_gr, false);
   1.313      }
   1.314      
   1.315    public :
   1.316   
   1.317      typedef BellmanFord Create;
   1.318  
   1.319 -    /// \name Named template parameters
   1.320 +    /// \name Named Template Parameters
   1.321  
   1.322      ///@{
   1.323  
   1.324      template <class T>
   1.325 -    struct DefPredMapTraits : public Traits {
   1.326 +    struct SetPredMapTraits : public Traits {
   1.327        typedef T PredMap;
   1.328        static PredMap *createPredMap(const Digraph&) {
   1.329          LEMON_ASSERT(false, "PredMap is not initialized");
   1.330 @@ -251,18 +256,20 @@
   1.331        }
   1.332      };
   1.333  
   1.334 -    /// \brief \ref named-templ-param "Named parameter" for setting PredMap 
   1.335 -    /// type
   1.336 -    /// \ref named-templ-param "Named parameter" for setting PredMap type
   1.337 +    /// \brief \ref named-templ-param "Named parameter" for setting
   1.338 +    /// \c PredMap type.
   1.339      ///
   1.340 +    /// \ref named-templ-param "Named parameter" for setting
   1.341 +    /// \c PredMap type.
   1.342 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.343      template <class T>
   1.344      struct SetPredMap 
   1.345 -      : public BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > {
   1.346 -      typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > Create;
   1.347 +      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
   1.348 +      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   1.349      };
   1.350      
   1.351      template <class T>
   1.352 -    struct DefDistMapTraits : public Traits {
   1.353 +    struct SetDistMapTraits : public Traits {
   1.354        typedef T DistMap;
   1.355        static DistMap *createDistMap(const Digraph&) {
   1.356          LEMON_ASSERT(false, "DistMap is not initialized");
   1.357 @@ -270,31 +277,33 @@
   1.358        }
   1.359      };
   1.360  
   1.361 -    /// \brief \ref named-templ-param "Named parameter" for setting DistMap 
   1.362 -    /// type
   1.363 +    /// \brief \ref named-templ-param "Named parameter" for setting
   1.364 +    /// \c DistMap type.
   1.365      ///
   1.366 -    /// \ref named-templ-param "Named parameter" for setting DistMap type
   1.367 -    ///
   1.368 +    /// \ref named-templ-param "Named parameter" for setting
   1.369 +    /// \c DistMap type.
   1.370 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.371      template <class T>
   1.372      struct SetDistMap 
   1.373 -      : public BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > {
   1.374 -      typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > Create;
   1.375 +      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
   1.376 +      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   1.377      };
   1.378 -    
   1.379 +
   1.380      template <class T>
   1.381 -    struct DefOperationTraitsTraits : public Traits {
   1.382 +    struct SetOperationTraitsTraits : public Traits {
   1.383        typedef T OperationTraits;
   1.384      };
   1.385      
   1.386      /// \brief \ref named-templ-param "Named parameter" for setting 
   1.387 -    /// OperationTraits type
   1.388 +    /// \c OperationTraits type.
   1.389      ///
   1.390 -    /// \ref named-templ-param "Named parameter" for setting OperationTraits
   1.391 -    /// type
   1.392 +    /// \ref named-templ-param "Named parameter" for setting
   1.393 +    /// \c OperationTraits type.
   1.394 +    /// For more information see \ref BellmanFordDefaultOperationTraits.
   1.395      template <class T>
   1.396      struct SetOperationTraits
   1.397 -      : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> > {
   1.398 -      typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> >
   1.399 +      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   1.400 +      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
   1.401        Create;
   1.402      };
   1.403      
   1.404 @@ -308,85 +317,89 @@
   1.405      
   1.406      /// \brief Constructor.
   1.407      ///
   1.408 -    /// \param _graph the digraph the algorithm will run on.
   1.409 -    /// \param _length the length map used by the algorithm.
   1.410 -    BellmanFord(const Digraph& _graph, const LengthMap& _length) :
   1.411 -      digraph(&_graph), length(&_length),
   1.412 -      _pred(0), local_pred(false),
   1.413 -      _dist(0), local_dist(false), _mask(0) {}
   1.414 +    /// Constructor.
   1.415 +    /// \param g The digraph the algorithm runs on.
   1.416 +    /// \param length The length map used by the algorithm.
   1.417 +    BellmanFord(const Digraph& g, const LengthMap& length) :
   1.418 +      _gr(&g), _length(&length),
   1.419 +      _pred(0), _local_pred(false),
   1.420 +      _dist(0), _local_dist(false), _mask(0) {}
   1.421      
   1.422      ///Destructor.
   1.423      ~BellmanFord() {
   1.424 -      if(local_pred) delete _pred;
   1.425 -      if(local_dist) delete _dist;
   1.426 +      if(_local_pred) delete _pred;
   1.427 +      if(_local_dist) delete _dist;
   1.428        if(_mask) delete _mask;
   1.429      }
   1.430  
   1.431      /// \brief Sets the length map.
   1.432      ///
   1.433      /// Sets the length map.
   1.434 -    /// \return \c (*this)
   1.435 -    BellmanFord &lengthMap(const LengthMap &m) {
   1.436 -      length = &m;
   1.437 +    /// \return <tt>(*this)</tt>
   1.438 +    BellmanFord &lengthMap(const LengthMap &map) {
   1.439 +      _length = &map;
   1.440        return *this;
   1.441      }
   1.442  
   1.443 -    /// \brief Sets the map storing the predecessor arcs.
   1.444 +    /// \brief Sets the map that stores the predecessor arcs.
   1.445      ///
   1.446 -    /// Sets the map storing the predecessor arcs.
   1.447 -    /// If you don't use this function before calling \ref run(),
   1.448 -    /// it will allocate one. The destuctor deallocates this
   1.449 -    /// automatically allocated map, of course.
   1.450 -    /// \return \c (*this)
   1.451 -    BellmanFord &predMap(PredMap &m) {
   1.452 -      if(local_pred) {
   1.453 +    /// Sets the map that stores the predecessor arcs.
   1.454 +    /// If you don't use this function before calling \ref run()
   1.455 +    /// or \ref init(), an instance will be allocated automatically.
   1.456 +    /// The destructor deallocates this automatically allocated map,
   1.457 +    /// of course.
   1.458 +    /// \return <tt>(*this)</tt>
   1.459 +    BellmanFord &predMap(PredMap &map) {
   1.460 +      if(_local_pred) {
   1.461  	delete _pred;
   1.462 -	local_pred=false;
   1.463 +	_local_pred=false;
   1.464        }
   1.465 -      _pred = &m;
   1.466 +      _pred = &map;
   1.467        return *this;
   1.468      }
   1.469  
   1.470 -    /// \brief Sets the map storing the distances calculated by the algorithm.
   1.471 +    /// \brief Sets the map that stores the distances of the nodes.
   1.472      ///
   1.473 -    /// Sets the map storing the distances calculated by the algorithm.
   1.474 -    /// If you don't use this function before calling \ref run(),
   1.475 -    /// it will allocate one. The destuctor deallocates this
   1.476 -    /// automatically allocated map, of course.
   1.477 -    /// \return \c (*this)
   1.478 -    BellmanFord &distMap(DistMap &m) {
   1.479 -      if(local_dist) {
   1.480 +    /// Sets the map that stores the distances of the nodes calculated
   1.481 +    /// by the algorithm.
   1.482 +    /// If you don't use this function before calling \ref run()
   1.483 +    /// or \ref init(), an instance will be allocated automatically.
   1.484 +    /// The destructor deallocates this automatically allocated map,
   1.485 +    /// of course.
   1.486 +    /// \return <tt>(*this)</tt>
   1.487 +    BellmanFord &distMap(DistMap &map) {
   1.488 +      if(_local_dist) {
   1.489  	delete _dist;
   1.490 -	local_dist=false;
   1.491 +	_local_dist=false;
   1.492        }
   1.493 -      _dist = &m;
   1.494 +      _dist = &map;
   1.495        return *this;
   1.496      }
   1.497  
   1.498 -    /// \name Execution control
   1.499 -    /// The simplest way to execute the algorithm is to use
   1.500 -    /// one of the member functions called \c run(...).
   1.501 -    /// \n
   1.502 -    /// If you need more control on the execution,
   1.503 -    /// first you must call \ref init(), then you can add several source nodes
   1.504 -    /// with \ref addSource().
   1.505 -    /// Finally \ref start() will perform the actual path
   1.506 -    /// computation.
   1.507 +    /// \name Execution Control
   1.508 +    /// The simplest way to execute the Bellman-Ford algorithm is to use
   1.509 +    /// one of the member functions called \ref run().\n
   1.510 +    /// If you need better control on the execution, you have to call
   1.511 +    /// \ref init() first, then you can add several source nodes
   1.512 +    /// with \ref addSource(). Finally the actual path computation can be
   1.513 +    /// performed with \ref start(), \ref checkedStart() or
   1.514 +    /// \ref limitedStart().
   1.515  
   1.516      ///@{
   1.517  
   1.518      /// \brief Initializes the internal data structures.
   1.519      /// 
   1.520 -    /// Initializes the internal data structures.
   1.521 +    /// Initializes the internal data structures. The optional parameter
   1.522 +    /// is the initial distance of each node.
   1.523      void init(const Value value = OperationTraits::infinity()) {
   1.524        create_maps();
   1.525 -      for (NodeIt it(*digraph); it != INVALID; ++it) {
   1.526 +      for (NodeIt it(*_gr); it != INVALID; ++it) {
   1.527  	_pred->set(it, INVALID);
   1.528  	_dist->set(it, value);
   1.529        }
   1.530        _process.clear();
   1.531        if (OperationTraits::less(value, OperationTraits::infinity())) {
   1.532 -	for (NodeIt it(*digraph); it != INVALID; ++it) {
   1.533 +	for (NodeIt it(*_gr); it != INVALID; ++it) {
   1.534  	  _process.push_back(it);
   1.535  	  _mask->set(it, true);
   1.536  	}
   1.537 @@ -395,9 +408,8 @@
   1.538      
   1.539      /// \brief Adds a new source node.
   1.540      ///
   1.541 -    /// Adds a new source node. The optional second parameter is the 
   1.542 -    /// initial distance of the node. It just sets the distance of the 
   1.543 -    /// node to the given value.
   1.544 +    /// This function adds a new source node. The optional second parameter
   1.545 +    /// is the initial distance of the node.
   1.546      void addSource(Node source, Value dst = OperationTraits::zero()) {
   1.547        _dist->set(source, dst);
   1.548        if (!(*_mask)[source]) {
   1.549 @@ -409,19 +421,22 @@
   1.550      /// \brief Executes one round from the Bellman-Ford algorithm.
   1.551      ///
   1.552      /// If the algoritm calculated the distances in the previous round
   1.553 -    /// exactly for all at most \f$ k \f$ length path lengths then it will
   1.554 -    /// calculate the distances exactly for all at most \f$ k + 1 \f$
   1.555 -    /// length path lengths. With \f$ k \f$ iteration this function
   1.556 -    /// calculates the at most \f$ k \f$ length path lengths.
   1.557 +    /// exactly for the paths of at most \c k arcs, then this function
   1.558 +    /// will calculate the distances exactly for the paths of at most
   1.559 +    /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
   1.560 +    /// calculates the shortest path distances exactly for the paths
   1.561 +    /// consisting of at most \c k arcs.
   1.562      ///
   1.563      /// \warning The paths with limited arc number cannot be retrieved
   1.564 -    /// easily with \ref path() or \ref predArc() functions. If you
   1.565 -    /// need the shortest path and not just the distance you should store
   1.566 -    /// after each iteration the \ref predMap() map and manually build
   1.567 -    /// the path.
   1.568 +    /// easily with \ref path() or \ref predArc() functions. If you also
   1.569 +    /// need the shortest paths and not only the distances, you should
   1.570 +    /// store the \ref predMap() "predecessor map" after each iteration
   1.571 +    /// and build the path manually.
   1.572      ///
   1.573      /// \return \c true when the algorithm have not found more shorter
   1.574      /// paths.
   1.575 +    ///
   1.576 +    /// \see ActiveIt
   1.577      bool processNextRound() {
   1.578        for (int i = 0; i < int(_process.size()); ++i) {
   1.579  	_mask->set(_process[i], false);
   1.580 @@ -432,9 +447,9 @@
   1.581  	values[i] = (*_dist)[_process[i]];
   1.582        }
   1.583        for (int i = 0; i < int(_process.size()); ++i) {
   1.584 -	for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
   1.585 -	  Node target = digraph->target(it);
   1.586 -	  Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
   1.587 +	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   1.588 +	  Node target = _gr->target(it);
   1.589 +	  Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
   1.590  	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
   1.591  	    _pred->set(target, it);
   1.592  	    _dist->set(target, relaxed);
   1.593 @@ -451,23 +466,28 @@
   1.594  
   1.595      /// \brief Executes one weak round from the Bellman-Ford algorithm.
   1.596      ///
   1.597 -    /// If the algorithm calculated the distances in the
   1.598 -    /// previous round at least for all at most k length paths then it will
   1.599 -    /// calculate the distances at least for all at most k + 1 length paths.
   1.600 -    /// This function does not make it possible to calculate strictly the
   1.601 -    /// at most k length minimal paths, this is why it is
   1.602 -    /// called just weak round.
   1.603 -    /// \return \c true when the algorithm have not found more shorter paths.
   1.604 +    /// If the algorithm calculated the distances in the previous round
   1.605 +    /// at least for the paths of at most \c k arcs, then this function
   1.606 +    /// will calculate the distances at least for the paths of at most
   1.607 +    /// <tt>k+1</tt> arcs.
   1.608 +    /// This function does not make it possible to calculate the shortest
   1.609 +    /// path distances exactly for paths consisting of at most \c k arcs,
   1.610 +    /// this is why it is called weak round.
   1.611 +    ///
   1.612 +    /// \return \c true when the algorithm have not found more shorter
   1.613 +    /// paths.
   1.614 +    ///
   1.615 +    /// \see ActiveIt
   1.616      bool processNextWeakRound() {
   1.617        for (int i = 0; i < int(_process.size()); ++i) {
   1.618  	_mask->set(_process[i], false);
   1.619        }
   1.620        std::vector<Node> nextProcess;
   1.621        for (int i = 0; i < int(_process.size()); ++i) {
   1.622 -	for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
   1.623 -	  Node target = digraph->target(it);
   1.624 +	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   1.625 +	  Node target = _gr->target(it);
   1.626  	  Value relaxed = 
   1.627 -	    OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
   1.628 +	    OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
   1.629  	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
   1.630  	    _pred->set(target, it);
   1.631  	    _dist->set(target, relaxed);
   1.632 @@ -484,16 +504,19 @@
   1.633  
   1.634      /// \brief Executes the algorithm.
   1.635      ///
   1.636 -    /// \pre init() must be called and at least one node should be added
   1.637 -    /// with addSource() before using this function.
   1.638 +    /// Executes the algorithm.
   1.639      ///
   1.640 -    /// This method runs the %BellmanFord algorithm from the root node(s)
   1.641 -    /// in order to compute the shortest path to each node. The algorithm 
   1.642 -    /// computes 
   1.643 -    /// - The shortest path tree.
   1.644 -    /// - The distance of each node from the root(s).
   1.645 +    /// This method runs the Bellman-Ford algorithm from the root node(s)
   1.646 +    /// in order to compute the shortest path to each node.
   1.647 +    ///
   1.648 +    /// The algorithm computes
   1.649 +    /// - the shortest path tree (forest),
   1.650 +    /// - the distance of each node from the root(s).
   1.651 +    ///
   1.652 +    /// \pre init() must be called and at least one root node should be
   1.653 +    /// added with addSource() before using this function.
   1.654      void start() {
   1.655 -      int num = countNodes(*digraph) - 1;
   1.656 +      int num = countNodes(*_gr) - 1;
   1.657        for (int i = 0; i < num; ++i) {
   1.658  	if (processNextWeakRound()) break;
   1.659        }
   1.660 @@ -501,83 +524,98 @@
   1.661  
   1.662      /// \brief Executes the algorithm and checks the negative cycles.
   1.663      ///
   1.664 -    /// \pre init() must be called and at least one node should be added
   1.665 -    /// with addSource() before using this function. 
   1.666 +    /// Executes the algorithm and checks the negative cycles.
   1.667      ///
   1.668 -    /// This method runs the %BellmanFord algorithm from the root node(s)
   1.669 -    /// in order to compute the shortest path to each node. The algorithm 
   1.670 -    /// computes 
   1.671 -    /// - The shortest path tree.
   1.672 -    /// - The distance of each node from the root(s).
   1.673 +    /// This method runs the Bellman-Ford algorithm from the root node(s)
   1.674 +    /// in order to compute the shortest path to each node and also checks
   1.675 +    /// if the digraph contains cycles with negative total length.
   1.676 +    ///
   1.677 +    /// The algorithm computes 
   1.678 +    /// - the shortest path tree (forest),
   1.679 +    /// - the distance of each node from the root(s).
   1.680      /// 
   1.681      /// \return \c false if there is a negative cycle in the digraph.
   1.682 +    ///
   1.683 +    /// \pre init() must be called and at least one root node should be
   1.684 +    /// added with addSource() before using this function. 
   1.685      bool checkedStart() {
   1.686 -      int num = countNodes(*digraph);
   1.687 +      int num = countNodes(*_gr);
   1.688        for (int i = 0; i < num; ++i) {
   1.689  	if (processNextWeakRound()) return true;
   1.690        }
   1.691        return _process.empty();
   1.692      }
   1.693  
   1.694 -    /// \brief Executes the algorithm with path length limit.
   1.695 +    /// \brief Executes the algorithm with arc number limit.
   1.696      ///
   1.697 -    /// \pre init() must be called and at least one node should be added
   1.698 -    /// with addSource() before using this function.
   1.699 +    /// Executes the algorithm with arc number limit.
   1.700      ///
   1.701 -    /// This method runs the %BellmanFord algorithm from the root
   1.702 -    /// node(s) in order to compute the shortest path lengths with at
   1.703 -    /// most \c num arc.
   1.704 +    /// This method runs the Bellman-Ford algorithm from the root node(s)
   1.705 +    /// in order to compute the shortest path distance for each node
   1.706 +    /// using only the paths consisting of at most \c num arcs.
   1.707 +    ///
   1.708 +    /// The algorithm computes
   1.709 +    /// - the limited distance of each node from the root(s),
   1.710 +    /// - the predecessor arc for each node.
   1.711      ///
   1.712      /// \warning The paths with limited arc number cannot be retrieved
   1.713 -    /// easily with \ref path() or \ref predArc() functions. If you
   1.714 -    /// need the shortest path and not just the distance you should store
   1.715 -    /// after each iteration the \ref predMap() map and manually build
   1.716 -    /// the path.
   1.717 +    /// easily with \ref path() or \ref predArc() functions. If you also
   1.718 +    /// need the shortest paths and not only the distances, you should
   1.719 +    /// store the \ref predMap() "predecessor map" after each iteration
   1.720 +    /// and build the path manually.
   1.721      ///
   1.722 -    /// The algorithm computes
   1.723 -    /// - The predecessor arc from each node.
   1.724 -    /// - The limited distance of each node from the root(s).
   1.725 +    /// \pre init() must be called and at least one root node should be
   1.726 +    /// added with addSource() before using this function. 
   1.727      void limitedStart(int num) {
   1.728        for (int i = 0; i < num; ++i) {
   1.729  	if (processNextRound()) break;
   1.730        }
   1.731      }
   1.732      
   1.733 -    /// \brief Runs %BellmanFord algorithm from node \c s.
   1.734 +    /// \brief Runs the algorithm from the given root node.
   1.735      ///    
   1.736 -    /// This method runs the %BellmanFord algorithm from a root node \c s
   1.737 -    /// in order to compute the shortest path to each node. The algorithm 
   1.738 -    /// computes
   1.739 -    /// - The shortest path tree.
   1.740 -    /// - The distance of each node from the root.
   1.741 +    /// This method runs the Bellman-Ford algorithm from the given root
   1.742 +    /// node \c s in order to compute the shortest path to each node.
   1.743      ///
   1.744 -    /// \note d.run(s) is just a shortcut of the following code.
   1.745 -    ///\code
   1.746 -    ///  d.init();
   1.747 -    ///  d.addSource(s);
   1.748 -    ///  d.start();
   1.749 -    ///\endcode
   1.750 +    /// The algorithm computes
   1.751 +    /// - the shortest path tree (forest),
   1.752 +    /// - the distance of each node from the root(s).
   1.753 +    ///
   1.754 +    /// \note bf.run(s) is just a shortcut of the following code.
   1.755 +    /// \code
   1.756 +    ///   bf.init();
   1.757 +    ///   bf.addSource(s);
   1.758 +    ///   bf.start();
   1.759 +    /// \endcode
   1.760      void run(Node s) {
   1.761        init();
   1.762        addSource(s);
   1.763        start();
   1.764      }
   1.765      
   1.766 -    /// \brief Runs %BellmanFord algorithm with limited path length 
   1.767 -    /// from node \c s.
   1.768 +    /// \brief Runs the algorithm from the given root node with arc
   1.769 +    /// number limit.
   1.770      ///    
   1.771 -    /// This method runs the %BellmanFord algorithm from a root node \c s
   1.772 -    /// in order to compute the shortest path with at most \c len arcs 
   1.773 -    /// to each node. The algorithm computes
   1.774 -    /// - The shortest path tree.
   1.775 -    /// - The distance of each node from the root.
   1.776 +    /// This method runs the Bellman-Ford algorithm from the given root
   1.777 +    /// node \c s in order to compute the shortest path distance for each
   1.778 +    /// node using only the paths consisting of at most \c num arcs.
   1.779      ///
   1.780 -    /// \note d.run(s, num) is just a shortcut of the following code.
   1.781 -    ///\code
   1.782 -    ///  d.init();
   1.783 -    ///  d.addSource(s);
   1.784 -    ///  d.limitedStart(num);
   1.785 -    ///\endcode
   1.786 +    /// The algorithm computes
   1.787 +    /// - the limited distance of each node from the root(s),
   1.788 +    /// - the predecessor arc for each node.
   1.789 +    ///
   1.790 +    /// \warning The paths with limited arc number cannot be retrieved
   1.791 +    /// easily with \ref path() or \ref predArc() functions. If you also
   1.792 +    /// need the shortest paths and not only the distances, you should
   1.793 +    /// store the \ref predMap() "predecessor map" after each iteration
   1.794 +    /// and build the path manually.
   1.795 +    ///
   1.796 +    /// \note bf.run(s, num) is just a shortcut of the following code.
   1.797 +    /// \code
   1.798 +    ///   bf.init();
   1.799 +    ///   bf.addSource(s);
   1.800 +    ///   bf.limitedStart(num);
   1.801 +    /// \endcode
   1.802      void run(Node s, int num) {
   1.803        init();
   1.804        addSource(s);
   1.805 @@ -586,27 +624,19 @@
   1.806      
   1.807      ///@}
   1.808  
   1.809 -    /// \name Query Functions
   1.810 -    /// The result of the %BellmanFord algorithm can be obtained using these
   1.811 -    /// functions.\n
   1.812 -    /// Before the use of these functions,
   1.813 -    /// either run() or start() must be called.
   1.814 -    
   1.815 -    ///@{
   1.816 -
   1.817 -    /// \brief Lemon iterator for get the active nodes.
   1.818 +    /// \brief LEMON iterator for getting the active nodes.
   1.819      ///
   1.820 -    /// Lemon iterator for get the active nodes. This class provides a
   1.821 -    /// common style lemon iterator which gives back a subset of the
   1.822 -    /// nodes. The iterated nodes are active in the algorithm after
   1.823 -    /// the last phase so these should be checked in the next phase to
   1.824 -    /// find augmenting arcs from these.
   1.825 +    /// This class provides a common style LEMON iterator that traverses
   1.826 +    /// the active nodes of the Bellman-Ford algorithm after the last
   1.827 +    /// phase. These nodes should be checked in the next phase to
   1.828 +    /// find augmenting arcs outgoing from them.
   1.829      class ActiveIt {
   1.830      public:
   1.831  
   1.832        /// \brief Constructor.
   1.833        ///
   1.834 -      /// Constructor for get the nodeset of the variable. 
   1.835 +      /// Constructor for getting the active nodes of the given BellmanFord
   1.836 +      /// instance. 
   1.837        ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
   1.838        {
   1.839          _index = _algorithm->_process.size() - 1;
   1.840 @@ -617,9 +647,9 @@
   1.841        /// Invalid constructor.
   1.842        ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
   1.843  
   1.844 -      /// \brief Conversion to node.
   1.845 +      /// \brief Conversion to \c Node.
   1.846        ///
   1.847 -      /// Conversion to node.
   1.848 +      /// Conversion to \c Node.
   1.849        operator Node() const { 
   1.850          return _index >= 0 ? _algorithm->_process[_index] : INVALID;
   1.851        }
   1.852 @@ -646,394 +676,432 @@
   1.853        const BellmanFord* _algorithm;
   1.854        int _index;
   1.855      };
   1.856 +    
   1.857 +    /// \name Query Functions
   1.858 +    /// The result of the Bellman-Ford algorithm can be obtained using these
   1.859 +    /// functions.\n
   1.860 +    /// Either \ref run() or \ref init() should be called before using them.
   1.861 +    
   1.862 +    ///@{
   1.863  
   1.864 -    typedef PredMapPath<Digraph, PredMap> Path;
   1.865 +    /// \brief The shortest path to the given node.
   1.866 +    ///    
   1.867 +    /// Gives back the shortest path to the given node from the root(s).
   1.868 +    ///
   1.869 +    /// \warning \c t should be reached from the root(s).
   1.870 +    ///
   1.871 +    /// \pre Either \ref run() or \ref init() must be called before
   1.872 +    /// using this function.
   1.873 +    Path path(Node t) const
   1.874 +    {
   1.875 +      return Path(*_gr, *_pred, t);
   1.876 +    }
   1.877 +	  
   1.878 +    /// \brief The distance of the given node from the root(s).
   1.879 +    ///
   1.880 +    /// Returns the distance of the given node from the root(s).
   1.881 +    ///
   1.882 +    /// \warning If node \c v is not reached from the root(s), then
   1.883 +    /// the return value of this function is undefined.
   1.884 +    ///
   1.885 +    /// \pre Either \ref run() or \ref init() must be called before
   1.886 +    /// using this function.
   1.887 +    Value dist(Node v) const { return (*_dist)[v]; }
   1.888  
   1.889 -    /// \brief Gives back the shortest path.
   1.890 -    ///    
   1.891 -    /// Gives back the shortest path.
   1.892 -    /// \pre The \c t should be reachable from the source.
   1.893 -    Path path(Node t) 
   1.894 -    {
   1.895 -      return Path(*digraph, *_pred, t);
   1.896 +    /// \brief Returns the 'previous arc' of the shortest path tree for
   1.897 +    /// the given node.
   1.898 +    ///
   1.899 +    /// This function returns the 'previous arc' of the shortest path
   1.900 +    /// tree for node \c v, i.e. it returns the last arc of a
   1.901 +    /// shortest path from a root to \c v. It is \c INVALID if \c v
   1.902 +    /// is not reached from the root(s) or if \c v is a root.
   1.903 +    ///
   1.904 +    /// The shortest path tree used here is equal to the shortest path
   1.905 +    /// tree used in \ref predNode() and \predMap().
   1.906 +    ///
   1.907 +    /// \pre Either \ref run() or \ref init() must be called before
   1.908 +    /// using this function.
   1.909 +    Arc predArc(Node v) const { return (*_pred)[v]; }
   1.910 +
   1.911 +    /// \brief Returns the 'previous node' of the shortest path tree for
   1.912 +    /// the given node.
   1.913 +    ///
   1.914 +    /// This function returns the 'previous node' of the shortest path
   1.915 +    /// tree for node \c v, i.e. it returns the last but one node of
   1.916 +    /// a shortest path from a root to \c v. It is \c INVALID if \c v
   1.917 +    /// is not reached from the root(s) or if \c v is a root.
   1.918 +    ///
   1.919 +    /// The shortest path tree used here is equal to the shortest path
   1.920 +    /// tree used in \ref predArc() and \predMap().
   1.921 +    ///
   1.922 +    /// \pre Either \ref run() or \ref init() must be called before
   1.923 +    /// using this function.
   1.924 +    Node predNode(Node v) const { 
   1.925 +      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
   1.926 +    }
   1.927 +    
   1.928 +    /// \brief Returns a const reference to the node map that stores the
   1.929 +    /// distances of the nodes.
   1.930 +    ///
   1.931 +    /// Returns a const reference to the node map that stores the distances
   1.932 +    /// of the nodes calculated by the algorithm.
   1.933 +    ///
   1.934 +    /// \pre Either \ref run() or \ref init() must be called before
   1.935 +    /// using this function.
   1.936 +    const DistMap &distMap() const { return *_dist;}
   1.937 + 
   1.938 +    /// \brief Returns a const reference to the node map that stores the
   1.939 +    /// predecessor arcs.
   1.940 +    ///
   1.941 +    /// Returns a const reference to the node map that stores the predecessor
   1.942 +    /// arcs, which form the shortest path tree (forest).
   1.943 +    ///
   1.944 +    /// \pre Either \ref run() or \ref init() must be called before
   1.945 +    /// using this function.
   1.946 +    const PredMap &predMap() const { return *_pred; }
   1.947 + 
   1.948 +    /// \brief Checks if a node is reached from the root(s).
   1.949 +    ///
   1.950 +    /// Returns \c true if \c v is reached from the root(s).
   1.951 +    ///
   1.952 +    /// \pre Either \ref run() or \ref init() must be called before
   1.953 +    /// using this function.
   1.954 +    bool reached(Node v) const {
   1.955 +      return (*_dist)[v] != OperationTraits::infinity();
   1.956      }
   1.957  
   1.958 -
   1.959 -    // TODO : implement negative cycle
   1.960 -//     /// \brief Gives back a negative cycle.
   1.961 -//     ///    
   1.962 -//     /// This function gives back a negative cycle.
   1.963 -//     /// If the algorithm have not found yet negative cycle it will give back
   1.964 -//     /// an empty path.
   1.965 -//     Path negativeCycle() {
   1.966 -//       typename Digraph::template NodeMap<int> state(*digraph, 0);
   1.967 -//       for (ActiveIt it(*this); it != INVALID; ++it) {
   1.968 -//         if (state[it] == 0) {
   1.969 -//           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
   1.970 -//             if (state[t] == 0) {
   1.971 -//               state[t] = 1;
   1.972 -//             } else if (state[t] == 2) {
   1.973 -//               break;
   1.974 -//             } else {
   1.975 -//               p.clear();
   1.976 -//               typename Path::Builder b(p);
   1.977 -//               b.setStartNode(t);
   1.978 -//               b.pushFront(predArc(t));
   1.979 -//               for(Node s = predNode(t); s != t; s = predNode(s)) {
   1.980 -//                 b.pushFront(predArc(s));
   1.981 -//               }
   1.982 -//               b.commit();
   1.983 -//               return true;
   1.984 -//             }
   1.985 -//           }
   1.986 -//           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
   1.987 -//             if (state[t] == 1) {
   1.988 -//               state[t] = 2;
   1.989 -//             } else {
   1.990 -//               break;
   1.991 -//             }
   1.992 -//           }
   1.993 -//         }
   1.994 -//       }
   1.995 -//       return false;
   1.996 -//     }
   1.997 -	  
   1.998 -    /// \brief The distance of a node from the root.
   1.999 -    ///
  1.1000 -    /// Returns the distance of a node from the root.
  1.1001 -    /// \pre \ref run() must be called before using this function.
  1.1002 -    /// \warning If node \c v in unreachable from the root the return value
  1.1003 -    /// of this funcion is undefined.
  1.1004 -    Value dist(Node v) const { return (*_dist)[v]; }
  1.1005 -
  1.1006 -    /// \brief Returns the 'previous arc' of the shortest path tree.
  1.1007 -    ///
  1.1008 -    /// For a node \c v it returns the 'previous arc' of the shortest path 
  1.1009 -    /// tree, i.e. it returns the last arc of a shortest path from the root 
  1.1010 -    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or 
  1.1011 -    /// if \c v=s. The shortest path tree used here is equal to the shortest 
  1.1012 -    /// path tree used in \ref predNode(). 
  1.1013 -    /// \pre \ref run() must be called before using
  1.1014 -    /// this function.
  1.1015 -    Arc predArc(Node v) const { return (*_pred)[v]; }
  1.1016 -
  1.1017 -    /// \brief Returns the 'previous node' of the shortest path tree.
  1.1018 -    ///
  1.1019 -    /// For a node \c v it returns the 'previous node' of the shortest path 
  1.1020 -    /// tree, i.e. it returns the last but one node from a shortest path from 
  1.1021 -    /// the root to \c /v. It is INVALID if \c v is unreachable from the root 
  1.1022 -    /// or if \c v=s. The shortest path tree used here is equal to the 
  1.1023 -    /// shortest path tree used in \ref predArc().  \pre \ref run() must be 
  1.1024 -    /// called before using this function.
  1.1025 -    Node predNode(Node v) const { 
  1.1026 -      return (*_pred)[v] == INVALID ? INVALID : digraph->source((*_pred)[v]); 
  1.1027 -    }
  1.1028 -    
  1.1029 -    /// \brief Returns a reference to the NodeMap of distances.
  1.1030 -    ///
  1.1031 -    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
  1.1032 -    /// be called before using this function.
  1.1033 -    const DistMap &distMap() const { return *_dist;}
  1.1034 - 
  1.1035 -    /// \brief Returns a reference to the shortest path tree map.
  1.1036 -    ///
  1.1037 -    /// Returns a reference to the NodeMap of the arcs of the
  1.1038 -    /// shortest path tree.
  1.1039 -    /// \pre \ref run() must be called before using this function.
  1.1040 -    const PredMap &predMap() const { return *_pred; }
  1.1041 - 
  1.1042 -    /// \brief Checks if a node is reachable from the root.
  1.1043 -    ///
  1.1044 -    /// Returns \c true if \c v is reachable from the root.
  1.1045 -    /// \pre \ref run() must be called before using this function.
  1.1046 -    ///
  1.1047 -    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
  1.1048 +    // TODO: implement negative cycle
  1.1049 +//    /// \brief Gives back a negative cycle.
  1.1050 +//    ///    
  1.1051 +//    /// This function gives back a negative cycle.
  1.1052 +//    /// If the algorithm have not found yet negative cycle it will give back
  1.1053 +//    /// an empty path.
  1.1054 +//    Path negativeCycle() {
  1.1055 +//      typename Digraph::template NodeMap<int> state(*digraph, 0);
  1.1056 +//      for (ActiveIt it(*this); it != INVALID; ++it) {
  1.1057 +//        if (state[it] == 0) {
  1.1058 +//          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
  1.1059 +//            if (state[t] == 0) {
  1.1060 +//              state[t] = 1;
  1.1061 +//            } else if (state[t] == 2) {
  1.1062 +//              break;
  1.1063 +//            } else {
  1.1064 +//              p.clear();
  1.1065 +//              typename Path::Builder b(p);
  1.1066 +//              b.setStartNode(t);
  1.1067 +//              b.pushFront(predArc(t));
  1.1068 +//              for(Node s = predNode(t); s != t; s = predNode(s)) {
  1.1069 +//                b.pushFront(predArc(s));
  1.1070 +//              }
  1.1071 +//              b.commit();
  1.1072 +//              return true;
  1.1073 +//            }
  1.1074 +//          }
  1.1075 +//          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
  1.1076 +//            if (state[t] == 1) {
  1.1077 +//              state[t] = 2;
  1.1078 +//            } else {
  1.1079 +//              break;
  1.1080 +//            }
  1.1081 +//          }
  1.1082 +//        }
  1.1083 +//      }
  1.1084 +//      return false;
  1.1085 +//    }
  1.1086      
  1.1087      ///@}
  1.1088    };
  1.1089   
  1.1090 -  /// \brief Default traits class of BellmanFord function.
  1.1091 +  /// \brief Default traits class of bellmanFord() function.
  1.1092    ///
  1.1093 -  /// Default traits class of BellmanFord function.
  1.1094 -  /// \param _Digraph Digraph type.
  1.1095 -  /// \param _LengthMap Type of length map.
  1.1096 -  template <typename _Digraph, typename _LengthMap>
  1.1097 +  /// Default traits class of bellmanFord() function.
  1.1098 +  /// \tparam GR The type of the digraph.
  1.1099 +  /// \tparam LEN The type of the length map.
  1.1100 +  template <typename GR, typename LEN>
  1.1101    struct BellmanFordWizardDefaultTraits {
  1.1102 -    /// \brief The digraph type the algorithm runs on. 
  1.1103 -    typedef _Digraph Digraph;
  1.1104 +    /// The type of the digraph the algorithm runs on. 
  1.1105 +    typedef GR Digraph;
  1.1106  
  1.1107      /// \brief The type of the map that stores the arc lengths.
  1.1108      ///
  1.1109      /// The type of the map that stores the arc lengths.
  1.1110      /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
  1.1111 -    typedef _LengthMap LengthMap;
  1.1112 +    typedef LEN LengthMap;
  1.1113  
  1.1114 -    /// \brief The value type of the length map.
  1.1115 -    typedef typename _LengthMap::Value Value;
  1.1116 +    /// The type of the arc lengths.
  1.1117 +    typedef typename LEN::Value Value;
  1.1118  
  1.1119      /// \brief Operation traits for Bellman-Ford algorithm.
  1.1120      ///
  1.1121 -    /// It defines the infinity type on the given Value type
  1.1122 -    /// and the used operation.
  1.1123 +    /// It defines the used operations and the infinity value for the
  1.1124 +    /// given \c Value type.
  1.1125      /// \see BellmanFordDefaultOperationTraits
  1.1126      typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
  1.1127  
  1.1128      /// \brief The type of the map that stores the last
  1.1129      /// arcs of the shortest paths.
  1.1130      /// 
  1.1131 -    /// The type of the map that stores the last
  1.1132 -    /// arcs of the shortest paths.
  1.1133 -    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1.1134 -    typedef NullMap <typename _Digraph::Node,typename _Digraph::Arc> PredMap;
  1.1135 +    /// The type of the map that stores the last arcs of the shortest paths.
  1.1136 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
  1.1137 +    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
  1.1138  
  1.1139 -    /// \brief Instantiates a PredMap.
  1.1140 +    /// \brief Instantiates a \c PredMap.
  1.1141      /// 
  1.1142 -    /// This function instantiates a \ref PredMap. 
  1.1143 -    static PredMap *createPredMap(const _Digraph &) {
  1.1144 -      return new PredMap();
  1.1145 +    /// This function instantiates a \ref PredMap.
  1.1146 +    /// \param g is the digraph to which we would like to define the
  1.1147 +    /// \ref PredMap.
  1.1148 +    static PredMap *createPredMap(const GR &g) {
  1.1149 +      return new PredMap(g);
  1.1150      }
  1.1151 -    /// \brief The type of the map that stores the dists of the nodes.
  1.1152 +
  1.1153 +    /// \brief The type of the map that stores the distances of the nodes.
  1.1154      ///
  1.1155 -    /// The type of the map that stores the dists of the nodes.
  1.1156 -    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1.1157 -    typedef NullMap<typename Digraph::Node, Value> DistMap;
  1.1158 -    /// \brief Instantiates a DistMap.
  1.1159 +    /// The type of the map that stores the distances of the nodes.
  1.1160 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
  1.1161 +    typedef typename GR::template NodeMap<Value> DistMap;
  1.1162 +
  1.1163 +    /// \brief Instantiates a \c DistMap.
  1.1164      ///
  1.1165      /// This function instantiates a \ref DistMap. 
  1.1166 -    static DistMap *createDistMap(const _Digraph &) {
  1.1167 -      return new DistMap();
  1.1168 +    /// \param g is the digraph to which we would like to define the
  1.1169 +    /// \ref DistMap.
  1.1170 +    static DistMap *createDistMap(const GR &g) {
  1.1171 +      return new DistMap(g);
  1.1172      }
  1.1173 +
  1.1174 +    ///The type of the shortest paths.
  1.1175 +
  1.1176 +    ///The type of the shortest paths.
  1.1177 +    ///It must meet the \ref concepts::Path "Path" concept.
  1.1178 +    typedef lemon::Path<Digraph> Path;
  1.1179    };
  1.1180    
  1.1181 -  /// \brief Default traits used by \ref BellmanFordWizard
  1.1182 +  /// \brief Default traits class used by BellmanFordWizard.
  1.1183    ///
  1.1184 -  /// To make it easier to use BellmanFord algorithm
  1.1185 -  /// we have created a wizard class.
  1.1186 -  /// This \ref BellmanFordWizard class needs default traits,
  1.1187 -  /// as well as the \ref BellmanFord class.
  1.1188 -  /// The \ref BellmanFordWizardBase is a class to be the default traits of the
  1.1189 -  /// \ref BellmanFordWizard class.
  1.1190 -  /// \todo More named parameters are required...
  1.1191 -  template<class _Digraph,class _LengthMap>
  1.1192 +  /// Default traits class used by BellmanFordWizard.
  1.1193 +  /// \tparam GR The type of the digraph.
  1.1194 +  /// \tparam LEN The type of the length map.
  1.1195 +  template <typename GR, typename LEN>
  1.1196    class BellmanFordWizardBase 
  1.1197 -    : public BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> {
  1.1198 +    : public BellmanFordWizardDefaultTraits<GR, LEN> {
  1.1199  
  1.1200 -    typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base;
  1.1201 +    typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
  1.1202    protected:
  1.1203 -    /// Type of the nodes in the digraph.
  1.1204 +    // Type of the nodes in the digraph.
  1.1205      typedef typename Base::Digraph::Node Node;
  1.1206  
  1.1207 -    /// Pointer to the underlying digraph.
  1.1208 +    // Pointer to the underlying digraph.
  1.1209      void *_graph;
  1.1210 -    /// Pointer to the length map
  1.1211 +    // Pointer to the length map
  1.1212      void *_length;
  1.1213 -    ///Pointer to the map of predecessors arcs.
  1.1214 +    // Pointer to the map of predecessors arcs.
  1.1215      void *_pred;
  1.1216 -    ///Pointer to the map of distances.
  1.1217 +    // Pointer to the map of distances.
  1.1218      void *_dist;
  1.1219 -    ///Pointer to the source node.
  1.1220 -    Node _source;
  1.1221 +    //Pointer to the shortest path to the target node.
  1.1222 +    void *_path;
  1.1223 +    //Pointer to the distance of the target node.
  1.1224 +    void *_di;
  1.1225  
  1.1226      public:
  1.1227      /// Constructor.
  1.1228      
  1.1229 -    /// This constructor does not require parameters, therefore it initiates
  1.1230 -    /// all of the attributes to default values (0, INVALID).
  1.1231 -    BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
  1.1232 -			   _dist(0), _source(INVALID) {}
  1.1233 +    /// This constructor does not require parameters, it initiates
  1.1234 +    /// all of the attributes to default values \c 0.
  1.1235 +    BellmanFordWizardBase() :
  1.1236 +      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
  1.1237  
  1.1238      /// Constructor.
  1.1239      
  1.1240 -    /// This constructor requires some parameters,
  1.1241 -    /// listed in the parameters list.
  1.1242 -    /// Others are initiated to 0.
  1.1243 -    /// \param digraph is the initial value of  \ref _graph
  1.1244 -    /// \param length is the initial value of  \ref _length
  1.1245 -    /// \param source is the initial value of  \ref _source
  1.1246 -    BellmanFordWizardBase(const _Digraph& digraph, 
  1.1247 -			  const _LengthMap& length, 
  1.1248 -			  Node source = INVALID) :
  1.1249 -      _graph(reinterpret_cast<void*>(const_cast<_Digraph*>(&digraph))), 
  1.1250 -      _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))), 
  1.1251 -      _pred(0), _dist(0), _source(source) {}
  1.1252 +    /// This constructor requires two parameters,
  1.1253 +    /// others are initiated to \c 0.
  1.1254 +    /// \param gr The digraph the algorithm runs on.
  1.1255 +    /// \param len The length map.
  1.1256 +    BellmanFordWizardBase(const GR& gr, 
  1.1257 +			  const LEN& len) :
  1.1258 +      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
  1.1259 +      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
  1.1260 +      _pred(0), _dist(0), _path(0), _di(0) {}
  1.1261  
  1.1262    };
  1.1263    
  1.1264 -  /// A class to make the usage of BellmanFord algorithm easier
  1.1265 +  /// \brief Auxiliary class for the function-type interface of the
  1.1266 +  /// \ref BellmanFord "Bellman-Ford" algorithm.
  1.1267 +  ///
  1.1268 +  /// This auxiliary class is created to implement the
  1.1269 +  /// \ref bellmanFord() "function-type interface" of the
  1.1270 +  /// \ref BellmanFord "Bellman-Ford" algorithm.
  1.1271 +  /// It does not have own \ref run() method, it uses the
  1.1272 +  /// functions and features of the plain \ref BellmanFord.
  1.1273 +  ///
  1.1274 +  /// This class should only be used through the \ref bellmanFord()
  1.1275 +  /// function, which makes it easier to use the algorithm.
  1.1276 +  template<class TR>
  1.1277 +  class BellmanFordWizard : public TR {
  1.1278 +    typedef TR Base;
  1.1279  
  1.1280 -  /// This class is created to make it easier to use BellmanFord algorithm.
  1.1281 -  /// It uses the functions and features of the plain \ref BellmanFord,
  1.1282 -  /// but it is much simpler to use it.
  1.1283 -  ///
  1.1284 -  /// Simplicity means that the way to change the types defined
  1.1285 -  /// in the traits class is based on functions that returns the new class
  1.1286 -  /// and not on templatable built-in classes.
  1.1287 -  /// When using the plain \ref BellmanFord
  1.1288 -  /// the new class with the modified type comes from
  1.1289 -  /// the original class by using the ::
  1.1290 -  /// operator. In the case of \ref BellmanFordWizard only
  1.1291 -  /// a function have to be called and it will
  1.1292 -  /// return the needed class.
  1.1293 -  ///
  1.1294 -  /// It does not have own \ref run method. When its \ref run method is called
  1.1295 -  /// it initiates a plain \ref BellmanFord class, and calls the \ref 
  1.1296 -  /// BellmanFord::run method of it.
  1.1297 -  template<class _Traits>
  1.1298 -  class BellmanFordWizard : public _Traits {
  1.1299 -    typedef _Traits Base;
  1.1300 -
  1.1301 -    ///The type of the underlying digraph.
  1.1302 -    typedef typename _Traits::Digraph Digraph;
  1.1303 +    typedef typename TR::Digraph Digraph;
  1.1304  
  1.1305      typedef typename Digraph::Node Node;
  1.1306      typedef typename Digraph::NodeIt NodeIt;
  1.1307      typedef typename Digraph::Arc Arc;
  1.1308      typedef typename Digraph::OutArcIt ArcIt;
  1.1309      
  1.1310 -    ///The type of the map that stores the arc lengths.
  1.1311 -    typedef typename _Traits::LengthMap LengthMap;
  1.1312 -
  1.1313 -    ///The type of the length of the arcs.
  1.1314 +    typedef typename TR::LengthMap LengthMap;
  1.1315      typedef typename LengthMap::Value Value;
  1.1316 -
  1.1317 -    ///\brief The type of the map that stores the last
  1.1318 -    ///arcs of the shortest paths.
  1.1319 -    typedef typename _Traits::PredMap PredMap;
  1.1320 -
  1.1321 -    ///The type of the map that stores the dists of the nodes.
  1.1322 -    typedef typename _Traits::DistMap DistMap;
  1.1323 +    typedef typename TR::PredMap PredMap;
  1.1324 +    typedef typename TR::DistMap DistMap;
  1.1325 +    typedef typename TR::Path Path;
  1.1326  
  1.1327    public:
  1.1328      /// Constructor.
  1.1329 -    BellmanFordWizard() : _Traits() {}
  1.1330 +    BellmanFordWizard() : TR() {}
  1.1331  
  1.1332      /// \brief Constructor that requires parameters.
  1.1333      ///
  1.1334      /// Constructor that requires parameters.
  1.1335      /// These parameters will be the default values for the traits class.
  1.1336 -    BellmanFordWizard(const Digraph& digraph, const LengthMap& length, 
  1.1337 -		      Node src = INVALID) 
  1.1338 -      : _Traits(digraph, length, src) {}
  1.1339 +    /// \param gr The digraph the algorithm runs on.
  1.1340 +    /// \param len The length map.
  1.1341 +    BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
  1.1342 +      : TR(gr, len) {}
  1.1343  
  1.1344      /// \brief Copy constructor
  1.1345 -    BellmanFordWizard(const _Traits &b) : _Traits(b) {}
  1.1346 +    BellmanFordWizard(const TR &b) : TR(b) {}
  1.1347  
  1.1348      ~BellmanFordWizard() {}
  1.1349  
  1.1350 -    /// \brief Runs BellmanFord algorithm from a given node.
  1.1351 +    /// \brief Runs the Bellman-Ford algorithm from the given source node.
  1.1352      ///    
  1.1353 -    /// Runs BellmanFord algorithm from a given node.
  1.1354 -    /// The node can be given by the \ref source function.
  1.1355 -    void run() {
  1.1356 -      LEMON_ASSERT(Base::_source != INVALID, "Source node is not given");
  1.1357 -      BellmanFord<Digraph,LengthMap,_Traits> 
  1.1358 +    /// This method runs the Bellman-Ford algorithm from the given source
  1.1359 +    /// node in order to compute the shortest path to each node.
  1.1360 +    void run(Node s) {
  1.1361 +      BellmanFord<Digraph,LengthMap,TR> 
  1.1362  	bf(*reinterpret_cast<const Digraph*>(Base::_graph), 
  1.1363             *reinterpret_cast<const LengthMap*>(Base::_length));
  1.1364        if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1.1365        if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1.1366 -      bf.run(Base::_source);
  1.1367 +      bf.run(s);
  1.1368      }
  1.1369  
  1.1370 -    /// \brief Runs BellmanFord algorithm from the given node.
  1.1371 +    /// \brief Runs the Bellman-Ford algorithm to find the shortest path
  1.1372 +    /// between \c s and \c t.
  1.1373      ///
  1.1374 -    /// Runs BellmanFord algorithm from the given node.
  1.1375 -    /// \param src is the given source.
  1.1376 -    void run(Node src) {
  1.1377 -      Base::_source = src;
  1.1378 -      run();
  1.1379 +    /// This method runs the Bellman-Ford algorithm from node \c s
  1.1380 +    /// in order to compute the shortest path to node \c t.
  1.1381 +    /// Actually, it computes the shortest path to each node, but using
  1.1382 +    /// this function you can retrieve the distance and the shortest path
  1.1383 +    /// for a single target node easier.
  1.1384 +    ///
  1.1385 +    /// \return \c true if \c t is reachable form \c s.
  1.1386 +    bool run(Node s, Node t) {
  1.1387 +      BellmanFord<Digraph,LengthMap,TR>
  1.1388 +        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
  1.1389 +           *reinterpret_cast<const LengthMap*>(Base::_length));
  1.1390 +      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1.1391 +      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1.1392 +      bf.run(s);
  1.1393 +      if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
  1.1394 +      if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
  1.1395 +      return bf.reached(t);
  1.1396      }
  1.1397  
  1.1398      template<class T>
  1.1399 -    struct DefPredMapBase : public Base {
  1.1400 +    struct SetPredMapBase : public Base {
  1.1401        typedef T PredMap;
  1.1402        static PredMap *createPredMap(const Digraph &) { return 0; };
  1.1403 -      DefPredMapBase(const _Traits &b) : _Traits(b) {}
  1.1404 +      SetPredMapBase(const TR &b) : TR(b) {}
  1.1405      };
  1.1406      
  1.1407 -    ///\brief \ref named-templ-param "Named parameter"
  1.1408 -    ///function for setting PredMap type
  1.1409 +    /// \brief \ref named-templ-param "Named parameter" for setting
  1.1410 +    /// the predecessor map.
  1.1411      ///
  1.1412 -    /// \ref named-templ-param "Named parameter"
  1.1413 -    ///function for setting PredMap type
  1.1414 -    ///
  1.1415 +    /// \ref named-templ-param "Named parameter" for setting
  1.1416 +    /// the map that stores the predecessor arcs of the nodes.
  1.1417      template<class T>
  1.1418 -    BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 
  1.1419 -    {
  1.1420 +    BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
  1.1421        Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1422 -      return BellmanFordWizard<DefPredMapBase<T> >(*this);
  1.1423 +      return BellmanFordWizard<SetPredMapBase<T> >(*this);
  1.1424      }
  1.1425      
  1.1426      template<class T>
  1.1427 -    struct DefDistMapBase : public Base {
  1.1428 +    struct SetDistMapBase : public Base {
  1.1429        typedef T DistMap;
  1.1430        static DistMap *createDistMap(const Digraph &) { return 0; };
  1.1431 -      DefDistMapBase(const _Traits &b) : _Traits(b) {}
  1.1432 +      SetDistMapBase(const TR &b) : TR(b) {}
  1.1433      };
  1.1434      
  1.1435 -    ///\brief \ref named-templ-param "Named parameter"
  1.1436 -    ///function for setting DistMap type
  1.1437 +    /// \brief \ref named-templ-param "Named parameter" for setting
  1.1438 +    /// the distance map.
  1.1439      ///
  1.1440 -    /// \ref named-templ-param "Named parameter"
  1.1441 -    ///function for setting DistMap type
  1.1442 -    ///
  1.1443 +    /// \ref named-templ-param "Named parameter" for setting
  1.1444 +    /// the map that stores the distances of the nodes calculated
  1.1445 +    /// by the algorithm.
  1.1446      template<class T>
  1.1447 -    BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
  1.1448 +    BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
  1.1449        Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1450 -      return BellmanFordWizard<DefDistMapBase<T> >(*this);
  1.1451 +      return BellmanFordWizard<SetDistMapBase<T> >(*this);
  1.1452      }
  1.1453  
  1.1454      template<class T>
  1.1455 -    struct DefOperationTraitsBase : public Base {
  1.1456 -      typedef T OperationTraits;
  1.1457 -      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
  1.1458 +    struct SetPathBase : public Base {
  1.1459 +      typedef T Path;
  1.1460 +      SetPathBase(const TR &b) : TR(b) {}
  1.1461      };
  1.1462 -    
  1.1463 -    ///\brief \ref named-templ-param "Named parameter"
  1.1464 -    ///function for setting OperationTraits type
  1.1465 +
  1.1466 +    /// \brief \ref named-func-param "Named parameter" for getting
  1.1467 +    /// the shortest path to the target node.
  1.1468      ///
  1.1469 -    /// \ref named-templ-param "Named parameter"
  1.1470 -    ///function for setting OperationTraits type
  1.1471 +    /// \ref named-func-param "Named parameter" for getting
  1.1472 +    /// the shortest path to the target node.
  1.1473 +    template<class T>
  1.1474 +    BellmanFordWizard<SetPathBase<T> > path(const T &t)
  1.1475 +    {
  1.1476 +      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1477 +      return BellmanFordWizard<SetPathBase<T> >(*this);
  1.1478 +    }
  1.1479 +
  1.1480 +    /// \brief \ref named-func-param "Named parameter" for getting
  1.1481 +    /// the distance of the target node.
  1.1482      ///
  1.1483 -    template<class T>
  1.1484 -    BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
  1.1485 -      return BellmanFordWizard<DefDistMapBase<T> >(*this);
  1.1486 -    }
  1.1487 -    
  1.1488 -    /// \brief Sets the source node, from which the BellmanFord algorithm runs.
  1.1489 -    ///
  1.1490 -    /// Sets the source node, from which the BellmanFord algorithm runs.
  1.1491 -    /// \param src is the source node.
  1.1492 -    BellmanFordWizard<_Traits>& source(Node src) {
  1.1493 -      Base::_source = src;
  1.1494 +    /// \ref named-func-param "Named parameter" for getting
  1.1495 +    /// the distance of the target node.
  1.1496 +    BellmanFordWizard dist(const Value &d)
  1.1497 +    {
  1.1498 +      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
  1.1499        return *this;
  1.1500      }
  1.1501      
  1.1502    };
  1.1503    
  1.1504 -  /// \brief Function type interface for BellmanFord algorithm.
  1.1505 +  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
  1.1506 +  /// algorithm.
  1.1507    ///
  1.1508    /// \ingroup shortest_path
  1.1509 -  /// Function type interface for BellmanFord algorithm.
  1.1510 +  /// Function type interface for the \ref BellmanFord "Bellman-Ford"
  1.1511 +  /// algorithm.
  1.1512    ///
  1.1513    /// This function also has several \ref named-templ-func-param 
  1.1514    /// "named parameters", they are declared as the members of class 
  1.1515    /// \ref BellmanFordWizard.
  1.1516 -  /// The following
  1.1517 -  /// example shows how to use these parameters.
  1.1518 -  ///\code
  1.1519 -  /// bellmanford(g,length,source).predMap(preds).run();
  1.1520 -  ///\endcode
  1.1521 +  /// The following examples show how to use these parameters.
  1.1522 +  /// \code
  1.1523 +  ///   // Compute shortest path from node s to each node
  1.1524 +  ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
  1.1525 +  ///
  1.1526 +  ///   // Compute shortest path from s to t
  1.1527 +  ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
  1.1528 +  /// \endcode
  1.1529    /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
  1.1530    /// to the end of the parameter list.
  1.1531    /// \sa BellmanFordWizard
  1.1532    /// \sa BellmanFord
  1.1533 -  template<class _Digraph, class _LengthMap>
  1.1534 -  BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
  1.1535 -  bellmanFord(const _Digraph& digraph,
  1.1536 -	      const _LengthMap& length, 
  1.1537 -	      typename _Digraph::Node source = INVALID) {
  1.1538 -    return BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
  1.1539 -      (digraph, length, source);
  1.1540 +  template<typename GR, typename LEN>
  1.1541 +  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
  1.1542 +  bellmanFord(const GR& digraph,
  1.1543 +	      const LEN& length)
  1.1544 +  {
  1.1545 +    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
  1.1546    }
  1.1547  
  1.1548  } //END OF NAMESPACE LEMON