alpar@877: /* -*- mode: C++; indent-tabs-mode: nil; -*- kpeter@696: * alpar@877: * This file is a part of LEMON, a generic C++ optimization library. kpeter@696: * alpar@877: * Copyright (C) 2003-2010 kpeter@696: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@696: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@696: * kpeter@696: * Permission to use, modify and distribute this software is granted kpeter@696: * provided that this copyright notice appears in all copies. For kpeter@696: * precise terms see the accompanying LICENSE file. kpeter@696: * kpeter@696: * This software is provided "AS IS" with no warranty of any kind, kpeter@696: * express or implied, and with no claim as to its suitability for any kpeter@696: * purpose. kpeter@696: * kpeter@696: */ kpeter@696: kpeter@697: #ifndef LEMON_BELLMAN_FORD_H kpeter@697: #define LEMON_BELLMAN_FORD_H kpeter@696: kpeter@696: /// \ingroup shortest_path kpeter@696: /// \file kpeter@696: /// \brief Bellman-Ford algorithm. kpeter@696: kpeter@781: #include kpeter@696: #include kpeter@696: #include kpeter@696: #include kpeter@696: #include kpeter@697: #include kpeter@696: kpeter@696: #include kpeter@696: kpeter@696: namespace lemon { kpeter@696: alpar@878: /// \brief Default OperationTraits for the BellmanFord algorithm class. alpar@877: /// kpeter@697: /// This operation traits class defines all computational operations kpeter@697: /// and constants that are used in the Bellman-Ford algorithm. kpeter@697: /// The default implementation is based on the \c numeric_limits class. kpeter@697: /// If the numeric type does not have infinity value, then the maximum kpeter@697: /// value is used as extremal infinity value. kpeter@696: template < alpar@877: typename V, kpeter@697: bool has_inf = std::numeric_limits::has_infinity> kpeter@696: struct BellmanFordDefaultOperationTraits { alpar@878: /// \e kpeter@697: typedef V Value; kpeter@696: /// \brief Gives back the zero value of the type. kpeter@696: static Value zero() { kpeter@696: return static_cast(0); kpeter@696: } kpeter@696: /// \brief Gives back the positive infinity value of the type. kpeter@696: static Value infinity() { kpeter@696: return std::numeric_limits::infinity(); kpeter@696: } kpeter@696: /// \brief Gives back the sum of the given two elements. kpeter@696: static Value plus(const Value& left, const Value& right) { kpeter@696: return left + right; kpeter@696: } kpeter@697: /// \brief Gives back \c true only if the first value is less than kpeter@697: /// the second. kpeter@696: static bool less(const Value& left, const Value& right) { kpeter@696: return left < right; kpeter@696: } kpeter@696: }; kpeter@696: kpeter@697: template kpeter@697: struct BellmanFordDefaultOperationTraits { kpeter@697: typedef V Value; kpeter@696: static Value zero() { kpeter@696: return static_cast(0); kpeter@696: } kpeter@696: static Value infinity() { kpeter@696: return std::numeric_limits::max(); kpeter@696: } kpeter@696: static Value plus(const Value& left, const Value& right) { kpeter@696: if (left == infinity() || right == infinity()) return infinity(); kpeter@696: return left + right; kpeter@696: } kpeter@696: static bool less(const Value& left, const Value& right) { kpeter@696: return left < right; kpeter@696: } kpeter@696: }; alpar@877: kpeter@696: /// \brief Default traits class of BellmanFord class. kpeter@696: /// kpeter@696: /// Default traits class of BellmanFord class. kpeter@697: /// \param GR The type of the digraph. kpeter@697: /// \param LEN The type of the length map. kpeter@697: template kpeter@696: struct BellmanFordDefaultTraits { alpar@877: /// The type of the digraph the algorithm runs on. kpeter@697: typedef GR Digraph; kpeter@696: kpeter@696: /// \brief The type of the map that stores the arc lengths. kpeter@696: /// kpeter@696: /// The type of the map that stores the arc lengths. kpeter@697: /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. kpeter@697: typedef LEN LengthMap; kpeter@696: kpeter@697: /// The type of the arc lengths. kpeter@697: typedef typename LEN::Value Value; kpeter@696: kpeter@696: /// \brief Operation traits for Bellman-Ford algorithm. kpeter@696: /// kpeter@697: /// It defines the used operations and the infinity value for the kpeter@697: /// given \c Value type. alpar@878: /// \see BellmanFordDefaultOperationTraits kpeter@696: typedef BellmanFordDefaultOperationTraits OperationTraits; alpar@877: alpar@877: /// \brief The type of the map that stores the last arcs of the kpeter@696: /// shortest paths. alpar@877: /// kpeter@696: /// The type of the map that stores the last kpeter@696: /// arcs of the shortest paths. kpeter@697: /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@697: typedef typename GR::template NodeMap PredMap; kpeter@696: kpeter@697: /// \brief Instantiates a \c PredMap. alpar@877: /// alpar@877: /// This function instantiates a \ref PredMap. kpeter@697: /// \param g is the digraph to which we would like to define the kpeter@697: /// \ref PredMap. kpeter@697: static PredMap *createPredMap(const GR& g) { kpeter@697: return new PredMap(g); kpeter@696: } kpeter@696: kpeter@697: /// \brief The type of the map that stores the distances of the nodes. kpeter@696: /// kpeter@697: /// The type of the map that stores the distances of the nodes. kpeter@697: /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@697: typedef typename GR::template NodeMap DistMap; kpeter@696: kpeter@697: /// \brief Instantiates a \c DistMap. kpeter@696: /// alpar@877: /// This function instantiates a \ref DistMap. alpar@877: /// \param g is the digraph to which we would like to define the kpeter@697: /// \ref DistMap. kpeter@697: static DistMap *createDistMap(const GR& g) { kpeter@697: return new DistMap(g); kpeter@696: } kpeter@696: kpeter@696: }; alpar@877: kpeter@696: /// \brief %BellmanFord algorithm class. kpeter@696: /// kpeter@696: /// \ingroup shortest_path alpar@877: /// This class provides an efficient implementation of the Bellman-Ford kpeter@697: /// algorithm. The maximum time complexity of the algorithm is kpeter@1080: /// O(nm). kpeter@697: /// kpeter@697: /// The Bellman-Ford algorithm solves the single-source shortest path kpeter@697: /// problem when the arcs can have negative lengths, but the digraph kpeter@697: /// should not contain directed cycles with negative total length. kpeter@697: /// If all arc costs are non-negative, consider to use the Dijkstra kpeter@697: /// algorithm instead, since it is more efficient. kpeter@697: /// kpeter@697: /// The arc lengths are passed to the algorithm using a alpar@877: /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any kpeter@697: /// kind of length. The type of the length values is determined by the kpeter@697: /// \ref concepts::ReadMap::Value "Value" type of the length map. kpeter@696: /// kpeter@697: /// There is also a \ref bellmanFord() "function-type interface" for the kpeter@697: /// Bellman-Ford algorithm, which is convenient in the simplier cases and kpeter@697: /// it can be used easier. kpeter@696: /// kpeter@697: /// \tparam GR The type of the digraph the algorithm runs on. kpeter@697: /// The default type is \ref ListDigraph. kpeter@697: /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies kpeter@697: /// the lengths of the arcs. The default map type is kpeter@697: /// \ref concepts::Digraph::ArcMap "GR::ArcMap". kpeter@825: /// \tparam TR The traits class that defines various types used by the kpeter@825: /// algorithm. By default, it is \ref BellmanFordDefaultTraits kpeter@825: /// "BellmanFordDefaultTraits". kpeter@825: /// In most cases, this parameter should not be set directly, kpeter@825: /// consider to use the named template parameters instead. kpeter@696: #ifdef DOXYGEN kpeter@697: template kpeter@696: #else kpeter@697: template , kpeter@697: typename TR=BellmanFordDefaultTraits > kpeter@696: #endif kpeter@696: class BellmanFord { kpeter@696: public: kpeter@696: kpeter@696: ///The type of the underlying digraph. kpeter@697: typedef typename TR::Digraph Digraph; alpar@877: kpeter@697: /// \brief The type of the arc lengths. kpeter@697: typedef typename TR::LengthMap::Value Value; kpeter@697: /// \brief The type of the map that stores the arc lengths. kpeter@697: typedef typename TR::LengthMap LengthMap; kpeter@697: /// \brief The type of the map that stores the last kpeter@697: /// arcs of the shortest paths. kpeter@697: typedef typename TR::PredMap PredMap; kpeter@697: /// \brief The type of the map that stores the distances of the nodes. kpeter@697: typedef typename TR::DistMap DistMap; kpeter@697: /// The type of the paths. kpeter@697: typedef PredMapPath Path; alpar@1074: ///\brief The \ref lemon::BellmanFordDefaultOperationTraits kpeter@697: /// "operation traits class" of the algorithm. kpeter@697: typedef typename TR::OperationTraits OperationTraits; kpeter@697: alpar@1074: ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class" alpar@1074: ///of the algorithm. kpeter@697: typedef TR Traits; kpeter@697: kpeter@697: private: kpeter@696: kpeter@696: typedef typename Digraph::Node Node; kpeter@696: typedef typename Digraph::NodeIt NodeIt; kpeter@696: typedef typename Digraph::Arc Arc; kpeter@696: typedef typename Digraph::OutArcIt OutArcIt; kpeter@697: kpeter@697: // Pointer to the underlying digraph. kpeter@697: const Digraph *_gr; kpeter@697: // Pointer to the length map kpeter@697: const LengthMap *_length; kpeter@697: // Pointer to the map of predecessors arcs. kpeter@696: PredMap *_pred; kpeter@697: // Indicates if _pred is locally allocated (true) or not. kpeter@697: bool _local_pred; kpeter@697: // Pointer to the map of distances. kpeter@696: DistMap *_dist; kpeter@697: // Indicates if _dist is locally allocated (true) or not. kpeter@697: bool _local_dist; kpeter@696: kpeter@696: typedef typename Digraph::template NodeMap MaskMap; kpeter@696: MaskMap *_mask; kpeter@696: kpeter@696: std::vector _process; kpeter@696: kpeter@697: // Creates the maps if necessary. kpeter@696: void create_maps() { kpeter@696: if(!_pred) { alpar@877: _local_pred = true; alpar@877: _pred = Traits::createPredMap(*_gr); kpeter@696: } kpeter@696: if(!_dist) { alpar@877: _local_dist = true; alpar@877: _dist = Traits::createDistMap(*_gr); kpeter@696: } kpeter@804: if(!_mask) { kpeter@804: _mask = new MaskMap(*_gr); kpeter@804: } kpeter@696: } alpar@877: kpeter@696: public : alpar@877: kpeter@696: typedef BellmanFord Create; kpeter@696: kpeter@697: /// \name Named Template Parameters kpeter@696: kpeter@696: ///@{ kpeter@696: kpeter@696: template kpeter@697: struct SetPredMapTraits : public Traits { kpeter@696: typedef T PredMap; kpeter@696: static PredMap *createPredMap(const Digraph&) { kpeter@696: LEMON_ASSERT(false, "PredMap is not initialized"); kpeter@696: return 0; // ignore warnings kpeter@696: } kpeter@696: }; kpeter@696: kpeter@697: /// \brief \ref named-templ-param "Named parameter" for setting kpeter@697: /// \c PredMap type. kpeter@696: /// kpeter@697: /// \ref named-templ-param "Named parameter" for setting kpeter@697: /// \c PredMap type. kpeter@697: /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@696: template alpar@877: struct SetPredMap kpeter@697: : public BellmanFord< Digraph, LengthMap, SetPredMapTraits > { kpeter@697: typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create; kpeter@696: }; alpar@877: kpeter@696: template kpeter@697: struct SetDistMapTraits : public Traits { kpeter@696: typedef T DistMap; kpeter@696: static DistMap *createDistMap(const Digraph&) { kpeter@696: LEMON_ASSERT(false, "DistMap is not initialized"); kpeter@696: return 0; // ignore warnings kpeter@696: } kpeter@696: }; kpeter@696: kpeter@697: /// \brief \ref named-templ-param "Named parameter" for setting kpeter@697: /// \c DistMap type. kpeter@696: /// kpeter@697: /// \ref named-templ-param "Named parameter" for setting kpeter@697: /// \c DistMap type. kpeter@697: /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@696: template alpar@877: struct SetDistMap kpeter@697: : public BellmanFord< Digraph, LengthMap, SetDistMapTraits > { kpeter@697: typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create; kpeter@696: }; kpeter@697: kpeter@696: template kpeter@697: struct SetOperationTraitsTraits : public Traits { kpeter@696: typedef T OperationTraits; kpeter@696: }; alpar@877: alpar@877: /// \brief \ref named-templ-param "Named parameter" for setting kpeter@697: /// \c OperationTraits type. kpeter@696: /// kpeter@697: /// \ref named-templ-param "Named parameter" for setting kpeter@697: /// \c OperationTraits type. kpeter@786: /// For more information, see \ref BellmanFordDefaultOperationTraits. kpeter@696: template kpeter@696: struct SetOperationTraits kpeter@697: : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > { kpeter@697: typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > kpeter@696: Create; kpeter@696: }; alpar@877: kpeter@696: ///@} kpeter@696: kpeter@696: protected: alpar@877: kpeter@696: BellmanFord() {} kpeter@696: alpar@877: public: alpar@877: kpeter@696: /// \brief Constructor. kpeter@696: /// kpeter@697: /// Constructor. kpeter@697: /// \param g The digraph the algorithm runs on. kpeter@697: /// \param length The length map used by the algorithm. kpeter@697: BellmanFord(const Digraph& g, const LengthMap& length) : kpeter@697: _gr(&g), _length(&length), kpeter@697: _pred(0), _local_pred(false), kpeter@697: _dist(0), _local_dist(false), _mask(0) {} alpar@877: kpeter@696: ///Destructor. kpeter@696: ~BellmanFord() { kpeter@697: if(_local_pred) delete _pred; kpeter@697: if(_local_dist) delete _dist; kpeter@696: if(_mask) delete _mask; kpeter@696: } kpeter@696: kpeter@696: /// \brief Sets the length map. kpeter@696: /// kpeter@696: /// Sets the length map. kpeter@697: /// \return (*this) kpeter@697: BellmanFord &lengthMap(const LengthMap &map) { kpeter@697: _length = ↦ kpeter@696: return *this; kpeter@696: } kpeter@696: kpeter@697: /// \brief Sets the map that stores the predecessor arcs. kpeter@696: /// kpeter@697: /// Sets the map that stores the predecessor arcs. kpeter@697: /// If you don't use this function before calling \ref run() kpeter@697: /// or \ref init(), an instance will be allocated automatically. kpeter@697: /// The destructor deallocates this automatically allocated map, kpeter@697: /// of course. kpeter@697: /// \return (*this) kpeter@697: BellmanFord &predMap(PredMap &map) { kpeter@697: if(_local_pred) { alpar@877: delete _pred; alpar@877: _local_pred=false; kpeter@696: } kpeter@697: _pred = ↦ kpeter@696: return *this; kpeter@696: } kpeter@696: kpeter@697: /// \brief Sets the map that stores the distances of the nodes. kpeter@696: /// kpeter@697: /// Sets the map that stores the distances of the nodes calculated kpeter@697: /// by the algorithm. kpeter@697: /// If you don't use this function before calling \ref run() kpeter@697: /// or \ref init(), an instance will be allocated automatically. kpeter@697: /// The destructor deallocates this automatically allocated map, kpeter@697: /// of course. kpeter@697: /// \return (*this) kpeter@697: BellmanFord &distMap(DistMap &map) { kpeter@697: if(_local_dist) { alpar@877: delete _dist; alpar@877: _local_dist=false; kpeter@696: } kpeter@697: _dist = ↦ kpeter@696: return *this; kpeter@696: } kpeter@696: kpeter@697: /// \name Execution Control kpeter@697: /// The simplest way to execute the Bellman-Ford algorithm is to use kpeter@697: /// one of the member functions called \ref run().\n kpeter@697: /// If you need better control on the execution, you have to call kpeter@697: /// \ref init() first, then you can add several source nodes kpeter@697: /// with \ref addSource(). Finally the actual path computation can be kpeter@697: /// performed with \ref start(), \ref checkedStart() or kpeter@697: /// \ref limitedStart(). kpeter@696: kpeter@696: ///@{ kpeter@696: kpeter@696: /// \brief Initializes the internal data structures. alpar@877: /// kpeter@697: /// Initializes the internal data structures. The optional parameter kpeter@697: /// is the initial distance of each node. kpeter@696: void init(const Value value = OperationTraits::infinity()) { kpeter@696: create_maps(); kpeter@697: for (NodeIt it(*_gr); it != INVALID; ++it) { alpar@877: _pred->set(it, INVALID); alpar@877: _dist->set(it, value); kpeter@696: } kpeter@696: _process.clear(); kpeter@696: if (OperationTraits::less(value, OperationTraits::infinity())) { alpar@877: for (NodeIt it(*_gr); it != INVALID; ++it) { alpar@877: _process.push_back(it); alpar@877: _mask->set(it, true); alpar@877: } kpeter@804: } else { alpar@877: for (NodeIt it(*_gr); it != INVALID; ++it) { alpar@877: _mask->set(it, false); alpar@877: } kpeter@696: } kpeter@696: } alpar@877: kpeter@696: /// \brief Adds a new source node. kpeter@696: /// kpeter@697: /// This function adds a new source node. The optional second parameter kpeter@697: /// is the initial distance of the node. kpeter@696: void addSource(Node source, Value dst = OperationTraits::zero()) { kpeter@696: _dist->set(source, dst); kpeter@696: if (!(*_mask)[source]) { alpar@877: _process.push_back(source); alpar@877: _mask->set(source, true); kpeter@696: } kpeter@696: } kpeter@696: kpeter@696: /// \brief Executes one round from the Bellman-Ford algorithm. kpeter@696: /// kpeter@696: /// If the algoritm calculated the distances in the previous round kpeter@697: /// exactly for the paths of at most \c k arcs, then this function kpeter@697: /// will calculate the distances exactly for the paths of at most kpeter@697: /// k+1 arcs. Performing \c k iterations using this function kpeter@697: /// calculates the shortest path distances exactly for the paths kpeter@697: /// consisting of at most \c k arcs. kpeter@696: /// kpeter@696: /// \warning The paths with limited arc number cannot be retrieved kpeter@697: /// easily with \ref path() or \ref predArc() functions. If you also kpeter@697: /// need the shortest paths and not only the distances, you should kpeter@697: /// store the \ref predMap() "predecessor map" after each iteration kpeter@697: /// and build the path manually. kpeter@696: /// kpeter@696: /// \return \c true when the algorithm have not found more shorter kpeter@696: /// paths. kpeter@697: /// kpeter@697: /// \see ActiveIt kpeter@696: bool processNextRound() { kpeter@696: for (int i = 0; i < int(_process.size()); ++i) { alpar@877: _mask->set(_process[i], false); kpeter@696: } kpeter@696: std::vector nextProcess; kpeter@696: std::vector values(_process.size()); kpeter@696: for (int i = 0; i < int(_process.size()); ++i) { alpar@877: values[i] = (*_dist)[_process[i]]; kpeter@696: } kpeter@696: for (int i = 0; i < int(_process.size()); ++i) { alpar@877: for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { alpar@877: Node target = _gr->target(it); alpar@877: Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); alpar@877: if (OperationTraits::less(relaxed, (*_dist)[target])) { alpar@877: _pred->set(target, it); alpar@877: _dist->set(target, relaxed); alpar@877: if (!(*_mask)[target]) { alpar@877: _mask->set(target, true); alpar@877: nextProcess.push_back(target); alpar@877: } alpar@877: } alpar@877: } kpeter@696: } kpeter@696: _process.swap(nextProcess); kpeter@696: return _process.empty(); kpeter@696: } kpeter@696: kpeter@696: /// \brief Executes one weak round from the Bellman-Ford algorithm. kpeter@696: /// kpeter@697: /// If the algorithm calculated the distances in the previous round kpeter@697: /// at least for the paths of at most \c k arcs, then this function kpeter@697: /// will calculate the distances at least for the paths of at most kpeter@697: /// k+1 arcs. kpeter@697: /// This function does not make it possible to calculate the shortest kpeter@697: /// path distances exactly for paths consisting of at most \c k arcs, kpeter@697: /// this is why it is called weak round. kpeter@697: /// kpeter@697: /// \return \c true when the algorithm have not found more shorter kpeter@697: /// paths. kpeter@697: /// kpeter@697: /// \see ActiveIt kpeter@696: bool processNextWeakRound() { kpeter@696: for (int i = 0; i < int(_process.size()); ++i) { alpar@877: _mask->set(_process[i], false); kpeter@696: } kpeter@696: std::vector nextProcess; kpeter@696: for (int i = 0; i < int(_process.size()); ++i) { alpar@877: for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { alpar@877: Node target = _gr->target(it); alpar@877: Value relaxed = alpar@877: OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); alpar@877: if (OperationTraits::less(relaxed, (*_dist)[target])) { alpar@877: _pred->set(target, it); alpar@877: _dist->set(target, relaxed); alpar@877: if (!(*_mask)[target]) { alpar@877: _mask->set(target, true); alpar@877: nextProcess.push_back(target); alpar@877: } alpar@877: } alpar@877: } kpeter@696: } kpeter@696: _process.swap(nextProcess); kpeter@696: return _process.empty(); kpeter@696: } kpeter@696: kpeter@696: /// \brief Executes the algorithm. kpeter@696: /// kpeter@697: /// Executes the algorithm. kpeter@696: /// kpeter@697: /// This method runs the Bellman-Ford algorithm from the root node(s) kpeter@697: /// in order to compute the shortest path to each node. kpeter@697: /// kpeter@697: /// The algorithm computes kpeter@697: /// - the shortest path tree (forest), kpeter@697: /// - the distance of each node from the root(s). kpeter@697: /// kpeter@697: /// \pre init() must be called and at least one root node should be kpeter@697: /// added with addSource() before using this function. kpeter@696: void start() { kpeter@697: int num = countNodes(*_gr) - 1; kpeter@696: for (int i = 0; i < num; ++i) { alpar@877: if (processNextWeakRound()) break; kpeter@696: } kpeter@696: } kpeter@696: kpeter@696: /// \brief Executes the algorithm and checks the negative cycles. kpeter@696: /// kpeter@697: /// Executes the algorithm and checks the negative cycles. kpeter@696: /// kpeter@697: /// This method runs the Bellman-Ford algorithm from the root node(s) kpeter@697: /// in order to compute the shortest path to each node and also checks kpeter@697: /// if the digraph contains cycles with negative total length. kpeter@697: /// alpar@877: /// The algorithm computes kpeter@697: /// - the shortest path tree (forest), kpeter@697: /// - the distance of each node from the root(s). alpar@877: /// kpeter@696: /// \return \c false if there is a negative cycle in the digraph. kpeter@697: /// kpeter@697: /// \pre init() must be called and at least one root node should be alpar@877: /// added with addSource() before using this function. kpeter@696: bool checkedStart() { kpeter@697: int num = countNodes(*_gr); kpeter@696: for (int i = 0; i < num; ++i) { alpar@877: if (processNextWeakRound()) return true; kpeter@696: } kpeter@696: return _process.empty(); kpeter@696: } kpeter@696: kpeter@697: /// \brief Executes the algorithm with arc number limit. kpeter@696: /// kpeter@697: /// Executes the algorithm with arc number limit. kpeter@696: /// kpeter@697: /// This method runs the Bellman-Ford algorithm from the root node(s) kpeter@697: /// in order to compute the shortest path distance for each node kpeter@697: /// using only the paths consisting of at most \c num arcs. kpeter@697: /// kpeter@697: /// The algorithm computes kpeter@697: /// - the limited distance of each node from the root(s), kpeter@697: /// - the predecessor arc for each node. kpeter@696: /// kpeter@696: /// \warning The paths with limited arc number cannot be retrieved kpeter@697: /// easily with \ref path() or \ref predArc() functions. If you also kpeter@697: /// need the shortest paths and not only the distances, you should kpeter@697: /// store the \ref predMap() "predecessor map" after each iteration kpeter@697: /// and build the path manually. kpeter@696: /// kpeter@697: /// \pre init() must be called and at least one root node should be alpar@877: /// added with addSource() before using this function. kpeter@696: void limitedStart(int num) { kpeter@696: for (int i = 0; i < num; ++i) { alpar@877: if (processNextRound()) break; kpeter@696: } kpeter@696: } alpar@877: kpeter@697: /// \brief Runs the algorithm from the given root node. alpar@877: /// kpeter@697: /// This method runs the Bellman-Ford algorithm from the given root kpeter@697: /// node \c s in order to compute the shortest path to each node. kpeter@696: /// kpeter@697: /// The algorithm computes kpeter@697: /// - the shortest path tree (forest), kpeter@697: /// - the distance of each node from the root(s). kpeter@697: /// kpeter@697: /// \note bf.run(s) is just a shortcut of the following code. kpeter@697: /// \code kpeter@697: /// bf.init(); kpeter@697: /// bf.addSource(s); kpeter@697: /// bf.start(); kpeter@697: /// \endcode kpeter@696: void run(Node s) { kpeter@696: init(); kpeter@696: addSource(s); kpeter@696: start(); kpeter@696: } alpar@877: kpeter@697: /// \brief Runs the algorithm from the given root node with arc kpeter@697: /// number limit. alpar@877: /// kpeter@697: /// This method runs the Bellman-Ford algorithm from the given root kpeter@697: /// node \c s in order to compute the shortest path distance for each kpeter@697: /// node using only the paths consisting of at most \c num arcs. kpeter@696: /// kpeter@697: /// The algorithm computes kpeter@697: /// - the limited distance of each node from the root(s), kpeter@697: /// - the predecessor arc for each node. kpeter@697: /// kpeter@697: /// \warning The paths with limited arc number cannot be retrieved kpeter@697: /// easily with \ref path() or \ref predArc() functions. If you also kpeter@697: /// need the shortest paths and not only the distances, you should kpeter@697: /// store the \ref predMap() "predecessor map" after each iteration kpeter@697: /// and build the path manually. kpeter@697: /// kpeter@697: /// \note bf.run(s, num) is just a shortcut of the following code. kpeter@697: /// \code kpeter@697: /// bf.init(); kpeter@697: /// bf.addSource(s); kpeter@697: /// bf.limitedStart(num); kpeter@697: /// \endcode kpeter@696: void run(Node s, int num) { kpeter@696: init(); kpeter@696: addSource(s); kpeter@696: limitedStart(num); kpeter@696: } alpar@877: kpeter@696: ///@} kpeter@696: kpeter@697: /// \brief LEMON iterator for getting the active nodes. kpeter@696: /// kpeter@697: /// This class provides a common style LEMON iterator that traverses kpeter@697: /// the active nodes of the Bellman-Ford algorithm after the last kpeter@697: /// phase. These nodes should be checked in the next phase to kpeter@697: /// find augmenting arcs outgoing from them. kpeter@696: class ActiveIt { kpeter@696: public: kpeter@696: kpeter@696: /// \brief Constructor. kpeter@696: /// kpeter@697: /// Constructor for getting the active nodes of the given BellmanFord alpar@877: /// instance. kpeter@696: ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) kpeter@696: { kpeter@696: _index = _algorithm->_process.size() - 1; kpeter@696: } kpeter@696: kpeter@696: /// \brief Invalid constructor. kpeter@696: /// kpeter@696: /// Invalid constructor. kpeter@696: ActiveIt(Invalid) : _algorithm(0), _index(-1) {} kpeter@696: kpeter@697: /// \brief Conversion to \c Node. kpeter@696: /// kpeter@697: /// Conversion to \c Node. alpar@877: operator Node() const { kpeter@696: return _index >= 0 ? _algorithm->_process[_index] : INVALID; kpeter@696: } kpeter@696: kpeter@696: /// \brief Increment operator. kpeter@696: /// kpeter@696: /// Increment operator. kpeter@696: ActiveIt& operator++() { kpeter@696: --_index; alpar@877: return *this; kpeter@696: } kpeter@696: alpar@877: bool operator==(const ActiveIt& it) const { alpar@877: return static_cast(*this) == static_cast(it); kpeter@696: } alpar@877: bool operator!=(const ActiveIt& it) const { alpar@877: return static_cast(*this) != static_cast(it); kpeter@696: } alpar@877: bool operator<(const ActiveIt& it) const { alpar@877: return static_cast(*this) < static_cast(it); kpeter@696: } alpar@877: kpeter@696: private: kpeter@696: const BellmanFord* _algorithm; kpeter@696: int _index; kpeter@696: }; alpar@877: kpeter@697: /// \name Query Functions kpeter@697: /// The result of the Bellman-Ford algorithm can be obtained using these kpeter@697: /// functions.\n kpeter@697: /// Either \ref run() or \ref init() should be called before using them. alpar@877: kpeter@697: ///@{ kpeter@696: kpeter@697: /// \brief The shortest path to the given node. alpar@877: /// kpeter@697: /// Gives back the shortest path to the given node from the root(s). kpeter@697: /// kpeter@697: /// \warning \c t should be reached from the root(s). kpeter@697: /// kpeter@697: /// \pre Either \ref run() or \ref init() must be called before kpeter@697: /// using this function. kpeter@697: Path path(Node t) const kpeter@697: { kpeter@697: return Path(*_gr, *_pred, t); kpeter@697: } alpar@877: kpeter@697: /// \brief The distance of the given node from the root(s). kpeter@697: /// kpeter@697: /// Returns the distance of the given node from the root(s). kpeter@697: /// kpeter@697: /// \warning If node \c v is not reached from the root(s), then kpeter@697: /// the return value of this function is undefined. kpeter@697: /// kpeter@697: /// \pre Either \ref run() or \ref init() must be called before kpeter@697: /// using this function. kpeter@697: Value dist(Node v) const { return (*_dist)[v]; } kpeter@696: kpeter@697: /// \brief Returns the 'previous arc' of the shortest path tree for kpeter@697: /// the given node. kpeter@697: /// kpeter@697: /// This function returns the 'previous arc' of the shortest path kpeter@697: /// tree for node \c v, i.e. it returns the last arc of a kpeter@697: /// shortest path from a root to \c v. It is \c INVALID if \c v kpeter@697: /// is not reached from the root(s) or if \c v is a root. kpeter@697: /// kpeter@697: /// The shortest path tree used here is equal to the shortest path kpeter@786: /// tree used in \ref predNode() and \ref predMap(). kpeter@697: /// kpeter@697: /// \pre Either \ref run() or \ref init() must be called before kpeter@697: /// using this function. kpeter@697: Arc predArc(Node v) const { return (*_pred)[v]; } kpeter@697: kpeter@697: /// \brief Returns the 'previous node' of the shortest path tree for kpeter@697: /// the given node. kpeter@697: /// kpeter@697: /// This function returns the 'previous node' of the shortest path kpeter@697: /// tree for node \c v, i.e. it returns the last but one node of kpeter@697: /// a shortest path from a root to \c v. It is \c INVALID if \c v kpeter@697: /// is not reached from the root(s) or if \c v is a root. kpeter@697: /// kpeter@697: /// The shortest path tree used here is equal to the shortest path kpeter@786: /// tree used in \ref predArc() and \ref predMap(). kpeter@697: /// kpeter@697: /// \pre Either \ref run() or \ref init() must be called before kpeter@697: /// using this function. alpar@877: Node predNode(Node v) const { alpar@877: return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); kpeter@697: } alpar@877: kpeter@697: /// \brief Returns a const reference to the node map that stores the kpeter@697: /// distances of the nodes. kpeter@697: /// kpeter@697: /// Returns a const reference to the node map that stores the distances kpeter@697: /// of the nodes calculated by the algorithm. kpeter@697: /// kpeter@697: /// \pre Either \ref run() or \ref init() must be called before kpeter@697: /// using this function. kpeter@697: const DistMap &distMap() const { return *_dist;} alpar@877: kpeter@697: /// \brief Returns a const reference to the node map that stores the kpeter@697: /// predecessor arcs. kpeter@697: /// kpeter@697: /// Returns a const reference to the node map that stores the predecessor kpeter@697: /// arcs, which form the shortest path tree (forest). kpeter@697: /// kpeter@697: /// \pre Either \ref run() or \ref init() must be called before kpeter@697: /// using this function. kpeter@697: const PredMap &predMap() const { return *_pred; } alpar@877: kpeter@697: /// \brief Checks if a node is reached from the root(s). kpeter@697: /// kpeter@697: /// Returns \c true if \c v is reached from the root(s). kpeter@697: /// kpeter@697: /// \pre Either \ref run() or \ref init() must be called before kpeter@697: /// using this function. kpeter@697: bool reached(Node v) const { kpeter@697: return (*_dist)[v] != OperationTraits::infinity(); kpeter@696: } kpeter@696: kpeter@699: /// \brief Gives back a negative cycle. alpar@877: /// kpeter@699: /// This function gives back a directed cycle with negative total kpeter@699: /// length if the algorithm has already found one. kpeter@699: /// Otherwise it gives back an empty path. kpeter@781: lemon::Path negativeCycle() const { kpeter@699: typename Digraph::template NodeMap state(*_gr, -1); kpeter@699: lemon::Path cycle; kpeter@699: for (int i = 0; i < int(_process.size()); ++i) { kpeter@699: if (state[_process[i]] != -1) continue; kpeter@699: for (Node v = _process[i]; (*_pred)[v] != INVALID; kpeter@699: v = _gr->source((*_pred)[v])) { kpeter@699: if (state[v] == i) { kpeter@699: cycle.addFront((*_pred)[v]); kpeter@699: for (Node u = _gr->source((*_pred)[v]); u != v; kpeter@699: u = _gr->source((*_pred)[u])) { kpeter@699: cycle.addFront((*_pred)[u]); kpeter@699: } kpeter@699: return cycle; kpeter@699: } kpeter@699: else if (state[v] >= 0) { kpeter@699: break; kpeter@699: } kpeter@699: state[v] = i; kpeter@699: } kpeter@699: } kpeter@699: return cycle; kpeter@699: } alpar@877: kpeter@696: ///@} kpeter@696: }; alpar@877: kpeter@697: /// \brief Default traits class of bellmanFord() function. kpeter@696: /// kpeter@697: /// Default traits class of bellmanFord() function. kpeter@697: /// \tparam GR The type of the digraph. kpeter@697: /// \tparam LEN The type of the length map. kpeter@697: template kpeter@696: struct BellmanFordWizardDefaultTraits { alpar@877: /// The type of the digraph the algorithm runs on. kpeter@697: typedef GR Digraph; kpeter@696: kpeter@696: /// \brief The type of the map that stores the arc lengths. kpeter@696: /// kpeter@696: /// The type of the map that stores the arc lengths. kpeter@696: /// It must meet the \ref concepts::ReadMap "ReadMap" concept. kpeter@697: typedef LEN LengthMap; kpeter@696: kpeter@697: /// The type of the arc lengths. kpeter@697: typedef typename LEN::Value Value; kpeter@696: kpeter@696: /// \brief Operation traits for Bellman-Ford algorithm. kpeter@696: /// kpeter@697: /// It defines the used operations and the infinity value for the kpeter@697: /// given \c Value type. alpar@878: /// \see BellmanFordDefaultOperationTraits kpeter@696: typedef BellmanFordDefaultOperationTraits OperationTraits; kpeter@696: kpeter@696: /// \brief The type of the map that stores the last kpeter@696: /// arcs of the shortest paths. alpar@877: /// kpeter@697: /// The type of the map that stores the last arcs of the shortest paths. kpeter@697: /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@697: typedef typename GR::template NodeMap PredMap; kpeter@696: kpeter@697: /// \brief Instantiates a \c PredMap. alpar@877: /// kpeter@697: /// This function instantiates a \ref PredMap. kpeter@697: /// \param g is the digraph to which we would like to define the kpeter@697: /// \ref PredMap. kpeter@697: static PredMap *createPredMap(const GR &g) { kpeter@697: return new PredMap(g); kpeter@696: } kpeter@697: kpeter@697: /// \brief The type of the map that stores the distances of the nodes. kpeter@696: /// kpeter@697: /// The type of the map that stores the distances of the nodes. kpeter@697: /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@697: typedef typename GR::template NodeMap DistMap; kpeter@697: kpeter@697: /// \brief Instantiates a \c DistMap. kpeter@696: /// alpar@877: /// This function instantiates a \ref DistMap. kpeter@697: /// \param g is the digraph to which we would like to define the kpeter@697: /// \ref DistMap. kpeter@697: static DistMap *createDistMap(const GR &g) { kpeter@697: return new DistMap(g); kpeter@696: } kpeter@697: kpeter@697: ///The type of the shortest paths. kpeter@697: kpeter@697: ///The type of the shortest paths. kpeter@697: ///It must meet the \ref concepts::Path "Path" concept. kpeter@697: typedef lemon::Path Path; kpeter@696: }; alpar@877: kpeter@697: /// \brief Default traits class used by BellmanFordWizard. kpeter@696: /// kpeter@697: /// Default traits class used by BellmanFordWizard. kpeter@697: /// \tparam GR The type of the digraph. kpeter@697: /// \tparam LEN The type of the length map. kpeter@697: template alpar@877: class BellmanFordWizardBase kpeter@697: : public BellmanFordWizardDefaultTraits { kpeter@696: kpeter@697: typedef BellmanFordWizardDefaultTraits Base; kpeter@696: protected: kpeter@697: // Type of the nodes in the digraph. kpeter@696: typedef typename Base::Digraph::Node Node; kpeter@696: kpeter@697: // Pointer to the underlying digraph. kpeter@696: void *_graph; kpeter@697: // Pointer to the length map kpeter@696: void *_length; kpeter@697: // Pointer to the map of predecessors arcs. kpeter@696: void *_pred; kpeter@697: // Pointer to the map of distances. kpeter@696: void *_dist; kpeter@697: //Pointer to the shortest path to the target node. kpeter@697: void *_path; kpeter@697: //Pointer to the distance of the target node. kpeter@697: void *_di; kpeter@696: kpeter@696: public: kpeter@696: /// Constructor. alpar@877: kpeter@697: /// This constructor does not require parameters, it initiates kpeter@697: /// all of the attributes to default values \c 0. kpeter@697: BellmanFordWizardBase() : kpeter@697: _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {} kpeter@696: kpeter@696: /// Constructor. alpar@877: kpeter@697: /// This constructor requires two parameters, kpeter@697: /// others are initiated to \c 0. kpeter@697: /// \param gr The digraph the algorithm runs on. kpeter@697: /// \param len The length map. alpar@877: BellmanFordWizardBase(const GR& gr, alpar@877: const LEN& len) : alpar@877: _graph(reinterpret_cast(const_cast(&gr))), alpar@877: _length(reinterpret_cast(const_cast(&len))), kpeter@697: _pred(0), _dist(0), _path(0), _di(0) {} kpeter@696: kpeter@696: }; alpar@877: kpeter@697: /// \brief Auxiliary class for the function-type interface of the kpeter@697: /// \ref BellmanFord "Bellman-Ford" algorithm. kpeter@697: /// kpeter@697: /// This auxiliary class is created to implement the kpeter@697: /// \ref bellmanFord() "function-type interface" of the kpeter@697: /// \ref BellmanFord "Bellman-Ford" algorithm. kpeter@697: /// It does not have own \ref run() method, it uses the kpeter@697: /// functions and features of the plain \ref BellmanFord. kpeter@697: /// kpeter@697: /// This class should only be used through the \ref bellmanFord() kpeter@697: /// function, which makes it easier to use the algorithm. kpeter@825: /// kpeter@825: /// \tparam TR The traits class that defines various types used by the kpeter@825: /// algorithm. kpeter@697: template kpeter@697: class BellmanFordWizard : public TR { kpeter@697: typedef TR Base; kpeter@696: kpeter@697: typedef typename TR::Digraph Digraph; kpeter@696: kpeter@696: typedef typename Digraph::Node Node; kpeter@696: typedef typename Digraph::NodeIt NodeIt; kpeter@696: typedef typename Digraph::Arc Arc; kpeter@696: typedef typename Digraph::OutArcIt ArcIt; alpar@877: kpeter@697: typedef typename TR::LengthMap LengthMap; kpeter@696: typedef typename LengthMap::Value Value; kpeter@697: typedef typename TR::PredMap PredMap; kpeter@697: typedef typename TR::DistMap DistMap; kpeter@697: typedef typename TR::Path Path; kpeter@696: kpeter@696: public: kpeter@696: /// Constructor. kpeter@697: BellmanFordWizard() : TR() {} kpeter@696: kpeter@696: /// \brief Constructor that requires parameters. kpeter@696: /// kpeter@696: /// Constructor that requires parameters. kpeter@696: /// These parameters will be the default values for the traits class. kpeter@697: /// \param gr The digraph the algorithm runs on. kpeter@697: /// \param len The length map. alpar@877: BellmanFordWizard(const Digraph& gr, const LengthMap& len) kpeter@697: : TR(gr, len) {} kpeter@696: kpeter@696: /// \brief Copy constructor kpeter@697: BellmanFordWizard(const TR &b) : TR(b) {} kpeter@696: kpeter@696: ~BellmanFordWizard() {} kpeter@696: kpeter@697: /// \brief Runs the Bellman-Ford algorithm from the given source node. alpar@877: /// kpeter@697: /// This method runs the Bellman-Ford algorithm from the given source kpeter@697: /// node in order to compute the shortest path to each node. kpeter@697: void run(Node s) { alpar@877: BellmanFord alpar@877: bf(*reinterpret_cast(Base::_graph), kpeter@696: *reinterpret_cast(Base::_length)); kpeter@696: if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred)); kpeter@696: if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist)); kpeter@697: bf.run(s); kpeter@696: } kpeter@696: kpeter@697: /// \brief Runs the Bellman-Ford algorithm to find the shortest path kpeter@697: /// between \c s and \c t. kpeter@696: /// kpeter@697: /// This method runs the Bellman-Ford algorithm from node \c s kpeter@697: /// in order to compute the shortest path to node \c t. kpeter@697: /// Actually, it computes the shortest path to each node, but using kpeter@697: /// this function you can retrieve the distance and the shortest path kpeter@697: /// for a single target node easier. kpeter@697: /// kpeter@697: /// \return \c true if \c t is reachable form \c s. kpeter@697: bool run(Node s, Node t) { kpeter@697: BellmanFord kpeter@697: bf(*reinterpret_cast(Base::_graph), kpeter@697: *reinterpret_cast(Base::_length)); kpeter@697: if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred)); kpeter@697: if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist)); kpeter@697: bf.run(s); kpeter@697: if (Base::_path) *reinterpret_cast(Base::_path) = bf.path(t); kpeter@697: if (Base::_di) *reinterpret_cast(Base::_di) = bf.dist(t); kpeter@697: return bf.reached(t); kpeter@696: } kpeter@696: kpeter@696: template kpeter@697: struct SetPredMapBase : public Base { kpeter@696: typedef T PredMap; kpeter@696: static PredMap *createPredMap(const Digraph &) { return 0; }; kpeter@697: SetPredMapBase(const TR &b) : TR(b) {} kpeter@696: }; alpar@877: kpeter@697: /// \brief \ref named-templ-param "Named parameter" for setting kpeter@697: /// the predecessor map. kpeter@696: /// kpeter@697: /// \ref named-templ-param "Named parameter" for setting kpeter@697: /// the map that stores the predecessor arcs of the nodes. kpeter@696: template kpeter@697: BellmanFordWizard > predMap(const T &t) { kpeter@696: Base::_pred=reinterpret_cast(const_cast(&t)); kpeter@697: return BellmanFordWizard >(*this); kpeter@696: } alpar@877: kpeter@696: template kpeter@697: struct SetDistMapBase : public Base { kpeter@696: typedef T DistMap; kpeter@696: static DistMap *createDistMap(const Digraph &) { return 0; }; kpeter@697: SetDistMapBase(const TR &b) : TR(b) {} kpeter@696: }; alpar@877: kpeter@697: /// \brief \ref named-templ-param "Named parameter" for setting kpeter@697: /// the distance map. kpeter@696: /// kpeter@697: /// \ref named-templ-param "Named parameter" for setting kpeter@697: /// the map that stores the distances of the nodes calculated kpeter@697: /// by the algorithm. kpeter@696: template kpeter@697: BellmanFordWizard > distMap(const T &t) { kpeter@696: Base::_dist=reinterpret_cast(const_cast(&t)); kpeter@697: return BellmanFordWizard >(*this); kpeter@696: } kpeter@696: kpeter@696: template kpeter@697: struct SetPathBase : public Base { kpeter@697: typedef T Path; kpeter@697: SetPathBase(const TR &b) : TR(b) {} kpeter@696: }; kpeter@697: kpeter@697: /// \brief \ref named-func-param "Named parameter" for getting kpeter@697: /// the shortest path to the target node. kpeter@696: /// kpeter@697: /// \ref named-func-param "Named parameter" for getting kpeter@697: /// the shortest path to the target node. kpeter@697: template kpeter@697: BellmanFordWizard > path(const T &t) kpeter@697: { kpeter@697: Base::_path=reinterpret_cast(const_cast(&t)); kpeter@697: return BellmanFordWizard >(*this); kpeter@697: } kpeter@697: kpeter@697: /// \brief \ref named-func-param "Named parameter" for getting kpeter@697: /// the distance of the target node. kpeter@696: /// kpeter@697: /// \ref named-func-param "Named parameter" for getting kpeter@697: /// the distance of the target node. kpeter@697: BellmanFordWizard dist(const Value &d) kpeter@697: { kpeter@697: Base::_di=reinterpret_cast(const_cast(&d)); kpeter@696: return *this; kpeter@696: } alpar@877: kpeter@696: }; alpar@877: kpeter@697: /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" kpeter@697: /// algorithm. kpeter@696: /// kpeter@696: /// \ingroup shortest_path kpeter@697: /// Function type interface for the \ref BellmanFord "Bellman-Ford" kpeter@697: /// algorithm. kpeter@696: /// alpar@877: /// This function also has several \ref named-templ-func-param alpar@877: /// "named parameters", they are declared as the members of class kpeter@696: /// \ref BellmanFordWizard. kpeter@697: /// The following examples show how to use these parameters. kpeter@697: /// \code kpeter@697: /// // Compute shortest path from node s to each node kpeter@697: /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s); kpeter@697: /// kpeter@697: /// // Compute shortest path from s to t kpeter@697: /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t); kpeter@697: /// \endcode kpeter@696: /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()" kpeter@696: /// to the end of the parameter list. kpeter@696: /// \sa BellmanFordWizard kpeter@696: /// \sa BellmanFord kpeter@697: template kpeter@697: BellmanFordWizard > kpeter@697: bellmanFord(const GR& digraph, alpar@877: const LEN& length) kpeter@697: { kpeter@697: return BellmanFordWizard >(digraph, length); kpeter@696: } kpeter@696: kpeter@696: } //END OF NAMESPACE LEMON kpeter@696: kpeter@696: #endif kpeter@696: