1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bellman_ford.h Tue Dec 20 18:15:14 2011 +0100
1.3 @@ -0,0 +1,1165 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2010
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_BELLMAN_FORD_H
1.23 +#define LEMON_BELLMAN_FORD_H
1.24 +
1.25 +/// \ingroup shortest_path
1.26 +/// \file
1.27 +/// \brief Bellman-Ford algorithm.
1.28 +
1.29 +#include <lemon/list_graph.h>
1.30 +#include <lemon/bits/path_dump.h>
1.31 +#include <lemon/core.h>
1.32 +#include <lemon/error.h>
1.33 +#include <lemon/maps.h>
1.34 +#include <lemon/tolerance.h>
1.35 +#include <lemon/path.h>
1.36 +
1.37 +#include <limits>
1.38 +
1.39 +namespace lemon {
1.40 +
1.41 + /// \brief Default operation traits for the BellmanFord algorithm class.
1.42 + ///
1.43 + /// This operation traits class defines all computational operations
1.44 + /// and constants that are used in the Bellman-Ford algorithm.
1.45 + /// The default implementation is based on the \c numeric_limits class.
1.46 + /// If the numeric type does not have infinity value, then the maximum
1.47 + /// value is used as extremal infinity value.
1.48 + ///
1.49 + /// \see BellmanFordToleranceOperationTraits
1.50 + template <
1.51 + typename V,
1.52 + bool has_inf = std::numeric_limits<V>::has_infinity>
1.53 + struct BellmanFordDefaultOperationTraits {
1.54 + /// \brief Value type for the algorithm.
1.55 + typedef V Value;
1.56 + /// \brief Gives back the zero value of the type.
1.57 + static Value zero() {
1.58 + return static_cast<Value>(0);
1.59 + }
1.60 + /// \brief Gives back the positive infinity value of the type.
1.61 + static Value infinity() {
1.62 + return std::numeric_limits<Value>::infinity();
1.63 + }
1.64 + /// \brief Gives back the sum of the given two elements.
1.65 + static Value plus(const Value& left, const Value& right) {
1.66 + return left + right;
1.67 + }
1.68 + /// \brief Gives back \c true only if the first value is less than
1.69 + /// the second.
1.70 + static bool less(const Value& left, const Value& right) {
1.71 + return left < right;
1.72 + }
1.73 + };
1.74 +
1.75 + template <typename V>
1.76 + struct BellmanFordDefaultOperationTraits<V, false> {
1.77 + typedef V Value;
1.78 + static Value zero() {
1.79 + return static_cast<Value>(0);
1.80 + }
1.81 + static Value infinity() {
1.82 + return std::numeric_limits<Value>::max();
1.83 + }
1.84 + static Value plus(const Value& left, const Value& right) {
1.85 + if (left == infinity() || right == infinity()) return infinity();
1.86 + return left + right;
1.87 + }
1.88 + static bool less(const Value& left, const Value& right) {
1.89 + return left < right;
1.90 + }
1.91 + };
1.92 +
1.93 + /// \brief Operation traits for the BellmanFord algorithm class
1.94 + /// using tolerance.
1.95 + ///
1.96 + /// This operation traits class defines all computational operations
1.97 + /// and constants that are used in the Bellman-Ford algorithm.
1.98 + /// The only difference between this implementation and
1.99 + /// \ref BellmanFordDefaultOperationTraits is that this class uses
1.100 + /// the \ref Tolerance "tolerance technique" in its \ref less()
1.101 + /// function.
1.102 + ///
1.103 + /// \tparam V The value type.
1.104 + /// \tparam eps The epsilon value for the \ref less() function.
1.105 + /// By default, it is the epsilon value used by \ref Tolerance
1.106 + /// "Tolerance<V>".
1.107 + ///
1.108 + /// \see BellmanFordDefaultOperationTraits
1.109 +#ifdef DOXYGEN
1.110 + template <typename V, V eps>
1.111 +#else
1.112 + template <
1.113 + typename V,
1.114 + V eps = Tolerance<V>::def_epsilon>
1.115 +#endif
1.116 + struct BellmanFordToleranceOperationTraits {
1.117 + /// \brief Value type for the algorithm.
1.118 + typedef V Value;
1.119 + /// \brief Gives back the zero value of the type.
1.120 + static Value zero() {
1.121 + return static_cast<Value>(0);
1.122 + }
1.123 + /// \brief Gives back the positive infinity value of the type.
1.124 + static Value infinity() {
1.125 + return std::numeric_limits<Value>::infinity();
1.126 + }
1.127 + /// \brief Gives back the sum of the given two elements.
1.128 + static Value plus(const Value& left, const Value& right) {
1.129 + return left + right;
1.130 + }
1.131 + /// \brief Gives back \c true only if the first value is less than
1.132 + /// the second.
1.133 + static bool less(const Value& left, const Value& right) {
1.134 + return left + eps < right;
1.135 + }
1.136 + };
1.137 +
1.138 + /// \brief Default traits class of BellmanFord class.
1.139 + ///
1.140 + /// Default traits class of BellmanFord class.
1.141 + /// \param GR The type of the digraph.
1.142 + /// \param LEN The type of the length map.
1.143 + template<typename GR, typename LEN>
1.144 + struct BellmanFordDefaultTraits {
1.145 + /// The type of the digraph the algorithm runs on.
1.146 + typedef GR Digraph;
1.147 +
1.148 + /// \brief The type of the map that stores the arc lengths.
1.149 + ///
1.150 + /// The type of the map that stores the arc lengths.
1.151 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.152 + typedef LEN LengthMap;
1.153 +
1.154 + /// The type of the arc lengths.
1.155 + typedef typename LEN::Value Value;
1.156 +
1.157 + /// \brief Operation traits for Bellman-Ford algorithm.
1.158 + ///
1.159 + /// It defines the used operations and the infinity value for the
1.160 + /// given \c Value type.
1.161 + /// \see BellmanFordDefaultOperationTraits,
1.162 + /// BellmanFordToleranceOperationTraits
1.163 + typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.164 +
1.165 + /// \brief The type of the map that stores the last arcs of the
1.166 + /// shortest paths.
1.167 + ///
1.168 + /// The type of the map that stores the last
1.169 + /// arcs of the shortest paths.
1.170 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.171 + typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
1.172 +
1.173 + /// \brief Instantiates a \c PredMap.
1.174 + ///
1.175 + /// This function instantiates a \ref PredMap.
1.176 + /// \param g is the digraph to which we would like to define the
1.177 + /// \ref PredMap.
1.178 + static PredMap *createPredMap(const GR& g) {
1.179 + return new PredMap(g);
1.180 + }
1.181 +
1.182 + /// \brief The type of the map that stores the distances of the nodes.
1.183 + ///
1.184 + /// The type of the map that stores the distances of the nodes.
1.185 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.186 + typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
1.187 +
1.188 + /// \brief Instantiates a \c DistMap.
1.189 + ///
1.190 + /// This function instantiates a \ref DistMap.
1.191 + /// \param g is the digraph to which we would like to define the
1.192 + /// \ref DistMap.
1.193 + static DistMap *createDistMap(const GR& g) {
1.194 + return new DistMap(g);
1.195 + }
1.196 +
1.197 + };
1.198 +
1.199 + /// \brief %BellmanFord algorithm class.
1.200 + ///
1.201 + /// \ingroup shortest_path
1.202 + /// This class provides an efficient implementation of the Bellman-Ford
1.203 + /// algorithm. The maximum time complexity of the algorithm is
1.204 + /// <tt>O(ne)</tt>.
1.205 + ///
1.206 + /// The Bellman-Ford algorithm solves the single-source shortest path
1.207 + /// problem when the arcs can have negative lengths, but the digraph
1.208 + /// should not contain directed cycles with negative total length.
1.209 + /// If all arc costs are non-negative, consider to use the Dijkstra
1.210 + /// algorithm instead, since it is more efficient.
1.211 + ///
1.212 + /// The arc lengths are passed to the algorithm using a
1.213 + /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
1.214 + /// kind of length. The type of the length values is determined by the
1.215 + /// \ref concepts::ReadMap::Value "Value" type of the length map.
1.216 + ///
1.217 + /// There is also a \ref bellmanFord() "function-type interface" for the
1.218 + /// Bellman-Ford algorithm, which is convenient in the simplier cases and
1.219 + /// it can be used easier.
1.220 + ///
1.221 + /// \tparam GR The type of the digraph the algorithm runs on.
1.222 + /// The default type is \ref ListDigraph.
1.223 + /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
1.224 + /// the lengths of the arcs. The default map type is
1.225 + /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.226 + /// \tparam TR The traits class that defines various types used by the
1.227 + /// algorithm. By default, it is \ref BellmanFordDefaultTraits
1.228 + /// "BellmanFordDefaultTraits<GR, LEN>".
1.229 + /// In most cases, this parameter should not be set directly,
1.230 + /// consider to use the named template parameters instead.
1.231 +#ifdef DOXYGEN
1.232 + template <typename GR, typename LEN, typename TR>
1.233 +#else
1.234 + template <typename GR=ListDigraph,
1.235 + typename LEN=typename GR::template ArcMap<int>,
1.236 + typename TR=BellmanFordDefaultTraits<GR,LEN> >
1.237 +#endif
1.238 + class BellmanFord {
1.239 + public:
1.240 +
1.241 + ///The type of the underlying digraph.
1.242 + typedef typename TR::Digraph Digraph;
1.243 +
1.244 + /// \brief The type of the arc lengths.
1.245 + typedef typename TR::LengthMap::Value Value;
1.246 + /// \brief The type of the map that stores the arc lengths.
1.247 + typedef typename TR::LengthMap LengthMap;
1.248 + /// \brief The type of the map that stores the last
1.249 + /// arcs of the shortest paths.
1.250 + typedef typename TR::PredMap PredMap;
1.251 + /// \brief The type of the map that stores the distances of the nodes.
1.252 + typedef typename TR::DistMap DistMap;
1.253 + /// The type of the paths.
1.254 + typedef PredMapPath<Digraph, PredMap> Path;
1.255 + ///\brief The \ref BellmanFordDefaultOperationTraits
1.256 + /// "operation traits class" of the algorithm.
1.257 + typedef typename TR::OperationTraits OperationTraits;
1.258 +
1.259 + ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
1.260 + typedef TR Traits;
1.261 +
1.262 + private:
1.263 +
1.264 + typedef typename Digraph::Node Node;
1.265 + typedef typename Digraph::NodeIt NodeIt;
1.266 + typedef typename Digraph::Arc Arc;
1.267 + typedef typename Digraph::OutArcIt OutArcIt;
1.268 +
1.269 + // Pointer to the underlying digraph.
1.270 + const Digraph *_gr;
1.271 + // Pointer to the length map
1.272 + const LengthMap *_length;
1.273 + // Pointer to the map of predecessors arcs.
1.274 + PredMap *_pred;
1.275 + // Indicates if _pred is locally allocated (true) or not.
1.276 + bool _local_pred;
1.277 + // Pointer to the map of distances.
1.278 + DistMap *_dist;
1.279 + // Indicates if _dist is locally allocated (true) or not.
1.280 + bool _local_dist;
1.281 +
1.282 + typedef typename Digraph::template NodeMap<bool> MaskMap;
1.283 + MaskMap *_mask;
1.284 +
1.285 + std::vector<Node> _process;
1.286 +
1.287 + // Creates the maps if necessary.
1.288 + void create_maps() {
1.289 + if(!_pred) {
1.290 + _local_pred = true;
1.291 + _pred = Traits::createPredMap(*_gr);
1.292 + }
1.293 + if(!_dist) {
1.294 + _local_dist = true;
1.295 + _dist = Traits::createDistMap(*_gr);
1.296 + }
1.297 + if(!_mask) {
1.298 + _mask = new MaskMap(*_gr);
1.299 + }
1.300 + }
1.301 +
1.302 + public :
1.303 +
1.304 + typedef BellmanFord Create;
1.305 +
1.306 + /// \name Named Template Parameters
1.307 +
1.308 + ///@{
1.309 +
1.310 + template <class T>
1.311 + struct SetPredMapTraits : public Traits {
1.312 + typedef T PredMap;
1.313 + static PredMap *createPredMap(const Digraph&) {
1.314 + LEMON_ASSERT(false, "PredMap is not initialized");
1.315 + return 0; // ignore warnings
1.316 + }
1.317 + };
1.318 +
1.319 + /// \brief \ref named-templ-param "Named parameter" for setting
1.320 + /// \c PredMap type.
1.321 + ///
1.322 + /// \ref named-templ-param "Named parameter" for setting
1.323 + /// \c PredMap type.
1.324 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.325 + template <class T>
1.326 + struct SetPredMap
1.327 + : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
1.328 + typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
1.329 + };
1.330 +
1.331 + template <class T>
1.332 + struct SetDistMapTraits : public Traits {
1.333 + typedef T DistMap;
1.334 + static DistMap *createDistMap(const Digraph&) {
1.335 + LEMON_ASSERT(false, "DistMap is not initialized");
1.336 + return 0; // ignore warnings
1.337 + }
1.338 + };
1.339 +
1.340 + /// \brief \ref named-templ-param "Named parameter" for setting
1.341 + /// \c DistMap type.
1.342 + ///
1.343 + /// \ref named-templ-param "Named parameter" for setting
1.344 + /// \c DistMap type.
1.345 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.346 + template <class T>
1.347 + struct SetDistMap
1.348 + : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
1.349 + typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
1.350 + };
1.351 +
1.352 + template <class T>
1.353 + struct SetOperationTraitsTraits : public Traits {
1.354 + typedef T OperationTraits;
1.355 + };
1.356 +
1.357 + /// \brief \ref named-templ-param "Named parameter" for setting
1.358 + /// \c OperationTraits type.
1.359 + ///
1.360 + /// \ref named-templ-param "Named parameter" for setting
1.361 + /// \c OperationTraits type.
1.362 + /// For more information, see \ref BellmanFordDefaultOperationTraits.
1.363 + template <class T>
1.364 + struct SetOperationTraits
1.365 + : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
1.366 + typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
1.367 + Create;
1.368 + };
1.369 +
1.370 + ///@}
1.371 +
1.372 + protected:
1.373 +
1.374 + BellmanFord() {}
1.375 +
1.376 + public:
1.377 +
1.378 + /// \brief Constructor.
1.379 + ///
1.380 + /// Constructor.
1.381 + /// \param g The digraph the algorithm runs on.
1.382 + /// \param length The length map used by the algorithm.
1.383 + BellmanFord(const Digraph& g, const LengthMap& length) :
1.384 + _gr(&g), _length(&length),
1.385 + _pred(0), _local_pred(false),
1.386 + _dist(0), _local_dist(false), _mask(0) {}
1.387 +
1.388 + ///Destructor.
1.389 + ~BellmanFord() {
1.390 + if(_local_pred) delete _pred;
1.391 + if(_local_dist) delete _dist;
1.392 + if(_mask) delete _mask;
1.393 + }
1.394 +
1.395 + /// \brief Sets the length map.
1.396 + ///
1.397 + /// Sets the length map.
1.398 + /// \return <tt>(*this)</tt>
1.399 + BellmanFord &lengthMap(const LengthMap &map) {
1.400 + _length = ↦
1.401 + return *this;
1.402 + }
1.403 +
1.404 + /// \brief Sets the map that stores the predecessor arcs.
1.405 + ///
1.406 + /// Sets the map that stores the predecessor arcs.
1.407 + /// If you don't use this function before calling \ref run()
1.408 + /// or \ref init(), an instance will be allocated automatically.
1.409 + /// The destructor deallocates this automatically allocated map,
1.410 + /// of course.
1.411 + /// \return <tt>(*this)</tt>
1.412 + BellmanFord &predMap(PredMap &map) {
1.413 + if(_local_pred) {
1.414 + delete _pred;
1.415 + _local_pred=false;
1.416 + }
1.417 + _pred = ↦
1.418 + return *this;
1.419 + }
1.420 +
1.421 + /// \brief Sets the map that stores the distances of the nodes.
1.422 + ///
1.423 + /// Sets the map that stores the distances of the nodes calculated
1.424 + /// by the algorithm.
1.425 + /// If you don't use this function before calling \ref run()
1.426 + /// or \ref init(), an instance will be allocated automatically.
1.427 + /// The destructor deallocates this automatically allocated map,
1.428 + /// of course.
1.429 + /// \return <tt>(*this)</tt>
1.430 + BellmanFord &distMap(DistMap &map) {
1.431 + if(_local_dist) {
1.432 + delete _dist;
1.433 + _local_dist=false;
1.434 + }
1.435 + _dist = ↦
1.436 + return *this;
1.437 + }
1.438 +
1.439 + /// \name Execution Control
1.440 + /// The simplest way to execute the Bellman-Ford algorithm is to use
1.441 + /// one of the member functions called \ref run().\n
1.442 + /// If you need better control on the execution, you have to call
1.443 + /// \ref init() first, then you can add several source nodes
1.444 + /// with \ref addSource(). Finally the actual path computation can be
1.445 + /// performed with \ref start(), \ref checkedStart() or
1.446 + /// \ref limitedStart().
1.447 +
1.448 + ///@{
1.449 +
1.450 + /// \brief Initializes the internal data structures.
1.451 + ///
1.452 + /// Initializes the internal data structures. The optional parameter
1.453 + /// is the initial distance of each node.
1.454 + void init(const Value value = OperationTraits::infinity()) {
1.455 + create_maps();
1.456 + for (NodeIt it(*_gr); it != INVALID; ++it) {
1.457 + _pred->set(it, INVALID);
1.458 + _dist->set(it, value);
1.459 + }
1.460 + _process.clear();
1.461 + if (OperationTraits::less(value, OperationTraits::infinity())) {
1.462 + for (NodeIt it(*_gr); it != INVALID; ++it) {
1.463 + _process.push_back(it);
1.464 + _mask->set(it, true);
1.465 + }
1.466 + } else {
1.467 + for (NodeIt it(*_gr); it != INVALID; ++it) {
1.468 + _mask->set(it, false);
1.469 + }
1.470 + }
1.471 + }
1.472 +
1.473 + /// \brief Adds a new source node.
1.474 + ///
1.475 + /// This function adds a new source node. The optional second parameter
1.476 + /// is the initial distance of the node.
1.477 + void addSource(Node source, Value dst = OperationTraits::zero()) {
1.478 + _dist->set(source, dst);
1.479 + if (!(*_mask)[source]) {
1.480 + _process.push_back(source);
1.481 + _mask->set(source, true);
1.482 + }
1.483 + }
1.484 +
1.485 + /// \brief Executes one round from the Bellman-Ford algorithm.
1.486 + ///
1.487 + /// If the algoritm calculated the distances in the previous round
1.488 + /// exactly for the paths of at most \c k arcs, then this function
1.489 + /// will calculate the distances exactly for the paths of at most
1.490 + /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
1.491 + /// calculates the shortest path distances exactly for the paths
1.492 + /// consisting of at most \c k arcs.
1.493 + ///
1.494 + /// \warning The paths with limited arc number cannot be retrieved
1.495 + /// easily with \ref path() or \ref predArc() functions. If you also
1.496 + /// need the shortest paths and not only the distances, you should
1.497 + /// store the \ref predMap() "predecessor map" after each iteration
1.498 + /// and build the path manually.
1.499 + ///
1.500 + /// \return \c true when the algorithm have not found more shorter
1.501 + /// paths.
1.502 + ///
1.503 + /// \see ActiveIt
1.504 + bool processNextRound() {
1.505 + for (int i = 0; i < int(_process.size()); ++i) {
1.506 + _mask->set(_process[i], false);
1.507 + }
1.508 + std::vector<Node> nextProcess;
1.509 + std::vector<Value> values(_process.size());
1.510 + for (int i = 0; i < int(_process.size()); ++i) {
1.511 + values[i] = (*_dist)[_process[i]];
1.512 + }
1.513 + for (int i = 0; i < int(_process.size()); ++i) {
1.514 + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
1.515 + Node target = _gr->target(it);
1.516 + Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
1.517 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.518 + _pred->set(target, it);
1.519 + _dist->set(target, relaxed);
1.520 + if (!(*_mask)[target]) {
1.521 + _mask->set(target, true);
1.522 + nextProcess.push_back(target);
1.523 + }
1.524 + }
1.525 + }
1.526 + }
1.527 + _process.swap(nextProcess);
1.528 + return _process.empty();
1.529 + }
1.530 +
1.531 + /// \brief Executes one weak round from the Bellman-Ford algorithm.
1.532 + ///
1.533 + /// If the algorithm calculated the distances in the previous round
1.534 + /// at least for the paths of at most \c k arcs, then this function
1.535 + /// will calculate the distances at least for the paths of at most
1.536 + /// <tt>k+1</tt> arcs.
1.537 + /// This function does not make it possible to calculate the shortest
1.538 + /// path distances exactly for paths consisting of at most \c k arcs,
1.539 + /// this is why it is called weak round.
1.540 + ///
1.541 + /// \return \c true when the algorithm have not found more shorter
1.542 + /// paths.
1.543 + ///
1.544 + /// \see ActiveIt
1.545 + bool processNextWeakRound() {
1.546 + for (int i = 0; i < int(_process.size()); ++i) {
1.547 + _mask->set(_process[i], false);
1.548 + }
1.549 + std::vector<Node> nextProcess;
1.550 + for (int i = 0; i < int(_process.size()); ++i) {
1.551 + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
1.552 + Node target = _gr->target(it);
1.553 + Value relaxed =
1.554 + OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
1.555 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.556 + _pred->set(target, it);
1.557 + _dist->set(target, relaxed);
1.558 + if (!(*_mask)[target]) {
1.559 + _mask->set(target, true);
1.560 + nextProcess.push_back(target);
1.561 + }
1.562 + }
1.563 + }
1.564 + }
1.565 + _process.swap(nextProcess);
1.566 + return _process.empty();
1.567 + }
1.568 +
1.569 + /// \brief Executes the algorithm.
1.570 + ///
1.571 + /// Executes the algorithm.
1.572 + ///
1.573 + /// This method runs the Bellman-Ford algorithm from the root node(s)
1.574 + /// in order to compute the shortest path to each node.
1.575 + ///
1.576 + /// The algorithm computes
1.577 + /// - the shortest path tree (forest),
1.578 + /// - the distance of each node from the root(s).
1.579 + ///
1.580 + /// \pre init() must be called and at least one root node should be
1.581 + /// added with addSource() before using this function.
1.582 + void start() {
1.583 + int num = countNodes(*_gr) - 1;
1.584 + for (int i = 0; i < num; ++i) {
1.585 + if (processNextWeakRound()) break;
1.586 + }
1.587 + }
1.588 +
1.589 + /// \brief Executes the algorithm and checks the negative cycles.
1.590 + ///
1.591 + /// Executes the algorithm and checks the negative cycles.
1.592 + ///
1.593 + /// This method runs the Bellman-Ford algorithm from the root node(s)
1.594 + /// in order to compute the shortest path to each node and also checks
1.595 + /// if the digraph contains cycles with negative total length.
1.596 + ///
1.597 + /// The algorithm computes
1.598 + /// - the shortest path tree (forest),
1.599 + /// - the distance of each node from the root(s).
1.600 + ///
1.601 + /// \return \c false if there is a negative cycle in the digraph.
1.602 + ///
1.603 + /// \pre init() must be called and at least one root node should be
1.604 + /// added with addSource() before using this function.
1.605 + bool checkedStart() {
1.606 + int num = countNodes(*_gr);
1.607 + for (int i = 0; i < num; ++i) {
1.608 + if (processNextWeakRound()) return true;
1.609 + }
1.610 + return _process.empty();
1.611 + }
1.612 +
1.613 + /// \brief Executes the algorithm with arc number limit.
1.614 + ///
1.615 + /// Executes the algorithm with arc number limit.
1.616 + ///
1.617 + /// This method runs the Bellman-Ford algorithm from the root node(s)
1.618 + /// in order to compute the shortest path distance for each node
1.619 + /// using only the paths consisting of at most \c num arcs.
1.620 + ///
1.621 + /// The algorithm computes
1.622 + /// - the limited distance of each node from the root(s),
1.623 + /// - the predecessor arc for each node.
1.624 + ///
1.625 + /// \warning The paths with limited arc number cannot be retrieved
1.626 + /// easily with \ref path() or \ref predArc() functions. If you also
1.627 + /// need the shortest paths and not only the distances, you should
1.628 + /// store the \ref predMap() "predecessor map" after each iteration
1.629 + /// and build the path manually.
1.630 + ///
1.631 + /// \pre init() must be called and at least one root node should be
1.632 + /// added with addSource() before using this function.
1.633 + void limitedStart(int num) {
1.634 + for (int i = 0; i < num; ++i) {
1.635 + if (processNextRound()) break;
1.636 + }
1.637 + }
1.638 +
1.639 + /// \brief Runs the algorithm from the given root node.
1.640 + ///
1.641 + /// This method runs the Bellman-Ford algorithm from the given root
1.642 + /// node \c s in order to compute the shortest path to each node.
1.643 + ///
1.644 + /// The algorithm computes
1.645 + /// - the shortest path tree (forest),
1.646 + /// - the distance of each node from the root(s).
1.647 + ///
1.648 + /// \note bf.run(s) is just a shortcut of the following code.
1.649 + /// \code
1.650 + /// bf.init();
1.651 + /// bf.addSource(s);
1.652 + /// bf.start();
1.653 + /// \endcode
1.654 + void run(Node s) {
1.655 + init();
1.656 + addSource(s);
1.657 + start();
1.658 + }
1.659 +
1.660 + /// \brief Runs the algorithm from the given root node with arc
1.661 + /// number limit.
1.662 + ///
1.663 + /// This method runs the Bellman-Ford algorithm from the given root
1.664 + /// node \c s in order to compute the shortest path distance for each
1.665 + /// node using only the paths consisting of at most \c num arcs.
1.666 + ///
1.667 + /// The algorithm computes
1.668 + /// - the limited distance of each node from the root(s),
1.669 + /// - the predecessor arc for each node.
1.670 + ///
1.671 + /// \warning The paths with limited arc number cannot be retrieved
1.672 + /// easily with \ref path() or \ref predArc() functions. If you also
1.673 + /// need the shortest paths and not only the distances, you should
1.674 + /// store the \ref predMap() "predecessor map" after each iteration
1.675 + /// and build the path manually.
1.676 + ///
1.677 + /// \note bf.run(s, num) is just a shortcut of the following code.
1.678 + /// \code
1.679 + /// bf.init();
1.680 + /// bf.addSource(s);
1.681 + /// bf.limitedStart(num);
1.682 + /// \endcode
1.683 + void run(Node s, int num) {
1.684 + init();
1.685 + addSource(s);
1.686 + limitedStart(num);
1.687 + }
1.688 +
1.689 + ///@}
1.690 +
1.691 + /// \brief LEMON iterator for getting the active nodes.
1.692 + ///
1.693 + /// This class provides a common style LEMON iterator that traverses
1.694 + /// the active nodes of the Bellman-Ford algorithm after the last
1.695 + /// phase. These nodes should be checked in the next phase to
1.696 + /// find augmenting arcs outgoing from them.
1.697 + class ActiveIt {
1.698 + public:
1.699 +
1.700 + /// \brief Constructor.
1.701 + ///
1.702 + /// Constructor for getting the active nodes of the given BellmanFord
1.703 + /// instance.
1.704 + ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
1.705 + {
1.706 + _index = _algorithm->_process.size() - 1;
1.707 + }
1.708 +
1.709 + /// \brief Invalid constructor.
1.710 + ///
1.711 + /// Invalid constructor.
1.712 + ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
1.713 +
1.714 + /// \brief Conversion to \c Node.
1.715 + ///
1.716 + /// Conversion to \c Node.
1.717 + operator Node() const {
1.718 + return _index >= 0 ? _algorithm->_process[_index] : INVALID;
1.719 + }
1.720 +
1.721 + /// \brief Increment operator.
1.722 + ///
1.723 + /// Increment operator.
1.724 + ActiveIt& operator++() {
1.725 + --_index;
1.726 + return *this;
1.727 + }
1.728 +
1.729 + bool operator==(const ActiveIt& it) const {
1.730 + return static_cast<Node>(*this) == static_cast<Node>(it);
1.731 + }
1.732 + bool operator!=(const ActiveIt& it) const {
1.733 + return static_cast<Node>(*this) != static_cast<Node>(it);
1.734 + }
1.735 + bool operator<(const ActiveIt& it) const {
1.736 + return static_cast<Node>(*this) < static_cast<Node>(it);
1.737 + }
1.738 +
1.739 + private:
1.740 + const BellmanFord* _algorithm;
1.741 + int _index;
1.742 + };
1.743 +
1.744 + /// \name Query Functions
1.745 + /// The result of the Bellman-Ford algorithm can be obtained using these
1.746 + /// functions.\n
1.747 + /// Either \ref run() or \ref init() should be called before using them.
1.748 +
1.749 + ///@{
1.750 +
1.751 + /// \brief The shortest path to the given node.
1.752 + ///
1.753 + /// Gives back the shortest path to the given node from the root(s).
1.754 + ///
1.755 + /// \warning \c t should be reached from the root(s).
1.756 + ///
1.757 + /// \pre Either \ref run() or \ref init() must be called before
1.758 + /// using this function.
1.759 + Path path(Node t) const
1.760 + {
1.761 + return Path(*_gr, *_pred, t);
1.762 + }
1.763 +
1.764 + /// \brief The distance of the given node from the root(s).
1.765 + ///
1.766 + /// Returns the distance of the given node from the root(s).
1.767 + ///
1.768 + /// \warning If node \c v is not reached from the root(s), then
1.769 + /// the return value of this function is undefined.
1.770 + ///
1.771 + /// \pre Either \ref run() or \ref init() must be called before
1.772 + /// using this function.
1.773 + Value dist(Node v) const { return (*_dist)[v]; }
1.774 +
1.775 + /// \brief Returns the 'previous arc' of the shortest path tree for
1.776 + /// the given node.
1.777 + ///
1.778 + /// This function returns the 'previous arc' of the shortest path
1.779 + /// tree for node \c v, i.e. it returns the last arc of a
1.780 + /// shortest path from a root to \c v. It is \c INVALID if \c v
1.781 + /// is not reached from the root(s) or if \c v is a root.
1.782 + ///
1.783 + /// The shortest path tree used here is equal to the shortest path
1.784 + /// tree used in \ref predNode() and \ref predMap().
1.785 + ///
1.786 + /// \pre Either \ref run() or \ref init() must be called before
1.787 + /// using this function.
1.788 + Arc predArc(Node v) const { return (*_pred)[v]; }
1.789 +
1.790 + /// \brief Returns the 'previous node' of the shortest path tree for
1.791 + /// the given node.
1.792 + ///
1.793 + /// This function returns the 'previous node' of the shortest path
1.794 + /// tree for node \c v, i.e. it returns the last but one node of
1.795 + /// a shortest path from a root to \c v. It is \c INVALID if \c v
1.796 + /// is not reached from the root(s) or if \c v is a root.
1.797 + ///
1.798 + /// The shortest path tree used here is equal to the shortest path
1.799 + /// tree used in \ref predArc() and \ref predMap().
1.800 + ///
1.801 + /// \pre Either \ref run() or \ref init() must be called before
1.802 + /// using this function.
1.803 + Node predNode(Node v) const {
1.804 + return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
1.805 + }
1.806 +
1.807 + /// \brief Returns a const reference to the node map that stores the
1.808 + /// distances of the nodes.
1.809 + ///
1.810 + /// Returns a const reference to the node map that stores the distances
1.811 + /// of the nodes calculated by the algorithm.
1.812 + ///
1.813 + /// \pre Either \ref run() or \ref init() must be called before
1.814 + /// using this function.
1.815 + const DistMap &distMap() const { return *_dist;}
1.816 +
1.817 + /// \brief Returns a const reference to the node map that stores the
1.818 + /// predecessor arcs.
1.819 + ///
1.820 + /// Returns a const reference to the node map that stores the predecessor
1.821 + /// arcs, which form the shortest path tree (forest).
1.822 + ///
1.823 + /// \pre Either \ref run() or \ref init() must be called before
1.824 + /// using this function.
1.825 + const PredMap &predMap() const { return *_pred; }
1.826 +
1.827 + /// \brief Checks if a node is reached from the root(s).
1.828 + ///
1.829 + /// Returns \c true if \c v is reached from the root(s).
1.830 + ///
1.831 + /// \pre Either \ref run() or \ref init() must be called before
1.832 + /// using this function.
1.833 + bool reached(Node v) const {
1.834 + return (*_dist)[v] != OperationTraits::infinity();
1.835 + }
1.836 +
1.837 + /// \brief Gives back a negative cycle.
1.838 + ///
1.839 + /// This function gives back a directed cycle with negative total
1.840 + /// length if the algorithm has already found one.
1.841 + /// Otherwise it gives back an empty path.
1.842 + lemon::Path<Digraph> negativeCycle() const {
1.843 + typename Digraph::template NodeMap<int> state(*_gr, -1);
1.844 + lemon::Path<Digraph> cycle;
1.845 + for (int i = 0; i < int(_process.size()); ++i) {
1.846 + if (state[_process[i]] != -1) continue;
1.847 + for (Node v = _process[i]; (*_pred)[v] != INVALID;
1.848 + v = _gr->source((*_pred)[v])) {
1.849 + if (state[v] == i) {
1.850 + cycle.addFront((*_pred)[v]);
1.851 + for (Node u = _gr->source((*_pred)[v]); u != v;
1.852 + u = _gr->source((*_pred)[u])) {
1.853 + cycle.addFront((*_pred)[u]);
1.854 + }
1.855 + return cycle;
1.856 + }
1.857 + else if (state[v] >= 0) {
1.858 + break;
1.859 + }
1.860 + state[v] = i;
1.861 + }
1.862 + }
1.863 + return cycle;
1.864 + }
1.865 +
1.866 + ///@}
1.867 + };
1.868 +
1.869 + /// \brief Default traits class of bellmanFord() function.
1.870 + ///
1.871 + /// Default traits class of bellmanFord() function.
1.872 + /// \tparam GR The type of the digraph.
1.873 + /// \tparam LEN The type of the length map.
1.874 + template <typename GR, typename LEN>
1.875 + struct BellmanFordWizardDefaultTraits {
1.876 + /// The type of the digraph the algorithm runs on.
1.877 + typedef GR Digraph;
1.878 +
1.879 + /// \brief The type of the map that stores the arc lengths.
1.880 + ///
1.881 + /// The type of the map that stores the arc lengths.
1.882 + /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.883 + typedef LEN LengthMap;
1.884 +
1.885 + /// The type of the arc lengths.
1.886 + typedef typename LEN::Value Value;
1.887 +
1.888 + /// \brief Operation traits for Bellman-Ford algorithm.
1.889 + ///
1.890 + /// It defines the used operations and the infinity value for the
1.891 + /// given \c Value type.
1.892 + /// \see BellmanFordDefaultOperationTraits,
1.893 + /// BellmanFordToleranceOperationTraits
1.894 + typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.895 +
1.896 + /// \brief The type of the map that stores the last
1.897 + /// arcs of the shortest paths.
1.898 + ///
1.899 + /// The type of the map that stores the last arcs of the shortest paths.
1.900 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.901 + typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
1.902 +
1.903 + /// \brief Instantiates a \c PredMap.
1.904 + ///
1.905 + /// This function instantiates a \ref PredMap.
1.906 + /// \param g is the digraph to which we would like to define the
1.907 + /// \ref PredMap.
1.908 + static PredMap *createPredMap(const GR &g) {
1.909 + return new PredMap(g);
1.910 + }
1.911 +
1.912 + /// \brief The type of the map that stores the distances of the nodes.
1.913 + ///
1.914 + /// The type of the map that stores the distances of the nodes.
1.915 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.916 + typedef typename GR::template NodeMap<Value> DistMap;
1.917 +
1.918 + /// \brief Instantiates a \c DistMap.
1.919 + ///
1.920 + /// This function instantiates a \ref DistMap.
1.921 + /// \param g is the digraph to which we would like to define the
1.922 + /// \ref DistMap.
1.923 + static DistMap *createDistMap(const GR &g) {
1.924 + return new DistMap(g);
1.925 + }
1.926 +
1.927 + ///The type of the shortest paths.
1.928 +
1.929 + ///The type of the shortest paths.
1.930 + ///It must meet the \ref concepts::Path "Path" concept.
1.931 + typedef lemon::Path<Digraph> Path;
1.932 + };
1.933 +
1.934 + /// \brief Default traits class used by BellmanFordWizard.
1.935 + ///
1.936 + /// Default traits class used by BellmanFordWizard.
1.937 + /// \tparam GR The type of the digraph.
1.938 + /// \tparam LEN The type of the length map.
1.939 + template <typename GR, typename LEN>
1.940 + class BellmanFordWizardBase
1.941 + : public BellmanFordWizardDefaultTraits<GR, LEN> {
1.942 +
1.943 + typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
1.944 + protected:
1.945 + // Type of the nodes in the digraph.
1.946 + typedef typename Base::Digraph::Node Node;
1.947 +
1.948 + // Pointer to the underlying digraph.
1.949 + void *_graph;
1.950 + // Pointer to the length map
1.951 + void *_length;
1.952 + // Pointer to the map of predecessors arcs.
1.953 + void *_pred;
1.954 + // Pointer to the map of distances.
1.955 + void *_dist;
1.956 + //Pointer to the shortest path to the target node.
1.957 + void *_path;
1.958 + //Pointer to the distance of the target node.
1.959 + void *_di;
1.960 +
1.961 + public:
1.962 + /// Constructor.
1.963 +
1.964 + /// This constructor does not require parameters, it initiates
1.965 + /// all of the attributes to default values \c 0.
1.966 + BellmanFordWizardBase() :
1.967 + _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.968 +
1.969 + /// Constructor.
1.970 +
1.971 + /// This constructor requires two parameters,
1.972 + /// others are initiated to \c 0.
1.973 + /// \param gr The digraph the algorithm runs on.
1.974 + /// \param len The length map.
1.975 + BellmanFordWizardBase(const GR& gr,
1.976 + const LEN& len) :
1.977 + _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
1.978 + _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
1.979 + _pred(0), _dist(0), _path(0), _di(0) {}
1.980 +
1.981 + };
1.982 +
1.983 + /// \brief Auxiliary class for the function-type interface of the
1.984 + /// \ref BellmanFord "Bellman-Ford" algorithm.
1.985 + ///
1.986 + /// This auxiliary class is created to implement the
1.987 + /// \ref bellmanFord() "function-type interface" of the
1.988 + /// \ref BellmanFord "Bellman-Ford" algorithm.
1.989 + /// It does not have own \ref run() method, it uses the
1.990 + /// functions and features of the plain \ref BellmanFord.
1.991 + ///
1.992 + /// This class should only be used through the \ref bellmanFord()
1.993 + /// function, which makes it easier to use the algorithm.
1.994 + ///
1.995 + /// \tparam TR The traits class that defines various types used by the
1.996 + /// algorithm.
1.997 + template<class TR>
1.998 + class BellmanFordWizard : public TR {
1.999 + typedef TR Base;
1.1000 +
1.1001 + typedef typename TR::Digraph Digraph;
1.1002 +
1.1003 + typedef typename Digraph::Node Node;
1.1004 + typedef typename Digraph::NodeIt NodeIt;
1.1005 + typedef typename Digraph::Arc Arc;
1.1006 + typedef typename Digraph::OutArcIt ArcIt;
1.1007 +
1.1008 + typedef typename TR::LengthMap LengthMap;
1.1009 + typedef typename LengthMap::Value Value;
1.1010 + typedef typename TR::PredMap PredMap;
1.1011 + typedef typename TR::DistMap DistMap;
1.1012 + typedef typename TR::Path Path;
1.1013 +
1.1014 + public:
1.1015 + /// Constructor.
1.1016 + BellmanFordWizard() : TR() {}
1.1017 +
1.1018 + /// \brief Constructor that requires parameters.
1.1019 + ///
1.1020 + /// Constructor that requires parameters.
1.1021 + /// These parameters will be the default values for the traits class.
1.1022 + /// \param gr The digraph the algorithm runs on.
1.1023 + /// \param len The length map.
1.1024 + BellmanFordWizard(const Digraph& gr, const LengthMap& len)
1.1025 + : TR(gr, len) {}
1.1026 +
1.1027 + /// \brief Copy constructor
1.1028 + BellmanFordWizard(const TR &b) : TR(b) {}
1.1029 +
1.1030 + ~BellmanFordWizard() {}
1.1031 +
1.1032 + /// \brief Runs the Bellman-Ford algorithm from the given source node.
1.1033 + ///
1.1034 + /// This method runs the Bellman-Ford algorithm from the given source
1.1035 + /// node in order to compute the shortest path to each node.
1.1036 + void run(Node s) {
1.1037 + BellmanFord<Digraph,LengthMap,TR>
1.1038 + bf(*reinterpret_cast<const Digraph*>(Base::_graph),
1.1039 + *reinterpret_cast<const LengthMap*>(Base::_length));
1.1040 + if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.1041 + if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.1042 + bf.run(s);
1.1043 + }
1.1044 +
1.1045 + /// \brief Runs the Bellman-Ford algorithm to find the shortest path
1.1046 + /// between \c s and \c t.
1.1047 + ///
1.1048 + /// This method runs the Bellman-Ford algorithm from node \c s
1.1049 + /// in order to compute the shortest path to node \c t.
1.1050 + /// Actually, it computes the shortest path to each node, but using
1.1051 + /// this function you can retrieve the distance and the shortest path
1.1052 + /// for a single target node easier.
1.1053 + ///
1.1054 + /// \return \c true if \c t is reachable form \c s.
1.1055 + bool run(Node s, Node t) {
1.1056 + BellmanFord<Digraph,LengthMap,TR>
1.1057 + bf(*reinterpret_cast<const Digraph*>(Base::_graph),
1.1058 + *reinterpret_cast<const LengthMap*>(Base::_length));
1.1059 + if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.1060 + if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.1061 + bf.run(s);
1.1062 + if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
1.1063 + if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
1.1064 + return bf.reached(t);
1.1065 + }
1.1066 +
1.1067 + template<class T>
1.1068 + struct SetPredMapBase : public Base {
1.1069 + typedef T PredMap;
1.1070 + static PredMap *createPredMap(const Digraph &) { return 0; };
1.1071 + SetPredMapBase(const TR &b) : TR(b) {}
1.1072 + };
1.1073 +
1.1074 + /// \brief \ref named-templ-param "Named parameter" for setting
1.1075 + /// the predecessor map.
1.1076 + ///
1.1077 + /// \ref named-templ-param "Named parameter" for setting
1.1078 + /// the map that stores the predecessor arcs of the nodes.
1.1079 + template<class T>
1.1080 + BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
1.1081 + Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1082 + return BellmanFordWizard<SetPredMapBase<T> >(*this);
1.1083 + }
1.1084 +
1.1085 + template<class T>
1.1086 + struct SetDistMapBase : public Base {
1.1087 + typedef T DistMap;
1.1088 + static DistMap *createDistMap(const Digraph &) { return 0; };
1.1089 + SetDistMapBase(const TR &b) : TR(b) {}
1.1090 + };
1.1091 +
1.1092 + /// \brief \ref named-templ-param "Named parameter" for setting
1.1093 + /// the distance map.
1.1094 + ///
1.1095 + /// \ref named-templ-param "Named parameter" for setting
1.1096 + /// the map that stores the distances of the nodes calculated
1.1097 + /// by the algorithm.
1.1098 + template<class T>
1.1099 + BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
1.1100 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1101 + return BellmanFordWizard<SetDistMapBase<T> >(*this);
1.1102 + }
1.1103 +
1.1104 + template<class T>
1.1105 + struct SetPathBase : public Base {
1.1106 + typedef T Path;
1.1107 + SetPathBase(const TR &b) : TR(b) {}
1.1108 + };
1.1109 +
1.1110 + /// \brief \ref named-func-param "Named parameter" for getting
1.1111 + /// the shortest path to the target node.
1.1112 + ///
1.1113 + /// \ref named-func-param "Named parameter" for getting
1.1114 + /// the shortest path to the target node.
1.1115 + template<class T>
1.1116 + BellmanFordWizard<SetPathBase<T> > path(const T &t)
1.1117 + {
1.1118 + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1119 + return BellmanFordWizard<SetPathBase<T> >(*this);
1.1120 + }
1.1121 +
1.1122 + /// \brief \ref named-func-param "Named parameter" for getting
1.1123 + /// the distance of the target node.
1.1124 + ///
1.1125 + /// \ref named-func-param "Named parameter" for getting
1.1126 + /// the distance of the target node.
1.1127 + BellmanFordWizard dist(const Value &d)
1.1128 + {
1.1129 + Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
1.1130 + return *this;
1.1131 + }
1.1132 +
1.1133 + };
1.1134 +
1.1135 + /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
1.1136 + /// algorithm.
1.1137 + ///
1.1138 + /// \ingroup shortest_path
1.1139 + /// Function type interface for the \ref BellmanFord "Bellman-Ford"
1.1140 + /// algorithm.
1.1141 + ///
1.1142 + /// This function also has several \ref named-templ-func-param
1.1143 + /// "named parameters", they are declared as the members of class
1.1144 + /// \ref BellmanFordWizard.
1.1145 + /// The following examples show how to use these parameters.
1.1146 + /// \code
1.1147 + /// // Compute shortest path from node s to each node
1.1148 + /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
1.1149 + ///
1.1150 + /// // Compute shortest path from s to t
1.1151 + /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
1.1152 + /// \endcode
1.1153 + /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
1.1154 + /// to the end of the parameter list.
1.1155 + /// \sa BellmanFordWizard
1.1156 + /// \sa BellmanFord
1.1157 + template<typename GR, typename LEN>
1.1158 + BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
1.1159 + bellmanFord(const GR& digraph,
1.1160 + const LEN& length)
1.1161 + {
1.1162 + return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
1.1163 + }
1.1164 +
1.1165 +} //END OF NAMESPACE LEMON
1.1166 +
1.1167 +#endif
1.1168 +