Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Mon, 31 Aug 2009 08:32:25 +0200
changeset 7006f7c1052d260
parent 695 8dae88c5943e
parent 699 75325dfccf38
child 708 5d313b76f323
Merge
lemon/Makefile.am
     1.1 --- a/lemon/Makefile.am	Mon Aug 31 08:25:33 2009 +0200
     1.2 +++ b/lemon/Makefile.am	Mon Aug 31 08:32:25 2009 +0200
     1.3 @@ -57,6 +57,7 @@
     1.4  	lemon/adaptors.h \
     1.5  	lemon/arg_parser.h \
     1.6  	lemon/assert.h \
     1.7 +	lemon/bellman_ford.h \
     1.8  	lemon/bfs.h \
     1.9  	lemon/bin_heap.h \
    1.10  	lemon/bucket_heap.h \
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/lemon/bellman_ford.h	Mon Aug 31 08:32:25 2009 +0200
     2.3 @@ -0,0 +1,1100 @@
     2.4 +/* -*- C++ -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library
     2.7 + *
     2.8 + * Copyright (C) 2003-2008
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22 +#ifndef LEMON_BELLMAN_FORD_H
    2.23 +#define LEMON_BELLMAN_FORD_H
    2.24 +
    2.25 +/// \ingroup shortest_path
    2.26 +/// \file
    2.27 +/// \brief Bellman-Ford algorithm.
    2.28 +
    2.29 +#include <lemon/bits/path_dump.h>
    2.30 +#include <lemon/core.h>
    2.31 +#include <lemon/error.h>
    2.32 +#include <lemon/maps.h>
    2.33 +#include <lemon/path.h>
    2.34 +
    2.35 +#include <limits>
    2.36 +
    2.37 +namespace lemon {
    2.38 +
    2.39 +  /// \brief Default OperationTraits for the BellmanFord algorithm class.
    2.40 +  ///  
    2.41 +  /// This operation traits class defines all computational operations
    2.42 +  /// and constants that are used in the Bellman-Ford algorithm.
    2.43 +  /// The default implementation is based on the \c numeric_limits class.
    2.44 +  /// If the numeric type does not have infinity value, then the maximum
    2.45 +  /// value is used as extremal infinity value.
    2.46 +  template <
    2.47 +    typename V, 
    2.48 +    bool has_inf = std::numeric_limits<V>::has_infinity>
    2.49 +  struct BellmanFordDefaultOperationTraits {
    2.50 +    /// \e
    2.51 +    typedef V Value;
    2.52 +    /// \brief Gives back the zero value of the type.
    2.53 +    static Value zero() {
    2.54 +      return static_cast<Value>(0);
    2.55 +    }
    2.56 +    /// \brief Gives back the positive infinity value of the type.
    2.57 +    static Value infinity() {
    2.58 +      return std::numeric_limits<Value>::infinity();
    2.59 +    }
    2.60 +    /// \brief Gives back the sum of the given two elements.
    2.61 +    static Value plus(const Value& left, const Value& right) {
    2.62 +      return left + right;
    2.63 +    }
    2.64 +    /// \brief Gives back \c true only if the first value is less than
    2.65 +    /// the second.
    2.66 +    static bool less(const Value& left, const Value& right) {
    2.67 +      return left < right;
    2.68 +    }
    2.69 +  };
    2.70 +
    2.71 +  template <typename V>
    2.72 +  struct BellmanFordDefaultOperationTraits<V, false> {
    2.73 +    typedef V Value;
    2.74 +    static Value zero() {
    2.75 +      return static_cast<Value>(0);
    2.76 +    }
    2.77 +    static Value infinity() {
    2.78 +      return std::numeric_limits<Value>::max();
    2.79 +    }
    2.80 +    static Value plus(const Value& left, const Value& right) {
    2.81 +      if (left == infinity() || right == infinity()) return infinity();
    2.82 +      return left + right;
    2.83 +    }
    2.84 +    static bool less(const Value& left, const Value& right) {
    2.85 +      return left < right;
    2.86 +    }
    2.87 +  };
    2.88 +  
    2.89 +  /// \brief Default traits class of BellmanFord class.
    2.90 +  ///
    2.91 +  /// Default traits class of BellmanFord class.
    2.92 +  /// \param GR The type of the digraph.
    2.93 +  /// \param LEN The type of the length map.
    2.94 +  template<typename GR, typename LEN>
    2.95 +  struct BellmanFordDefaultTraits {
    2.96 +    /// The type of the digraph the algorithm runs on. 
    2.97 +    typedef GR Digraph;
    2.98 +
    2.99 +    /// \brief The type of the map that stores the arc lengths.
   2.100 +    ///
   2.101 +    /// The type of the map that stores the arc lengths.
   2.102 +    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
   2.103 +    typedef LEN LengthMap;
   2.104 +
   2.105 +    /// The type of the arc lengths.
   2.106 +    typedef typename LEN::Value Value;
   2.107 +
   2.108 +    /// \brief Operation traits for Bellman-Ford algorithm.
   2.109 +    ///
   2.110 +    /// It defines the used operations and the infinity value for the
   2.111 +    /// given \c Value type.
   2.112 +    /// \see BellmanFordDefaultOperationTraits
   2.113 +    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   2.114 + 
   2.115 +    /// \brief The type of the map that stores the last arcs of the 
   2.116 +    /// shortest paths.
   2.117 +    /// 
   2.118 +    /// The type of the map that stores the last
   2.119 +    /// arcs of the shortest paths.
   2.120 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.121 +    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   2.122 +
   2.123 +    /// \brief Instantiates a \c PredMap.
   2.124 +    /// 
   2.125 +    /// This function instantiates a \ref PredMap. 
   2.126 +    /// \param g is the digraph to which we would like to define the
   2.127 +    /// \ref PredMap.
   2.128 +    static PredMap *createPredMap(const GR& g) {
   2.129 +      return new PredMap(g);
   2.130 +    }
   2.131 +
   2.132 +    /// \brief The type of the map that stores the distances of the nodes.
   2.133 +    ///
   2.134 +    /// The type of the map that stores the distances of the nodes.
   2.135 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.136 +    typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
   2.137 +
   2.138 +    /// \brief Instantiates a \c DistMap.
   2.139 +    ///
   2.140 +    /// This function instantiates a \ref DistMap. 
   2.141 +    /// \param g is the digraph to which we would like to define the 
   2.142 +    /// \ref DistMap.
   2.143 +    static DistMap *createDistMap(const GR& g) {
   2.144 +      return new DistMap(g);
   2.145 +    }
   2.146 +
   2.147 +  };
   2.148 +  
   2.149 +  /// \brief %BellmanFord algorithm class.
   2.150 +  ///
   2.151 +  /// \ingroup shortest_path
   2.152 +  /// This class provides an efficient implementation of the Bellman-Ford 
   2.153 +  /// algorithm. The maximum time complexity of the algorithm is
   2.154 +  /// <tt>O(ne)</tt>.
   2.155 +  ///
   2.156 +  /// The Bellman-Ford algorithm solves the single-source shortest path
   2.157 +  /// problem when the arcs can have negative lengths, but the digraph
   2.158 +  /// should not contain directed cycles with negative total length.
   2.159 +  /// If all arc costs are non-negative, consider to use the Dijkstra
   2.160 +  /// algorithm instead, since it is more efficient.
   2.161 +  ///
   2.162 +  /// The arc lengths are passed to the algorithm using a
   2.163 +  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
   2.164 +  /// kind of length. The type of the length values is determined by the
   2.165 +  /// \ref concepts::ReadMap::Value "Value" type of the length map.
   2.166 +  ///
   2.167 +  /// There is also a \ref bellmanFord() "function-type interface" for the
   2.168 +  /// Bellman-Ford algorithm, which is convenient in the simplier cases and
   2.169 +  /// it can be used easier.
   2.170 +  ///
   2.171 +  /// \tparam GR The type of the digraph the algorithm runs on.
   2.172 +  /// The default type is \ref ListDigraph.
   2.173 +  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
   2.174 +  /// the lengths of the arcs. The default map type is
   2.175 +  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   2.176 +#ifdef DOXYGEN
   2.177 +  template <typename GR, typename LEN, typename TR>
   2.178 +#else
   2.179 +  template <typename GR=ListDigraph,
   2.180 +            typename LEN=typename GR::template ArcMap<int>,
   2.181 +            typename TR=BellmanFordDefaultTraits<GR,LEN> >
   2.182 +#endif
   2.183 +  class BellmanFord {
   2.184 +  public:
   2.185 +
   2.186 +    ///The type of the underlying digraph.
   2.187 +    typedef typename TR::Digraph Digraph;
   2.188 +    
   2.189 +    /// \brief The type of the arc lengths.
   2.190 +    typedef typename TR::LengthMap::Value Value;
   2.191 +    /// \brief The type of the map that stores the arc lengths.
   2.192 +    typedef typename TR::LengthMap LengthMap;
   2.193 +    /// \brief The type of the map that stores the last
   2.194 +    /// arcs of the shortest paths.
   2.195 +    typedef typename TR::PredMap PredMap;
   2.196 +    /// \brief The type of the map that stores the distances of the nodes.
   2.197 +    typedef typename TR::DistMap DistMap;
   2.198 +    /// The type of the paths.
   2.199 +    typedef PredMapPath<Digraph, PredMap> Path;
   2.200 +    ///\brief The \ref BellmanFordDefaultOperationTraits
   2.201 +    /// "operation traits class" of the algorithm.
   2.202 +    typedef typename TR::OperationTraits OperationTraits;
   2.203 +
   2.204 +    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
   2.205 +    typedef TR Traits;
   2.206 +
   2.207 +  private:
   2.208 +
   2.209 +    typedef typename Digraph::Node Node;
   2.210 +    typedef typename Digraph::NodeIt NodeIt;
   2.211 +    typedef typename Digraph::Arc Arc;
   2.212 +    typedef typename Digraph::OutArcIt OutArcIt;
   2.213 +
   2.214 +    // Pointer to the underlying digraph.
   2.215 +    const Digraph *_gr;
   2.216 +    // Pointer to the length map
   2.217 +    const LengthMap *_length;
   2.218 +    // Pointer to the map of predecessors arcs.
   2.219 +    PredMap *_pred;
   2.220 +    // Indicates if _pred is locally allocated (true) or not.
   2.221 +    bool _local_pred;
   2.222 +    // Pointer to the map of distances.
   2.223 +    DistMap *_dist;
   2.224 +    // Indicates if _dist is locally allocated (true) or not.
   2.225 +    bool _local_dist;
   2.226 +
   2.227 +    typedef typename Digraph::template NodeMap<bool> MaskMap;
   2.228 +    MaskMap *_mask;
   2.229 +
   2.230 +    std::vector<Node> _process;
   2.231 +
   2.232 +    // Creates the maps if necessary.
   2.233 +    void create_maps() {
   2.234 +      if(!_pred) {
   2.235 +	_local_pred = true;
   2.236 +	_pred = Traits::createPredMap(*_gr);
   2.237 +      }
   2.238 +      if(!_dist) {
   2.239 +	_local_dist = true;
   2.240 +	_dist = Traits::createDistMap(*_gr);
   2.241 +      }
   2.242 +      _mask = new MaskMap(*_gr, false);
   2.243 +    }
   2.244 +    
   2.245 +  public :
   2.246 + 
   2.247 +    typedef BellmanFord Create;
   2.248 +
   2.249 +    /// \name Named Template Parameters
   2.250 +
   2.251 +    ///@{
   2.252 +
   2.253 +    template <class T>
   2.254 +    struct SetPredMapTraits : public Traits {
   2.255 +      typedef T PredMap;
   2.256 +      static PredMap *createPredMap(const Digraph&) {
   2.257 +        LEMON_ASSERT(false, "PredMap is not initialized");
   2.258 +        return 0; // ignore warnings
   2.259 +      }
   2.260 +    };
   2.261 +
   2.262 +    /// \brief \ref named-templ-param "Named parameter" for setting
   2.263 +    /// \c PredMap type.
   2.264 +    ///
   2.265 +    /// \ref named-templ-param "Named parameter" for setting
   2.266 +    /// \c PredMap type.
   2.267 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.268 +    template <class T>
   2.269 +    struct SetPredMap 
   2.270 +      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
   2.271 +      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   2.272 +    };
   2.273 +    
   2.274 +    template <class T>
   2.275 +    struct SetDistMapTraits : public Traits {
   2.276 +      typedef T DistMap;
   2.277 +      static DistMap *createDistMap(const Digraph&) {
   2.278 +        LEMON_ASSERT(false, "DistMap is not initialized");
   2.279 +        return 0; // ignore warnings
   2.280 +      }
   2.281 +    };
   2.282 +
   2.283 +    /// \brief \ref named-templ-param "Named parameter" for setting
   2.284 +    /// \c DistMap type.
   2.285 +    ///
   2.286 +    /// \ref named-templ-param "Named parameter" for setting
   2.287 +    /// \c DistMap type.
   2.288 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.289 +    template <class T>
   2.290 +    struct SetDistMap 
   2.291 +      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
   2.292 +      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   2.293 +    };
   2.294 +
   2.295 +    template <class T>
   2.296 +    struct SetOperationTraitsTraits : public Traits {
   2.297 +      typedef T OperationTraits;
   2.298 +    };
   2.299 +    
   2.300 +    /// \brief \ref named-templ-param "Named parameter" for setting 
   2.301 +    /// \c OperationTraits type.
   2.302 +    ///
   2.303 +    /// \ref named-templ-param "Named parameter" for setting
   2.304 +    /// \c OperationTraits type.
   2.305 +    /// For more information see \ref BellmanFordDefaultOperationTraits.
   2.306 +    template <class T>
   2.307 +    struct SetOperationTraits
   2.308 +      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   2.309 +      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
   2.310 +      Create;
   2.311 +    };
   2.312 +    
   2.313 +    ///@}
   2.314 +
   2.315 +  protected:
   2.316 +    
   2.317 +    BellmanFord() {}
   2.318 +
   2.319 +  public:      
   2.320 +    
   2.321 +    /// \brief Constructor.
   2.322 +    ///
   2.323 +    /// Constructor.
   2.324 +    /// \param g The digraph the algorithm runs on.
   2.325 +    /// \param length The length map used by the algorithm.
   2.326 +    BellmanFord(const Digraph& g, const LengthMap& length) :
   2.327 +      _gr(&g), _length(&length),
   2.328 +      _pred(0), _local_pred(false),
   2.329 +      _dist(0), _local_dist(false), _mask(0) {}
   2.330 +    
   2.331 +    ///Destructor.
   2.332 +    ~BellmanFord() {
   2.333 +      if(_local_pred) delete _pred;
   2.334 +      if(_local_dist) delete _dist;
   2.335 +      if(_mask) delete _mask;
   2.336 +    }
   2.337 +
   2.338 +    /// \brief Sets the length map.
   2.339 +    ///
   2.340 +    /// Sets the length map.
   2.341 +    /// \return <tt>(*this)</tt>
   2.342 +    BellmanFord &lengthMap(const LengthMap &map) {
   2.343 +      _length = &map;
   2.344 +      return *this;
   2.345 +    }
   2.346 +
   2.347 +    /// \brief Sets the map that stores the predecessor arcs.
   2.348 +    ///
   2.349 +    /// Sets the map that stores the predecessor arcs.
   2.350 +    /// If you don't use this function before calling \ref run()
   2.351 +    /// or \ref init(), an instance will be allocated automatically.
   2.352 +    /// The destructor deallocates this automatically allocated map,
   2.353 +    /// of course.
   2.354 +    /// \return <tt>(*this)</tt>
   2.355 +    BellmanFord &predMap(PredMap &map) {
   2.356 +      if(_local_pred) {
   2.357 +	delete _pred;
   2.358 +	_local_pred=false;
   2.359 +      }
   2.360 +      _pred = &map;
   2.361 +      return *this;
   2.362 +    }
   2.363 +
   2.364 +    /// \brief Sets the map that stores the distances of the nodes.
   2.365 +    ///
   2.366 +    /// Sets the map that stores the distances of the nodes calculated
   2.367 +    /// by the algorithm.
   2.368 +    /// If you don't use this function before calling \ref run()
   2.369 +    /// or \ref init(), an instance will be allocated automatically.
   2.370 +    /// The destructor deallocates this automatically allocated map,
   2.371 +    /// of course.
   2.372 +    /// \return <tt>(*this)</tt>
   2.373 +    BellmanFord &distMap(DistMap &map) {
   2.374 +      if(_local_dist) {
   2.375 +	delete _dist;
   2.376 +	_local_dist=false;
   2.377 +      }
   2.378 +      _dist = &map;
   2.379 +      return *this;
   2.380 +    }
   2.381 +
   2.382 +    /// \name Execution Control
   2.383 +    /// The simplest way to execute the Bellman-Ford algorithm is to use
   2.384 +    /// one of the member functions called \ref run().\n
   2.385 +    /// If you need better control on the execution, you have to call
   2.386 +    /// \ref init() first, then you can add several source nodes
   2.387 +    /// with \ref addSource(). Finally the actual path computation can be
   2.388 +    /// performed with \ref start(), \ref checkedStart() or
   2.389 +    /// \ref limitedStart().
   2.390 +
   2.391 +    ///@{
   2.392 +
   2.393 +    /// \brief Initializes the internal data structures.
   2.394 +    /// 
   2.395 +    /// Initializes the internal data structures. The optional parameter
   2.396 +    /// is the initial distance of each node.
   2.397 +    void init(const Value value = OperationTraits::infinity()) {
   2.398 +      create_maps();
   2.399 +      for (NodeIt it(*_gr); it != INVALID; ++it) {
   2.400 +	_pred->set(it, INVALID);
   2.401 +	_dist->set(it, value);
   2.402 +      }
   2.403 +      _process.clear();
   2.404 +      if (OperationTraits::less(value, OperationTraits::infinity())) {
   2.405 +	for (NodeIt it(*_gr); it != INVALID; ++it) {
   2.406 +	  _process.push_back(it);
   2.407 +	  _mask->set(it, true);
   2.408 +	}
   2.409 +      }
   2.410 +    }
   2.411 +    
   2.412 +    /// \brief Adds a new source node.
   2.413 +    ///
   2.414 +    /// This function adds a new source node. The optional second parameter
   2.415 +    /// is the initial distance of the node.
   2.416 +    void addSource(Node source, Value dst = OperationTraits::zero()) {
   2.417 +      _dist->set(source, dst);
   2.418 +      if (!(*_mask)[source]) {
   2.419 +	_process.push_back(source);
   2.420 +	_mask->set(source, true);
   2.421 +      }
   2.422 +    }
   2.423 +
   2.424 +    /// \brief Executes one round from the Bellman-Ford algorithm.
   2.425 +    ///
   2.426 +    /// If the algoritm calculated the distances in the previous round
   2.427 +    /// exactly for the paths of at most \c k arcs, then this function
   2.428 +    /// will calculate the distances exactly for the paths of at most
   2.429 +    /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
   2.430 +    /// calculates the shortest path distances exactly for the paths
   2.431 +    /// consisting of at most \c k arcs.
   2.432 +    ///
   2.433 +    /// \warning The paths with limited arc number cannot be retrieved
   2.434 +    /// easily with \ref path() or \ref predArc() functions. If you also
   2.435 +    /// need the shortest paths and not only the distances, you should
   2.436 +    /// store the \ref predMap() "predecessor map" after each iteration
   2.437 +    /// and build the path manually.
   2.438 +    ///
   2.439 +    /// \return \c true when the algorithm have not found more shorter
   2.440 +    /// paths.
   2.441 +    ///
   2.442 +    /// \see ActiveIt
   2.443 +    bool processNextRound() {
   2.444 +      for (int i = 0; i < int(_process.size()); ++i) {
   2.445 +	_mask->set(_process[i], false);
   2.446 +      }
   2.447 +      std::vector<Node> nextProcess;
   2.448 +      std::vector<Value> values(_process.size());
   2.449 +      for (int i = 0; i < int(_process.size()); ++i) {
   2.450 +	values[i] = (*_dist)[_process[i]];
   2.451 +      }
   2.452 +      for (int i = 0; i < int(_process.size()); ++i) {
   2.453 +	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   2.454 +	  Node target = _gr->target(it);
   2.455 +	  Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
   2.456 +	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
   2.457 +	    _pred->set(target, it);
   2.458 +	    _dist->set(target, relaxed);
   2.459 +	    if (!(*_mask)[target]) {
   2.460 +	      _mask->set(target, true);
   2.461 +	      nextProcess.push_back(target);
   2.462 +	    }
   2.463 +	  }	  
   2.464 +	}
   2.465 +      }
   2.466 +      _process.swap(nextProcess);
   2.467 +      return _process.empty();
   2.468 +    }
   2.469 +
   2.470 +    /// \brief Executes one weak round from the Bellman-Ford algorithm.
   2.471 +    ///
   2.472 +    /// If the algorithm calculated the distances in the previous round
   2.473 +    /// at least for the paths of at most \c k arcs, then this function
   2.474 +    /// will calculate the distances at least for the paths of at most
   2.475 +    /// <tt>k+1</tt> arcs.
   2.476 +    /// This function does not make it possible to calculate the shortest
   2.477 +    /// path distances exactly for paths consisting of at most \c k arcs,
   2.478 +    /// this is why it is called weak round.
   2.479 +    ///
   2.480 +    /// \return \c true when the algorithm have not found more shorter
   2.481 +    /// paths.
   2.482 +    ///
   2.483 +    /// \see ActiveIt
   2.484 +    bool processNextWeakRound() {
   2.485 +      for (int i = 0; i < int(_process.size()); ++i) {
   2.486 +	_mask->set(_process[i], false);
   2.487 +      }
   2.488 +      std::vector<Node> nextProcess;
   2.489 +      for (int i = 0; i < int(_process.size()); ++i) {
   2.490 +	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   2.491 +	  Node target = _gr->target(it);
   2.492 +	  Value relaxed = 
   2.493 +	    OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
   2.494 +	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
   2.495 +	    _pred->set(target, it);
   2.496 +	    _dist->set(target, relaxed);
   2.497 +	    if (!(*_mask)[target]) {
   2.498 +	      _mask->set(target, true);
   2.499 +	      nextProcess.push_back(target);
   2.500 +	    }
   2.501 +	  }	  
   2.502 +	}
   2.503 +      }
   2.504 +      _process.swap(nextProcess);
   2.505 +      return _process.empty();
   2.506 +    }
   2.507 +
   2.508 +    /// \brief Executes the algorithm.
   2.509 +    ///
   2.510 +    /// Executes the algorithm.
   2.511 +    ///
   2.512 +    /// This method runs the Bellman-Ford algorithm from the root node(s)
   2.513 +    /// in order to compute the shortest path to each node.
   2.514 +    ///
   2.515 +    /// The algorithm computes
   2.516 +    /// - the shortest path tree (forest),
   2.517 +    /// - the distance of each node from the root(s).
   2.518 +    ///
   2.519 +    /// \pre init() must be called and at least one root node should be
   2.520 +    /// added with addSource() before using this function.
   2.521 +    void start() {
   2.522 +      int num = countNodes(*_gr) - 1;
   2.523 +      for (int i = 0; i < num; ++i) {
   2.524 +	if (processNextWeakRound()) break;
   2.525 +      }
   2.526 +    }
   2.527 +
   2.528 +    /// \brief Executes the algorithm and checks the negative cycles.
   2.529 +    ///
   2.530 +    /// Executes the algorithm and checks the negative cycles.
   2.531 +    ///
   2.532 +    /// This method runs the Bellman-Ford algorithm from the root node(s)
   2.533 +    /// in order to compute the shortest path to each node and also checks
   2.534 +    /// if the digraph contains cycles with negative total length.
   2.535 +    ///
   2.536 +    /// The algorithm computes 
   2.537 +    /// - the shortest path tree (forest),
   2.538 +    /// - the distance of each node from the root(s).
   2.539 +    /// 
   2.540 +    /// \return \c false if there is a negative cycle in the digraph.
   2.541 +    ///
   2.542 +    /// \pre init() must be called and at least one root node should be
   2.543 +    /// added with addSource() before using this function. 
   2.544 +    bool checkedStart() {
   2.545 +      int num = countNodes(*_gr);
   2.546 +      for (int i = 0; i < num; ++i) {
   2.547 +	if (processNextWeakRound()) return true;
   2.548 +      }
   2.549 +      return _process.empty();
   2.550 +    }
   2.551 +
   2.552 +    /// \brief Executes the algorithm with arc number limit.
   2.553 +    ///
   2.554 +    /// Executes the algorithm with arc number limit.
   2.555 +    ///
   2.556 +    /// This method runs the Bellman-Ford algorithm from the root node(s)
   2.557 +    /// in order to compute the shortest path distance for each node
   2.558 +    /// using only the paths consisting of at most \c num arcs.
   2.559 +    ///
   2.560 +    /// The algorithm computes
   2.561 +    /// - the limited distance of each node from the root(s),
   2.562 +    /// - the predecessor arc for each node.
   2.563 +    ///
   2.564 +    /// \warning The paths with limited arc number cannot be retrieved
   2.565 +    /// easily with \ref path() or \ref predArc() functions. If you also
   2.566 +    /// need the shortest paths and not only the distances, you should
   2.567 +    /// store the \ref predMap() "predecessor map" after each iteration
   2.568 +    /// and build the path manually.
   2.569 +    ///
   2.570 +    /// \pre init() must be called and at least one root node should be
   2.571 +    /// added with addSource() before using this function. 
   2.572 +    void limitedStart(int num) {
   2.573 +      for (int i = 0; i < num; ++i) {
   2.574 +	if (processNextRound()) break;
   2.575 +      }
   2.576 +    }
   2.577 +    
   2.578 +    /// \brief Runs the algorithm from the given root node.
   2.579 +    ///    
   2.580 +    /// This method runs the Bellman-Ford algorithm from the given root
   2.581 +    /// node \c s in order to compute the shortest path to each node.
   2.582 +    ///
   2.583 +    /// The algorithm computes
   2.584 +    /// - the shortest path tree (forest),
   2.585 +    /// - the distance of each node from the root(s).
   2.586 +    ///
   2.587 +    /// \note bf.run(s) is just a shortcut of the following code.
   2.588 +    /// \code
   2.589 +    ///   bf.init();
   2.590 +    ///   bf.addSource(s);
   2.591 +    ///   bf.start();
   2.592 +    /// \endcode
   2.593 +    void run(Node s) {
   2.594 +      init();
   2.595 +      addSource(s);
   2.596 +      start();
   2.597 +    }
   2.598 +    
   2.599 +    /// \brief Runs the algorithm from the given root node with arc
   2.600 +    /// number limit.
   2.601 +    ///    
   2.602 +    /// This method runs the Bellman-Ford algorithm from the given root
   2.603 +    /// node \c s in order to compute the shortest path distance for each
   2.604 +    /// node using only the paths consisting of at most \c num arcs.
   2.605 +    ///
   2.606 +    /// The algorithm computes
   2.607 +    /// - the limited distance of each node from the root(s),
   2.608 +    /// - the predecessor arc for each node.
   2.609 +    ///
   2.610 +    /// \warning The paths with limited arc number cannot be retrieved
   2.611 +    /// easily with \ref path() or \ref predArc() functions. If you also
   2.612 +    /// need the shortest paths and not only the distances, you should
   2.613 +    /// store the \ref predMap() "predecessor map" after each iteration
   2.614 +    /// and build the path manually.
   2.615 +    ///
   2.616 +    /// \note bf.run(s, num) is just a shortcut of the following code.
   2.617 +    /// \code
   2.618 +    ///   bf.init();
   2.619 +    ///   bf.addSource(s);
   2.620 +    ///   bf.limitedStart(num);
   2.621 +    /// \endcode
   2.622 +    void run(Node s, int num) {
   2.623 +      init();
   2.624 +      addSource(s);
   2.625 +      limitedStart(num);
   2.626 +    }
   2.627 +    
   2.628 +    ///@}
   2.629 +
   2.630 +    /// \brief LEMON iterator for getting the active nodes.
   2.631 +    ///
   2.632 +    /// This class provides a common style LEMON iterator that traverses
   2.633 +    /// the active nodes of the Bellman-Ford algorithm after the last
   2.634 +    /// phase. These nodes should be checked in the next phase to
   2.635 +    /// find augmenting arcs outgoing from them.
   2.636 +    class ActiveIt {
   2.637 +    public:
   2.638 +
   2.639 +      /// \brief Constructor.
   2.640 +      ///
   2.641 +      /// Constructor for getting the active nodes of the given BellmanFord
   2.642 +      /// instance. 
   2.643 +      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
   2.644 +      {
   2.645 +        _index = _algorithm->_process.size() - 1;
   2.646 +      }
   2.647 +
   2.648 +      /// \brief Invalid constructor.
   2.649 +      ///
   2.650 +      /// Invalid constructor.
   2.651 +      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
   2.652 +
   2.653 +      /// \brief Conversion to \c Node.
   2.654 +      ///
   2.655 +      /// Conversion to \c Node.
   2.656 +      operator Node() const { 
   2.657 +        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
   2.658 +      }
   2.659 +
   2.660 +      /// \brief Increment operator.
   2.661 +      ///
   2.662 +      /// Increment operator.
   2.663 +      ActiveIt& operator++() {
   2.664 +        --_index;
   2.665 +        return *this; 
   2.666 +      }
   2.667 +
   2.668 +      bool operator==(const ActiveIt& it) const { 
   2.669 +        return static_cast<Node>(*this) == static_cast<Node>(it); 
   2.670 +      }
   2.671 +      bool operator!=(const ActiveIt& it) const { 
   2.672 +        return static_cast<Node>(*this) != static_cast<Node>(it); 
   2.673 +      }
   2.674 +      bool operator<(const ActiveIt& it) const { 
   2.675 +        return static_cast<Node>(*this) < static_cast<Node>(it); 
   2.676 +      }
   2.677 +      
   2.678 +    private:
   2.679 +      const BellmanFord* _algorithm;
   2.680 +      int _index;
   2.681 +    };
   2.682 +    
   2.683 +    /// \name Query Functions
   2.684 +    /// The result of the Bellman-Ford algorithm can be obtained using these
   2.685 +    /// functions.\n
   2.686 +    /// Either \ref run() or \ref init() should be called before using them.
   2.687 +    
   2.688 +    ///@{
   2.689 +
   2.690 +    /// \brief The shortest path to the given node.
   2.691 +    ///    
   2.692 +    /// Gives back the shortest path to the given node from the root(s).
   2.693 +    ///
   2.694 +    /// \warning \c t should be reached from the root(s).
   2.695 +    ///
   2.696 +    /// \pre Either \ref run() or \ref init() must be called before
   2.697 +    /// using this function.
   2.698 +    Path path(Node t) const
   2.699 +    {
   2.700 +      return Path(*_gr, *_pred, t);
   2.701 +    }
   2.702 +	  
   2.703 +    /// \brief The distance of the given node from the root(s).
   2.704 +    ///
   2.705 +    /// Returns the distance of the given node from the root(s).
   2.706 +    ///
   2.707 +    /// \warning If node \c v is not reached from the root(s), then
   2.708 +    /// the return value of this function is undefined.
   2.709 +    ///
   2.710 +    /// \pre Either \ref run() or \ref init() must be called before
   2.711 +    /// using this function.
   2.712 +    Value dist(Node v) const { return (*_dist)[v]; }
   2.713 +
   2.714 +    /// \brief Returns the 'previous arc' of the shortest path tree for
   2.715 +    /// the given node.
   2.716 +    ///
   2.717 +    /// This function returns the 'previous arc' of the shortest path
   2.718 +    /// tree for node \c v, i.e. it returns the last arc of a
   2.719 +    /// shortest path from a root to \c v. It is \c INVALID if \c v
   2.720 +    /// is not reached from the root(s) or if \c v is a root.
   2.721 +    ///
   2.722 +    /// The shortest path tree used here is equal to the shortest path
   2.723 +    /// tree used in \ref predNode() and \predMap().
   2.724 +    ///
   2.725 +    /// \pre Either \ref run() or \ref init() must be called before
   2.726 +    /// using this function.
   2.727 +    Arc predArc(Node v) const { return (*_pred)[v]; }
   2.728 +
   2.729 +    /// \brief Returns the 'previous node' of the shortest path tree for
   2.730 +    /// the given node.
   2.731 +    ///
   2.732 +    /// This function returns the 'previous node' of the shortest path
   2.733 +    /// tree for node \c v, i.e. it returns the last but one node of
   2.734 +    /// a shortest path from a root to \c v. It is \c INVALID if \c v
   2.735 +    /// is not reached from the root(s) or if \c v is a root.
   2.736 +    ///
   2.737 +    /// The shortest path tree used here is equal to the shortest path
   2.738 +    /// tree used in \ref predArc() and \predMap().
   2.739 +    ///
   2.740 +    /// \pre Either \ref run() or \ref init() must be called before
   2.741 +    /// using this function.
   2.742 +    Node predNode(Node v) const { 
   2.743 +      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
   2.744 +    }
   2.745 +    
   2.746 +    /// \brief Returns a const reference to the node map that stores the
   2.747 +    /// distances of the nodes.
   2.748 +    ///
   2.749 +    /// Returns a const reference to the node map that stores the distances
   2.750 +    /// of the nodes calculated by the algorithm.
   2.751 +    ///
   2.752 +    /// \pre Either \ref run() or \ref init() must be called before
   2.753 +    /// using this function.
   2.754 +    const DistMap &distMap() const { return *_dist;}
   2.755 + 
   2.756 +    /// \brief Returns a const reference to the node map that stores the
   2.757 +    /// predecessor arcs.
   2.758 +    ///
   2.759 +    /// Returns a const reference to the node map that stores the predecessor
   2.760 +    /// arcs, which form the shortest path tree (forest).
   2.761 +    ///
   2.762 +    /// \pre Either \ref run() or \ref init() must be called before
   2.763 +    /// using this function.
   2.764 +    const PredMap &predMap() const { return *_pred; }
   2.765 + 
   2.766 +    /// \brief Checks if a node is reached from the root(s).
   2.767 +    ///
   2.768 +    /// Returns \c true if \c v is reached from the root(s).
   2.769 +    ///
   2.770 +    /// \pre Either \ref run() or \ref init() must be called before
   2.771 +    /// using this function.
   2.772 +    bool reached(Node v) const {
   2.773 +      return (*_dist)[v] != OperationTraits::infinity();
   2.774 +    }
   2.775 +
   2.776 +    /// \brief Gives back a negative cycle.
   2.777 +    ///    
   2.778 +    /// This function gives back a directed cycle with negative total
   2.779 +    /// length if the algorithm has already found one.
   2.780 +    /// Otherwise it gives back an empty path.
   2.781 +    lemon::Path<Digraph> negativeCycle() {
   2.782 +      typename Digraph::template NodeMap<int> state(*_gr, -1);
   2.783 +      lemon::Path<Digraph> cycle;
   2.784 +      for (int i = 0; i < int(_process.size()); ++i) {
   2.785 +        if (state[_process[i]] != -1) continue;
   2.786 +        for (Node v = _process[i]; (*_pred)[v] != INVALID;
   2.787 +             v = _gr->source((*_pred)[v])) {
   2.788 +          if (state[v] == i) {
   2.789 +            cycle.addFront((*_pred)[v]);
   2.790 +            for (Node u = _gr->source((*_pred)[v]); u != v;
   2.791 +                 u = _gr->source((*_pred)[u])) {
   2.792 +              cycle.addFront((*_pred)[u]);
   2.793 +            }
   2.794 +            return cycle;
   2.795 +          }
   2.796 +          else if (state[v] >= 0) {
   2.797 +            break;
   2.798 +          }
   2.799 +          state[v] = i;
   2.800 +        }
   2.801 +      }
   2.802 +      return cycle;
   2.803 +    }
   2.804 +    
   2.805 +    ///@}
   2.806 +  };
   2.807 + 
   2.808 +  /// \brief Default traits class of bellmanFord() function.
   2.809 +  ///
   2.810 +  /// Default traits class of bellmanFord() function.
   2.811 +  /// \tparam GR The type of the digraph.
   2.812 +  /// \tparam LEN The type of the length map.
   2.813 +  template <typename GR, typename LEN>
   2.814 +  struct BellmanFordWizardDefaultTraits {
   2.815 +    /// The type of the digraph the algorithm runs on. 
   2.816 +    typedef GR Digraph;
   2.817 +
   2.818 +    /// \brief The type of the map that stores the arc lengths.
   2.819 +    ///
   2.820 +    /// The type of the map that stores the arc lengths.
   2.821 +    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
   2.822 +    typedef LEN LengthMap;
   2.823 +
   2.824 +    /// The type of the arc lengths.
   2.825 +    typedef typename LEN::Value Value;
   2.826 +
   2.827 +    /// \brief Operation traits for Bellman-Ford algorithm.
   2.828 +    ///
   2.829 +    /// It defines the used operations and the infinity value for the
   2.830 +    /// given \c Value type.
   2.831 +    /// \see BellmanFordDefaultOperationTraits
   2.832 +    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   2.833 +
   2.834 +    /// \brief The type of the map that stores the last
   2.835 +    /// arcs of the shortest paths.
   2.836 +    /// 
   2.837 +    /// The type of the map that stores the last arcs of the shortest paths.
   2.838 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.839 +    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   2.840 +
   2.841 +    /// \brief Instantiates a \c PredMap.
   2.842 +    /// 
   2.843 +    /// This function instantiates a \ref PredMap.
   2.844 +    /// \param g is the digraph to which we would like to define the
   2.845 +    /// \ref PredMap.
   2.846 +    static PredMap *createPredMap(const GR &g) {
   2.847 +      return new PredMap(g);
   2.848 +    }
   2.849 +
   2.850 +    /// \brief The type of the map that stores the distances of the nodes.
   2.851 +    ///
   2.852 +    /// The type of the map that stores the distances of the nodes.
   2.853 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.854 +    typedef typename GR::template NodeMap<Value> DistMap;
   2.855 +
   2.856 +    /// \brief Instantiates a \c DistMap.
   2.857 +    ///
   2.858 +    /// This function instantiates a \ref DistMap. 
   2.859 +    /// \param g is the digraph to which we would like to define the
   2.860 +    /// \ref DistMap.
   2.861 +    static DistMap *createDistMap(const GR &g) {
   2.862 +      return new DistMap(g);
   2.863 +    }
   2.864 +
   2.865 +    ///The type of the shortest paths.
   2.866 +
   2.867 +    ///The type of the shortest paths.
   2.868 +    ///It must meet the \ref concepts::Path "Path" concept.
   2.869 +    typedef lemon::Path<Digraph> Path;
   2.870 +  };
   2.871 +  
   2.872 +  /// \brief Default traits class used by BellmanFordWizard.
   2.873 +  ///
   2.874 +  /// Default traits class used by BellmanFordWizard.
   2.875 +  /// \tparam GR The type of the digraph.
   2.876 +  /// \tparam LEN The type of the length map.
   2.877 +  template <typename GR, typename LEN>
   2.878 +  class BellmanFordWizardBase 
   2.879 +    : public BellmanFordWizardDefaultTraits<GR, LEN> {
   2.880 +
   2.881 +    typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
   2.882 +  protected:
   2.883 +    // Type of the nodes in the digraph.
   2.884 +    typedef typename Base::Digraph::Node Node;
   2.885 +
   2.886 +    // Pointer to the underlying digraph.
   2.887 +    void *_graph;
   2.888 +    // Pointer to the length map
   2.889 +    void *_length;
   2.890 +    // Pointer to the map of predecessors arcs.
   2.891 +    void *_pred;
   2.892 +    // Pointer to the map of distances.
   2.893 +    void *_dist;
   2.894 +    //Pointer to the shortest path to the target node.
   2.895 +    void *_path;
   2.896 +    //Pointer to the distance of the target node.
   2.897 +    void *_di;
   2.898 +
   2.899 +    public:
   2.900 +    /// Constructor.
   2.901 +    
   2.902 +    /// This constructor does not require parameters, it initiates
   2.903 +    /// all of the attributes to default values \c 0.
   2.904 +    BellmanFordWizardBase() :
   2.905 +      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
   2.906 +
   2.907 +    /// Constructor.
   2.908 +    
   2.909 +    /// This constructor requires two parameters,
   2.910 +    /// others are initiated to \c 0.
   2.911 +    /// \param gr The digraph the algorithm runs on.
   2.912 +    /// \param len The length map.
   2.913 +    BellmanFordWizardBase(const GR& gr, 
   2.914 +			  const LEN& len) :
   2.915 +      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
   2.916 +      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
   2.917 +      _pred(0), _dist(0), _path(0), _di(0) {}
   2.918 +
   2.919 +  };
   2.920 +  
   2.921 +  /// \brief Auxiliary class for the function-type interface of the
   2.922 +  /// \ref BellmanFord "Bellman-Ford" algorithm.
   2.923 +  ///
   2.924 +  /// This auxiliary class is created to implement the
   2.925 +  /// \ref bellmanFord() "function-type interface" of the
   2.926 +  /// \ref BellmanFord "Bellman-Ford" algorithm.
   2.927 +  /// It does not have own \ref run() method, it uses the
   2.928 +  /// functions and features of the plain \ref BellmanFord.
   2.929 +  ///
   2.930 +  /// This class should only be used through the \ref bellmanFord()
   2.931 +  /// function, which makes it easier to use the algorithm.
   2.932 +  template<class TR>
   2.933 +  class BellmanFordWizard : public TR {
   2.934 +    typedef TR Base;
   2.935 +
   2.936 +    typedef typename TR::Digraph Digraph;
   2.937 +
   2.938 +    typedef typename Digraph::Node Node;
   2.939 +    typedef typename Digraph::NodeIt NodeIt;
   2.940 +    typedef typename Digraph::Arc Arc;
   2.941 +    typedef typename Digraph::OutArcIt ArcIt;
   2.942 +    
   2.943 +    typedef typename TR::LengthMap LengthMap;
   2.944 +    typedef typename LengthMap::Value Value;
   2.945 +    typedef typename TR::PredMap PredMap;
   2.946 +    typedef typename TR::DistMap DistMap;
   2.947 +    typedef typename TR::Path Path;
   2.948 +
   2.949 +  public:
   2.950 +    /// Constructor.
   2.951 +    BellmanFordWizard() : TR() {}
   2.952 +
   2.953 +    /// \brief Constructor that requires parameters.
   2.954 +    ///
   2.955 +    /// Constructor that requires parameters.
   2.956 +    /// These parameters will be the default values for the traits class.
   2.957 +    /// \param gr The digraph the algorithm runs on.
   2.958 +    /// \param len The length map.
   2.959 +    BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
   2.960 +      : TR(gr, len) {}
   2.961 +
   2.962 +    /// \brief Copy constructor
   2.963 +    BellmanFordWizard(const TR &b) : TR(b) {}
   2.964 +
   2.965 +    ~BellmanFordWizard() {}
   2.966 +
   2.967 +    /// \brief Runs the Bellman-Ford algorithm from the given source node.
   2.968 +    ///    
   2.969 +    /// This method runs the Bellman-Ford algorithm from the given source
   2.970 +    /// node in order to compute the shortest path to each node.
   2.971 +    void run(Node s) {
   2.972 +      BellmanFord<Digraph,LengthMap,TR> 
   2.973 +	bf(*reinterpret_cast<const Digraph*>(Base::_graph), 
   2.974 +           *reinterpret_cast<const LengthMap*>(Base::_length));
   2.975 +      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
   2.976 +      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   2.977 +      bf.run(s);
   2.978 +    }
   2.979 +
   2.980 +    /// \brief Runs the Bellman-Ford algorithm to find the shortest path
   2.981 +    /// between \c s and \c t.
   2.982 +    ///
   2.983 +    /// This method runs the Bellman-Ford algorithm from node \c s
   2.984 +    /// in order to compute the shortest path to node \c t.
   2.985 +    /// Actually, it computes the shortest path to each node, but using
   2.986 +    /// this function you can retrieve the distance and the shortest path
   2.987 +    /// for a single target node easier.
   2.988 +    ///
   2.989 +    /// \return \c true if \c t is reachable form \c s.
   2.990 +    bool run(Node s, Node t) {
   2.991 +      BellmanFord<Digraph,LengthMap,TR>
   2.992 +        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
   2.993 +           *reinterpret_cast<const LengthMap*>(Base::_length));
   2.994 +      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
   2.995 +      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   2.996 +      bf.run(s);
   2.997 +      if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
   2.998 +      if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
   2.999 +      return bf.reached(t);
  2.1000 +    }
  2.1001 +
  2.1002 +    template<class T>
  2.1003 +    struct SetPredMapBase : public Base {
  2.1004 +      typedef T PredMap;
  2.1005 +      static PredMap *createPredMap(const Digraph &) { return 0; };
  2.1006 +      SetPredMapBase(const TR &b) : TR(b) {}
  2.1007 +    };
  2.1008 +    
  2.1009 +    /// \brief \ref named-templ-param "Named parameter" for setting
  2.1010 +    /// the predecessor map.
  2.1011 +    ///
  2.1012 +    /// \ref named-templ-param "Named parameter" for setting
  2.1013 +    /// the map that stores the predecessor arcs of the nodes.
  2.1014 +    template<class T>
  2.1015 +    BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
  2.1016 +      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  2.1017 +      return BellmanFordWizard<SetPredMapBase<T> >(*this);
  2.1018 +    }
  2.1019 +    
  2.1020 +    template<class T>
  2.1021 +    struct SetDistMapBase : public Base {
  2.1022 +      typedef T DistMap;
  2.1023 +      static DistMap *createDistMap(const Digraph &) { return 0; };
  2.1024 +      SetDistMapBase(const TR &b) : TR(b) {}
  2.1025 +    };
  2.1026 +    
  2.1027 +    /// \brief \ref named-templ-param "Named parameter" for setting
  2.1028 +    /// the distance map.
  2.1029 +    ///
  2.1030 +    /// \ref named-templ-param "Named parameter" for setting
  2.1031 +    /// the map that stores the distances of the nodes calculated
  2.1032 +    /// by the algorithm.
  2.1033 +    template<class T>
  2.1034 +    BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
  2.1035 +      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  2.1036 +      return BellmanFordWizard<SetDistMapBase<T> >(*this);
  2.1037 +    }
  2.1038 +
  2.1039 +    template<class T>
  2.1040 +    struct SetPathBase : public Base {
  2.1041 +      typedef T Path;
  2.1042 +      SetPathBase(const TR &b) : TR(b) {}
  2.1043 +    };
  2.1044 +
  2.1045 +    /// \brief \ref named-func-param "Named parameter" for getting
  2.1046 +    /// the shortest path to the target node.
  2.1047 +    ///
  2.1048 +    /// \ref named-func-param "Named parameter" for getting
  2.1049 +    /// the shortest path to the target node.
  2.1050 +    template<class T>
  2.1051 +    BellmanFordWizard<SetPathBase<T> > path(const T &t)
  2.1052 +    {
  2.1053 +      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  2.1054 +      return BellmanFordWizard<SetPathBase<T> >(*this);
  2.1055 +    }
  2.1056 +
  2.1057 +    /// \brief \ref named-func-param "Named parameter" for getting
  2.1058 +    /// the distance of the target node.
  2.1059 +    ///
  2.1060 +    /// \ref named-func-param "Named parameter" for getting
  2.1061 +    /// the distance of the target node.
  2.1062 +    BellmanFordWizard dist(const Value &d)
  2.1063 +    {
  2.1064 +      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
  2.1065 +      return *this;
  2.1066 +    }
  2.1067 +    
  2.1068 +  };
  2.1069 +  
  2.1070 +  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
  2.1071 +  /// algorithm.
  2.1072 +  ///
  2.1073 +  /// \ingroup shortest_path
  2.1074 +  /// Function type interface for the \ref BellmanFord "Bellman-Ford"
  2.1075 +  /// algorithm.
  2.1076 +  ///
  2.1077 +  /// This function also has several \ref named-templ-func-param 
  2.1078 +  /// "named parameters", they are declared as the members of class 
  2.1079 +  /// \ref BellmanFordWizard.
  2.1080 +  /// The following examples show how to use these parameters.
  2.1081 +  /// \code
  2.1082 +  ///   // Compute shortest path from node s to each node
  2.1083 +  ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
  2.1084 +  ///
  2.1085 +  ///   // Compute shortest path from s to t
  2.1086 +  ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
  2.1087 +  /// \endcode
  2.1088 +  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
  2.1089 +  /// to the end of the parameter list.
  2.1090 +  /// \sa BellmanFordWizard
  2.1091 +  /// \sa BellmanFord
  2.1092 +  template<typename GR, typename LEN>
  2.1093 +  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
  2.1094 +  bellmanFord(const GR& digraph,
  2.1095 +	      const LEN& length)
  2.1096 +  {
  2.1097 +    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
  2.1098 +  }
  2.1099 +
  2.1100 +} //END OF NAMESPACE LEMON
  2.1101 +
  2.1102 +#endif
  2.1103 +
     3.1 --- a/test/CMakeLists.txt	Mon Aug 31 08:25:33 2009 +0200
     3.2 +++ b/test/CMakeLists.txt	Mon Aug 31 08:32:25 2009 +0200
     3.3 @@ -9,6 +9,7 @@
     3.4  
     3.5  SET(TESTS
     3.6    adaptors_test
     3.7 +  bellman_ford_test
     3.8    bfs_test
     3.9    circulation_test
    3.10    connectivity_test
     4.1 --- a/test/Makefile.am	Mon Aug 31 08:25:33 2009 +0200
     4.2 +++ b/test/Makefile.am	Mon Aug 31 08:32:25 2009 +0200
     4.3 @@ -7,6 +7,7 @@
     4.4  
     4.5  check_PROGRAMS += \
     4.6  	test/adaptors_test \
     4.7 +	test/bellman_ford_test \
     4.8  	test/bfs_test \
     4.9  	test/circulation_test \
    4.10  	test/connectivity_test \
    4.11 @@ -52,6 +53,7 @@
    4.12  XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    4.13  
    4.14  test_adaptors_test_SOURCES = test/adaptors_test.cc
    4.15 +test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    4.16  test_bfs_test_SOURCES = test/bfs_test.cc
    4.17  test_circulation_test_SOURCES = test/circulation_test.cc
    4.18  test_counter_test_SOURCES = test/counter_test.cc
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/test/bellman_ford_test.cc	Mon Aug 31 08:32:25 2009 +0200
     5.3 @@ -0,0 +1,283 @@
     5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     5.5 + *
     5.6 + * This file is a part of LEMON, a generic C++ optimization library.
     5.7 + *
     5.8 + * Copyright (C) 2003-2009
     5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 + *
    5.12 + * Permission to use, modify and distribute this software is granted
    5.13 + * provided that this copyright notice appears in all copies. For
    5.14 + * precise terms see the accompanying LICENSE file.
    5.15 + *
    5.16 + * This software is provided "AS IS" with no warranty of any kind,
    5.17 + * express or implied, and with no claim as to its suitability for any
    5.18 + * purpose.
    5.19 + *
    5.20 + */
    5.21 +
    5.22 +#include <lemon/concepts/digraph.h>
    5.23 +#include <lemon/smart_graph.h>
    5.24 +#include <lemon/list_graph.h>
    5.25 +#include <lemon/lgf_reader.h>
    5.26 +#include <lemon/bellman_ford.h>
    5.27 +#include <lemon/path.h>
    5.28 +
    5.29 +#include "graph_test.h"
    5.30 +#include "test_tools.h"
    5.31 +
    5.32 +using namespace lemon;
    5.33 +
    5.34 +char test_lgf[] =
    5.35 +  "@nodes\n"
    5.36 +  "label\n"
    5.37 +  "0\n"
    5.38 +  "1\n"
    5.39 +  "2\n"
    5.40 +  "3\n"
    5.41 +  "4\n"
    5.42 +  "@arcs\n"
    5.43 +  "    length\n"
    5.44 +  "0 1 3\n"
    5.45 +  "1 2 -3\n"
    5.46 +  "1 2 -5\n"
    5.47 +  "1 3 -2\n"
    5.48 +  "0 2 -1\n"
    5.49 +  "1 2 -4\n"
    5.50 +  "0 3 2\n"
    5.51 +  "4 2 -5\n"
    5.52 +  "2 3 1\n"
    5.53 +  "@attributes\n"
    5.54 +  "source 0\n"
    5.55 +  "target 3\n";
    5.56 +
    5.57 +
    5.58 +void checkBellmanFordCompile()
    5.59 +{
    5.60 +  typedef int Value;
    5.61 +  typedef concepts::Digraph Digraph;
    5.62 +  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
    5.63 +  typedef BellmanFord<Digraph, LengthMap> BF;
    5.64 +  typedef Digraph::Node Node;
    5.65 +  typedef Digraph::Arc Arc;
    5.66 +
    5.67 +  Digraph gr;
    5.68 +  Node s, t, n;
    5.69 +  Arc e;
    5.70 +  Value l;
    5.71 +  int k;
    5.72 +  bool b;
    5.73 +  BF::DistMap d(gr);
    5.74 +  BF::PredMap p(gr);
    5.75 +  LengthMap length;
    5.76 +  concepts::Path<Digraph> pp;
    5.77 +
    5.78 +  {
    5.79 +    BF bf_test(gr,length);
    5.80 +    const BF& const_bf_test = bf_test;
    5.81 +
    5.82 +    bf_test.run(s);
    5.83 +    bf_test.run(s,k);
    5.84 +
    5.85 +    bf_test.init();
    5.86 +    bf_test.addSource(s);
    5.87 +    bf_test.addSource(s, 1);
    5.88 +    b = bf_test.processNextRound();
    5.89 +    b = bf_test.processNextWeakRound();
    5.90 +
    5.91 +    bf_test.start();
    5.92 +    bf_test.checkedStart();
    5.93 +    bf_test.limitedStart(k);
    5.94 +
    5.95 +    l  = const_bf_test.dist(t);
    5.96 +    e  = const_bf_test.predArc(t);
    5.97 +    s  = const_bf_test.predNode(t);
    5.98 +    b  = const_bf_test.reached(t);
    5.99 +    d  = const_bf_test.distMap();
   5.100 +    p  = const_bf_test.predMap();
   5.101 +    pp = const_bf_test.path(t);
   5.102 +    
   5.103 +    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
   5.104 +  }
   5.105 +  {
   5.106 +    BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
   5.107 +      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
   5.108 +      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
   5.109 +      ::Create bf_test(gr,length);
   5.110 +
   5.111 +    LengthMap length_map;
   5.112 +    concepts::ReadWriteMap<Node,Arc> pred_map;
   5.113 +    concepts::ReadWriteMap<Node,Value> dist_map;
   5.114 +    
   5.115 +    bf_test
   5.116 +      .lengthMap(length_map)
   5.117 +      .predMap(pred_map)
   5.118 +      .distMap(dist_map);
   5.119 +
   5.120 +    bf_test.run(s);
   5.121 +    bf_test.run(s,k);
   5.122 +
   5.123 +    bf_test.init();
   5.124 +    bf_test.addSource(s);
   5.125 +    bf_test.addSource(s, 1);
   5.126 +    b = bf_test.processNextRound();
   5.127 +    b = bf_test.processNextWeakRound();
   5.128 +
   5.129 +    bf_test.start();
   5.130 +    bf_test.checkedStart();
   5.131 +    bf_test.limitedStart(k);
   5.132 +
   5.133 +    l  = bf_test.dist(t);
   5.134 +    e  = bf_test.predArc(t);
   5.135 +    s  = bf_test.predNode(t);
   5.136 +    b  = bf_test.reached(t);
   5.137 +    pp = bf_test.path(t);
   5.138 +  }
   5.139 +}
   5.140 +
   5.141 +void checkBellmanFordFunctionCompile()
   5.142 +{
   5.143 +  typedef int Value;
   5.144 +  typedef concepts::Digraph Digraph;
   5.145 +  typedef Digraph::Arc Arc;
   5.146 +  typedef Digraph::Node Node;
   5.147 +  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
   5.148 +
   5.149 +  Digraph g;
   5.150 +  bool b;
   5.151 +  bellmanFord(g,LengthMap()).run(Node());
   5.152 +  b = bellmanFord(g,LengthMap()).run(Node(),Node());
   5.153 +  bellmanFord(g,LengthMap())
   5.154 +    .predMap(concepts::ReadWriteMap<Node,Arc>())
   5.155 +    .distMap(concepts::ReadWriteMap<Node,Value>())
   5.156 +    .run(Node());
   5.157 +  b=bellmanFord(g,LengthMap())
   5.158 +    .predMap(concepts::ReadWriteMap<Node,Arc>())
   5.159 +    .distMap(concepts::ReadWriteMap<Node,Value>())
   5.160 +    .path(concepts::Path<Digraph>())
   5.161 +    .dist(Value())
   5.162 +    .run(Node(),Node());
   5.163 +}
   5.164 +
   5.165 +
   5.166 +template <typename Digraph, typename Value>
   5.167 +void checkBellmanFord() {
   5.168 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   5.169 +  typedef typename Digraph::template ArcMap<Value> LengthMap;
   5.170 +
   5.171 +  Digraph gr;
   5.172 +  Node s, t;
   5.173 +  LengthMap length(gr);
   5.174 +
   5.175 +  std::istringstream input(test_lgf);
   5.176 +  digraphReader(gr, input).
   5.177 +    arcMap("length", length).
   5.178 +    node("source", s).
   5.179 +    node("target", t).
   5.180 +    run();
   5.181 +
   5.182 +  BellmanFord<Digraph, LengthMap>
   5.183 +    bf(gr, length);
   5.184 +  bf.run(s);
   5.185 +  Path<Digraph> p = bf.path(t);
   5.186 +
   5.187 +  check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
   5.188 +  check(p.length() == 3, "path() found a wrong path.");
   5.189 +  check(checkPath(gr, p), "path() found a wrong path.");
   5.190 +  check(pathSource(gr, p) == s, "path() found a wrong path.");
   5.191 +  check(pathTarget(gr, p) == t, "path() found a wrong path.");
   5.192 +  
   5.193 +  ListPath<Digraph> path;
   5.194 +  Value dist;
   5.195 +  bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
   5.196 +
   5.197 +  check(reached && dist == -1, "Bellman-Ford found a wrong path.");
   5.198 +  check(path.length() == 3, "path() found a wrong path.");
   5.199 +  check(checkPath(gr, path), "path() found a wrong path.");
   5.200 +  check(pathSource(gr, path) == s, "path() found a wrong path.");
   5.201 +  check(pathTarget(gr, path) == t, "path() found a wrong path.");
   5.202 +
   5.203 +  for(ArcIt e(gr); e!=INVALID; ++e) {
   5.204 +    Node u=gr.source(e);
   5.205 +    Node v=gr.target(e);
   5.206 +    check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
   5.207 +          "Wrong output. dist(target)-dist(source)-arc_length=" <<
   5.208 +          bf.dist(v) - bf.dist(u) - length[e]);
   5.209 +  }
   5.210 +
   5.211 +  for(NodeIt v(gr); v!=INVALID; ++v) {
   5.212 +    if (bf.reached(v)) {
   5.213 +      check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
   5.214 +      if (bf.predArc(v)!=INVALID ) {
   5.215 +        Arc e=bf.predArc(v);
   5.216 +        Node u=gr.source(e);
   5.217 +        check(u==bf.predNode(v),"Wrong tree.");
   5.218 +        check(bf.dist(v) - bf.dist(u) == length[e],
   5.219 +              "Wrong distance! Difference: " <<
   5.220 +              bf.dist(v) - bf.dist(u) - length[e]);
   5.221 +      }
   5.222 +    }
   5.223 +  }
   5.224 +}
   5.225 +
   5.226 +void checkBellmanFordNegativeCycle() {
   5.227 +  DIGRAPH_TYPEDEFS(SmartDigraph);
   5.228 +
   5.229 +  SmartDigraph gr;
   5.230 +  IntArcMap length(gr);
   5.231 +  
   5.232 +  Node n1 = gr.addNode();
   5.233 +  Node n2 = gr.addNode();
   5.234 +  Node n3 = gr.addNode();
   5.235 +  Node n4 = gr.addNode();
   5.236 +  
   5.237 +  Arc a1 = gr.addArc(n1, n2);
   5.238 +  Arc a2 = gr.addArc(n2, n2);
   5.239 +  
   5.240 +  length[a1] = 2;
   5.241 +  length[a2] = -1;
   5.242 +  
   5.243 +  {
   5.244 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   5.245 +    bf.run(n1);
   5.246 +    StaticPath<SmartDigraph> p = bf.negativeCycle();
   5.247 +    check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
   5.248 +          "Wrong negative cycle.");
   5.249 +  }
   5.250 + 
   5.251 +  length[a2] = 0;
   5.252 +  
   5.253 +  {
   5.254 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   5.255 +    bf.run(n1);
   5.256 +    check(bf.negativeCycle().empty(),
   5.257 +          "Negative cycle should not be found.");
   5.258 +  }
   5.259 +  
   5.260 +  length[gr.addArc(n1, n3)] = 5;
   5.261 +  length[gr.addArc(n4, n3)] = 1;
   5.262 +  length[gr.addArc(n2, n4)] = 2;
   5.263 +  length[gr.addArc(n3, n2)] = -4;
   5.264 +  
   5.265 +  {
   5.266 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   5.267 +    bf.init();
   5.268 +    bf.addSource(n1);
   5.269 +    for (int i = 0; i < 4; ++i) {
   5.270 +      check(bf.negativeCycle().empty(),
   5.271 +            "Negative cycle should not be found.");
   5.272 +      bf.processNextRound();
   5.273 +    }
   5.274 +    StaticPath<SmartDigraph> p = bf.negativeCycle();
   5.275 +    check(p.length() == 3, "Wrong negative cycle.");
   5.276 +    check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
   5.277 +          "Wrong negative cycle.");
   5.278 +  }
   5.279 +}
   5.280 +
   5.281 +int main() {
   5.282 +  checkBellmanFord<ListDigraph, int>();
   5.283 +  checkBellmanFord<SmartDigraph, double>();
   5.284 +  checkBellmanFordNegativeCycle();
   5.285 +  return 0;
   5.286 +}