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