author Peter Kovacs Sun, 02 Aug 2009 13:24:46 +0200 changeset 697 9496ed797f20 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
- Simplify template parameter names.
- Many unifications and improvements in the doc.
 lemon/bellman_ford.h file | annotate | diff | comparison | revisions
     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.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.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.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.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.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.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.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.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.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.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.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.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.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.758 +    ///   bf.start();
1.759 +    /// \endcode
1.760      void run(Node s) {
1.761        init();
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.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.800 +    ///   bf.limitedStart(num);
1.801 +    /// \endcode
1.802      void run(Node s, int num) {
1.803        init();
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.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