diff --git a/lemon/bellman_ford.h b/lemon/bellman_ford.h --- a/lemon/bellman_ford.h +++ b/lemon/bellman_ford.h @@ -16,18 +16,18 @@ * */ -#ifndef LEMON_BELMANN_FORD_H -#define LEMON_BELMANN_FORD_H +#ifndef LEMON_BELLMAN_FORD_H +#define LEMON_BELLMAN_FORD_H /// \ingroup shortest_path /// \file /// \brief Bellman-Ford algorithm. -/// #include #include #include #include +#include #include @@ -35,15 +35,17 @@ /// \brief Default OperationTraits for the BellmanFord algorithm class. /// - /// It defines all computational operations and constants which are - /// used in the Bellman-Ford algorithm. The default implementation - /// is based on the numeric_limits class. If the numeric type does not - /// have infinity value then the maximum value is used as extremal - /// infinity value. + /// This operation traits class defines all computational operations + /// and constants that are used in the Bellman-Ford algorithm. + /// The default implementation is based on the \c numeric_limits class. + /// If the numeric type does not have infinity value, then the maximum + /// value is used as extremal infinity value. template < - typename Value, - bool has_infinity = std::numeric_limits::has_infinity> + typename V, + bool has_inf = std::numeric_limits::has_infinity> struct BellmanFordDefaultOperationTraits { + /// \e + typedef V Value; /// \brief Gives back the zero value of the type. static Value zero() { return static_cast(0); @@ -56,14 +58,16 @@ static Value plus(const Value& left, const Value& right) { return left + right; } - /// \brief Gives back true only if the first value less than the second. + /// \brief Gives back \c true only if the first value is less than + /// the second. static bool less(const Value& left, const Value& right) { return left < right; } }; - template - struct BellmanFordDefaultOperationTraits { + template + struct BellmanFordDefaultOperationTraits { + typedef V Value; static Value zero() { return static_cast(0); } @@ -82,26 +86,26 @@ /// \brief Default traits class of BellmanFord class. /// /// Default traits class of BellmanFord class. - /// \param _Digraph Digraph type. - /// \param _LegthMap Type of length map. - template + /// \param GR The type of the digraph. + /// \param LEN The type of the length map. + template struct BellmanFordDefaultTraits { - /// The digraph type the algorithm runs on. - typedef _Digraph Digraph; + /// The type of the digraph the algorithm runs on. + typedef GR Digraph; /// \brief The type of the map that stores the arc lengths. /// /// The type of the map that stores the arc lengths. - /// It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef _LengthMap LengthMap; + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef LEN LengthMap; - // The type of the length of the arcs. - typedef typename _LengthMap::Value Value; + /// The type of the arc lengths. + typedef typename LEN::Value Value; /// \brief Operation traits for Bellman-Ford algorithm. /// - /// It defines the infinity type on the given Value type - /// and the used operation. + /// It defines the used operations and the infinity value for the + /// given \c Value type. /// \see BellmanFordDefaultOperationTraits typedef BellmanFordDefaultOperationTraits OperationTraits; @@ -110,33 +114,31 @@ /// /// The type of the map that stores the last /// arcs of the shortest paths. - /// It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// - typedef typename Digraph::template NodeMap PredMap; + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. + typedef typename GR::template NodeMap PredMap; - /// \brief Instantiates a PredMap. + /// \brief Instantiates a \c PredMap. /// /// This function instantiates a \ref PredMap. - /// \param digraph is the digraph, to which we would like to define the PredMap. - static PredMap *createPredMap(const _Digraph& digraph) { - return new PredMap(digraph); + /// \param g is the digraph to which we would like to define the + /// \ref PredMap. + static PredMap *createPredMap(const GR& g) { + return new PredMap(g); } - /// \brief The type of the map that stores the dists of the nodes. + /// \brief The type of the map that stores the distances of the nodes. /// - /// The type of the map that stores the dists of the nodes. - /// It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// - typedef typename Digraph::template NodeMap - DistMap; + /// The type of the map that stores the distances of the nodes. + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. + typedef typename GR::template NodeMap DistMap; - /// \brief Instantiates a DistMap. + /// \brief Instantiates a \c DistMap. /// /// This function instantiates a \ref DistMap. - /// \param digraph is the digraph, to which we would like to define the - /// \ref DistMap - static DistMap *createDistMap(const _Digraph& digraph) { - return new DistMap(digraph); + /// \param g is the digraph to which we would like to define the + /// \ref DistMap. + static DistMap *createDistMap(const GR& g) { + return new DistMap(g); } }; @@ -144,106 +146,109 @@ /// \brief %BellmanFord algorithm class. /// /// \ingroup shortest_path - /// This class provides an efficient implementation of \c Bellman-Ford - /// algorithm. The arc lengths are passed to the algorithm using a + /// This class provides an efficient implementation of the Bellman-Ford + /// algorithm. The maximum time complexity of the algorithm is + /// O(ne). + /// + /// The Bellman-Ford algorithm solves the single-source shortest path + /// problem when the arcs can have negative lengths, but the digraph + /// should not contain directed cycles with negative total length. + /// If all arc costs are non-negative, consider to use the Dijkstra + /// algorithm instead, since it is more efficient. + /// + /// The arc lengths are passed to the algorithm using a /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any - /// kind of length. + /// kind of length. The type of the length values is determined by the + /// \ref concepts::ReadMap::Value "Value" type of the length map. /// - /// The Bellman-Ford algorithm solves the shortest path from one node - /// problem when the arcs can have negative length but the digraph should - /// not contain cycles with negative sum of length. If we can assume - /// that all arc is non-negative in the digraph then the dijkstra algorithm - /// should be used rather. + /// There is also a \ref bellmanFord() "function-type interface" for the + /// Bellman-Ford algorithm, which is convenient in the simplier cases and + /// it can be used easier. /// - /// The maximal time complexity of the algorithm is \f$ O(ne) \f$. - /// - /// The type of the length is determined by the - /// \ref concepts::ReadMap::Value "Value" of the length map. - /// - /// \param _Digraph The digraph type the algorithm runs on. The default value - /// is \ref ListDigraph. The value of _Digraph is not used directly by - /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. - /// \param _LengthMap This read-only ArcMap determines the lengths of the - /// arcs. The default map type is \ref concepts::Digraph::ArcMap - /// "Digraph::ArcMap". The value of _LengthMap is not used directly - /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. - /// \param _Traits Traits class to set various data types used by the - /// algorithm. The default traits class is \ref BellmanFordDefaultTraits - /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>". See \ref - /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits - /// class. + /// \tparam GR The type of the digraph the algorithm runs on. + /// The default type is \ref ListDigraph. + /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies + /// the lengths of the arcs. The default map type is + /// \ref concepts::Digraph::ArcMap "GR::ArcMap". #ifdef DOXYGEN - template + template #else - template , - typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> > + template , + typename TR=BellmanFordDefaultTraits > #endif class BellmanFord { public: - typedef _Traits Traits; ///The type of the underlying digraph. - typedef typename _Traits::Digraph Digraph; + typedef typename TR::Digraph Digraph; + + /// \brief The type of the arc lengths. + typedef typename TR::LengthMap::Value Value; + /// \brief The type of the map that stores the arc lengths. + typedef typename TR::LengthMap LengthMap; + /// \brief The type of the map that stores the last + /// arcs of the shortest paths. + typedef typename TR::PredMap PredMap; + /// \brief The type of the map that stores the distances of the nodes. + typedef typename TR::DistMap DistMap; + /// The type of the paths. + typedef PredMapPath Path; + ///\brief The \ref BellmanFordDefaultOperationTraits + /// "operation traits class" of the algorithm. + typedef typename TR::OperationTraits OperationTraits; + + ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm. + typedef TR Traits; + + private: typedef typename Digraph::Node Node; typedef typename Digraph::NodeIt NodeIt; typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - - /// \brief The type of the length of the arcs. - typedef typename _Traits::LengthMap::Value Value; - /// \brief The type of the map that stores the arc lengths. - typedef typename _Traits::LengthMap LengthMap; - /// \brief The type of the map that stores the last - /// arcs of the shortest paths. - typedef typename _Traits::PredMap PredMap; - /// \brief The type of the map that stores the dists of the nodes. - typedef typename _Traits::DistMap DistMap; - /// \brief The operation traits. - typedef typename _Traits::OperationTraits OperationTraits; - private: - /// Pointer to the underlying digraph. - const Digraph *digraph; - /// Pointer to the length map - const LengthMap *length; - ///Pointer to the map of predecessors arcs. + + // Pointer to the underlying digraph. + const Digraph *_gr; + // Pointer to the length map + const LengthMap *_length; + // Pointer to the map of predecessors arcs. PredMap *_pred; - ///Indicates if \ref _pred is locally allocated (\c true) or not. - bool local_pred; - ///Pointer to the map of distances. + // Indicates if _pred is locally allocated (true) or not. + bool _local_pred; + // Pointer to the map of distances. DistMap *_dist; - ///Indicates if \ref _dist is locally allocated (\c true) or not. - bool local_dist; + // Indicates if _dist is locally allocated (true) or not. + bool _local_dist; typedef typename Digraph::template NodeMap MaskMap; MaskMap *_mask; std::vector _process; - /// Creates the maps if necessary. + // Creates the maps if necessary. void create_maps() { if(!_pred) { - local_pred = true; - _pred = Traits::createPredMap(*digraph); + _local_pred = true; + _pred = Traits::createPredMap(*_gr); } if(!_dist) { - local_dist = true; - _dist = Traits::createDistMap(*digraph); + _local_dist = true; + _dist = Traits::createDistMap(*_gr); } - _mask = new MaskMap(*digraph, false); + _mask = new MaskMap(*_gr, false); } public : typedef BellmanFord Create; - /// \name Named template parameters + /// \name Named Template Parameters ///@{ template - struct DefPredMapTraits : public Traits { + struct SetPredMapTraits : public Traits { typedef T PredMap; static PredMap *createPredMap(const Digraph&) { LEMON_ASSERT(false, "PredMap is not initialized"); @@ -251,18 +256,20 @@ } }; - /// \brief \ref named-templ-param "Named parameter" for setting PredMap - /// type - /// \ref named-templ-param "Named parameter" for setting PredMap type + /// \brief \ref named-templ-param "Named parameter" for setting + /// \c PredMap type. /// + /// \ref named-templ-param "Named parameter" for setting + /// \c PredMap type. + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap - : public BellmanFord< Digraph, LengthMap, DefPredMapTraits > { - typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits > Create; + : public BellmanFord< Digraph, LengthMap, SetPredMapTraits > { + typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create; }; template - struct DefDistMapTraits : public Traits { + struct SetDistMapTraits : public Traits { typedef T DistMap; static DistMap *createDistMap(const Digraph&) { LEMON_ASSERT(false, "DistMap is not initialized"); @@ -270,31 +277,33 @@ } }; - /// \brief \ref named-templ-param "Named parameter" for setting DistMap - /// type + /// \brief \ref named-templ-param "Named parameter" for setting + /// \c DistMap type. /// - /// \ref named-templ-param "Named parameter" for setting DistMap type - /// + /// \ref named-templ-param "Named parameter" for setting + /// \c DistMap type. + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap - : public BellmanFord< Digraph, LengthMap, DefDistMapTraits > { - typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits > Create; + : public BellmanFord< Digraph, LengthMap, SetDistMapTraits > { + typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create; }; - + template - struct DefOperationTraitsTraits : public Traits { + struct SetOperationTraitsTraits : public Traits { typedef T OperationTraits; }; /// \brief \ref named-templ-param "Named parameter" for setting - /// OperationTraits type + /// \c OperationTraits type. /// - /// \ref named-templ-param "Named parameter" for setting OperationTraits - /// type + /// \ref named-templ-param "Named parameter" for setting + /// \c OperationTraits type. + /// For more information see \ref BellmanFordDefaultOperationTraits. template struct SetOperationTraits - : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits > { - typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits > + : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > { + typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > Create; }; @@ -308,85 +317,89 @@ /// \brief Constructor. /// - /// \param _graph the digraph the algorithm will run on. - /// \param _length the length map used by the algorithm. - BellmanFord(const Digraph& _graph, const LengthMap& _length) : - digraph(&_graph), length(&_length), - _pred(0), local_pred(false), - _dist(0), local_dist(false), _mask(0) {} + /// Constructor. + /// \param g The digraph the algorithm runs on. + /// \param length The length map used by the algorithm. + BellmanFord(const Digraph& g, const LengthMap& length) : + _gr(&g), _length(&length), + _pred(0), _local_pred(false), + _dist(0), _local_dist(false), _mask(0) {} ///Destructor. ~BellmanFord() { - if(local_pred) delete _pred; - if(local_dist) delete _dist; + if(_local_pred) delete _pred; + if(_local_dist) delete _dist; if(_mask) delete _mask; } /// \brief Sets the length map. /// /// Sets the length map. - /// \return \c (*this) - BellmanFord &lengthMap(const LengthMap &m) { - length = &m; + /// \return (*this) + BellmanFord &lengthMap(const LengthMap &map) { + _length = ↦ return *this; } - /// \brief Sets the map storing the predecessor arcs. + /// \brief Sets the map that stores the predecessor arcs. /// - /// Sets the map storing the predecessor arcs. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this - /// automatically allocated map, of course. - /// \return \c (*this) - BellmanFord &predMap(PredMap &m) { - if(local_pred) { + /// Sets the map that stores the predecessor arcs. + /// If you don't use this function before calling \ref run() + /// or \ref init(), an instance will be allocated automatically. + /// The destructor deallocates this automatically allocated map, + /// of course. + /// \return (*this) + BellmanFord &predMap(PredMap &map) { + if(_local_pred) { delete _pred; - local_pred=false; + _local_pred=false; } - _pred = &m; + _pred = ↦ return *this; } - /// \brief Sets the map storing the distances calculated by the algorithm. + /// \brief Sets the map that stores the distances of the nodes. /// - /// Sets the map storing the distances calculated by the algorithm. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this - /// automatically allocated map, of course. - /// \return \c (*this) - BellmanFord &distMap(DistMap &m) { - if(local_dist) { + /// Sets the map that stores the distances of the nodes calculated + /// by the algorithm. + /// If you don't use this function before calling \ref run() + /// or \ref init(), an instance will be allocated automatically. + /// The destructor deallocates this automatically allocated map, + /// of course. + /// \return (*this) + BellmanFord &distMap(DistMap &map) { + if(_local_dist) { delete _dist; - local_dist=false; + _local_dist=false; } - _dist = &m; + _dist = ↦ return *this; } - /// \name Execution control - /// The simplest way to execute the algorithm is to use - /// one of the member functions called \c run(...). - /// \n - /// If you need more control on the execution, - /// first you must call \ref init(), then you can add several source nodes - /// with \ref addSource(). - /// Finally \ref start() will perform the actual path - /// computation. + /// \name Execution Control + /// The simplest way to execute the Bellman-Ford algorithm is to use + /// one of the member functions called \ref run().\n + /// If you need better control on the execution, you have to call + /// \ref init() first, then you can add several source nodes + /// with \ref addSource(). Finally the actual path computation can be + /// performed with \ref start(), \ref checkedStart() or + /// \ref limitedStart(). ///@{ /// \brief Initializes the internal data structures. /// - /// Initializes the internal data structures. + /// Initializes the internal data structures. The optional parameter + /// is the initial distance of each node. void init(const Value value = OperationTraits::infinity()) { create_maps(); - for (NodeIt it(*digraph); it != INVALID; ++it) { + for (NodeIt it(*_gr); it != INVALID; ++it) { _pred->set(it, INVALID); _dist->set(it, value); } _process.clear(); if (OperationTraits::less(value, OperationTraits::infinity())) { - for (NodeIt it(*digraph); it != INVALID; ++it) { + for (NodeIt it(*_gr); it != INVALID; ++it) { _process.push_back(it); _mask->set(it, true); } @@ -395,9 +408,8 @@ /// \brief Adds a new source node. /// - /// Adds a new source node. The optional second parameter is the - /// initial distance of the node. It just sets the distance of the - /// node to the given value. + /// This function adds a new source node. The optional second parameter + /// is the initial distance of the node. void addSource(Node source, Value dst = OperationTraits::zero()) { _dist->set(source, dst); if (!(*_mask)[source]) { @@ -409,19 +421,22 @@ /// \brief Executes one round from the Bellman-Ford algorithm. /// /// If the algoritm calculated the distances in the previous round - /// exactly for all at most \f$ k \f$ length path lengths then it will - /// calculate the distances exactly for all at most \f$ k + 1 \f$ - /// length path lengths. With \f$ k \f$ iteration this function - /// calculates the at most \f$ k \f$ length path lengths. + /// exactly for the paths of at most \c k arcs, then this function + /// will calculate the distances exactly for the paths of at most + /// k+1 arcs. Performing \c k iterations using this function + /// calculates the shortest path distances exactly for the paths + /// consisting of at most \c k arcs. /// /// \warning The paths with limited arc number cannot be retrieved - /// easily with \ref path() or \ref predArc() functions. If you - /// need the shortest path and not just the distance you should store - /// after each iteration the \ref predMap() map and manually build - /// the path. + /// easily with \ref path() or \ref predArc() functions. If you also + /// need the shortest paths and not only the distances, you should + /// store the \ref predMap() "predecessor map" after each iteration + /// and build the path manually. /// /// \return \c true when the algorithm have not found more shorter /// paths. + /// + /// \see ActiveIt bool processNextRound() { for (int i = 0; i < int(_process.size()); ++i) { _mask->set(_process[i], false); @@ -432,9 +447,9 @@ values[i] = (*_dist)[_process[i]]; } for (int i = 0; i < int(_process.size()); ++i) { - for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) { - Node target = digraph->target(it); - Value relaxed = OperationTraits::plus(values[i], (*length)[it]); + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { + Node target = _gr->target(it); + Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); if (OperationTraits::less(relaxed, (*_dist)[target])) { _pred->set(target, it); _dist->set(target, relaxed); @@ -451,23 +466,28 @@ /// \brief Executes one weak round from the Bellman-Ford algorithm. /// - /// If the algorithm calculated the distances in the - /// previous round at least for all at most k length paths then it will - /// calculate the distances at least for all at most k + 1 length paths. - /// This function does not make it possible to calculate strictly the - /// at most k length minimal paths, this is why it is - /// called just weak round. - /// \return \c true when the algorithm have not found more shorter paths. + /// If the algorithm calculated the distances in the previous round + /// at least for the paths of at most \c k arcs, then this function + /// will calculate the distances at least for the paths of at most + /// k+1 arcs. + /// This function does not make it possible to calculate the shortest + /// path distances exactly for paths consisting of at most \c k arcs, + /// this is why it is called weak round. + /// + /// \return \c true when the algorithm have not found more shorter + /// paths. + /// + /// \see ActiveIt bool processNextWeakRound() { for (int i = 0; i < int(_process.size()); ++i) { _mask->set(_process[i], false); } std::vector nextProcess; for (int i = 0; i < int(_process.size()); ++i) { - for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) { - Node target = digraph->target(it); + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { + Node target = _gr->target(it); Value relaxed = - OperationTraits::plus((*_dist)[_process[i]], (*length)[it]); + OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); if (OperationTraits::less(relaxed, (*_dist)[target])) { _pred->set(target, it); _dist->set(target, relaxed); @@ -484,16 +504,19 @@ /// \brief Executes the algorithm. /// - /// \pre init() must be called and at least one node should be added - /// with addSource() before using this function. + /// Executes the algorithm. /// - /// This method runs the %BellmanFord algorithm from the root node(s) - /// in order to compute the shortest path to each node. The algorithm - /// computes - /// - The shortest path tree. - /// - The distance of each node from the root(s). + /// This method runs the Bellman-Ford algorithm from the root node(s) + /// in order to compute the shortest path to each node. + /// + /// The algorithm computes + /// - the shortest path tree (forest), + /// - the distance of each node from the root(s). + /// + /// \pre init() must be called and at least one root node should be + /// added with addSource() before using this function. void start() { - int num = countNodes(*digraph) - 1; + int num = countNodes(*_gr) - 1; for (int i = 0; i < num; ++i) { if (processNextWeakRound()) break; } @@ -501,83 +524,98 @@ /// \brief Executes the algorithm and checks the negative cycles. /// - /// \pre init() must be called and at least one node should be added - /// with addSource() before using this function. + /// Executes the algorithm and checks the negative cycles. /// - /// This method runs the %BellmanFord algorithm from the root node(s) - /// in order to compute the shortest path to each node. The algorithm - /// computes - /// - The shortest path tree. - /// - The distance of each node from the root(s). + /// This method runs the Bellman-Ford algorithm from the root node(s) + /// in order to compute the shortest path to each node and also checks + /// if the digraph contains cycles with negative total length. + /// + /// The algorithm computes + /// - the shortest path tree (forest), + /// - the distance of each node from the root(s). /// /// \return \c false if there is a negative cycle in the digraph. + /// + /// \pre init() must be called and at least one root node should be + /// added with addSource() before using this function. bool checkedStart() { - int num = countNodes(*digraph); + int num = countNodes(*_gr); for (int i = 0; i < num; ++i) { if (processNextWeakRound()) return true; } return _process.empty(); } - /// \brief Executes the algorithm with path length limit. + /// \brief Executes the algorithm with arc number limit. /// - /// \pre init() must be called and at least one node should be added - /// with addSource() before using this function. + /// Executes the algorithm with arc number limit. /// - /// This method runs the %BellmanFord algorithm from the root - /// node(s) in order to compute the shortest path lengths with at - /// most \c num arc. + /// This method runs the Bellman-Ford algorithm from the root node(s) + /// in order to compute the shortest path distance for each node + /// using only the paths consisting of at most \c num arcs. + /// + /// The algorithm computes + /// - the limited distance of each node from the root(s), + /// - the predecessor arc for each node. /// /// \warning The paths with limited arc number cannot be retrieved - /// easily with \ref path() or \ref predArc() functions. If you - /// need the shortest path and not just the distance you should store - /// after each iteration the \ref predMap() map and manually build - /// the path. + /// easily with \ref path() or \ref predArc() functions. If you also + /// need the shortest paths and not only the distances, you should + /// store the \ref predMap() "predecessor map" after each iteration + /// and build the path manually. /// - /// The algorithm computes - /// - The predecessor arc from each node. - /// - The limited distance of each node from the root(s). + /// \pre init() must be called and at least one root node should be + /// added with addSource() before using this function. void limitedStart(int num) { for (int i = 0; i < num; ++i) { if (processNextRound()) break; } } - /// \brief Runs %BellmanFord algorithm from node \c s. + /// \brief Runs the algorithm from the given root node. /// - /// This method runs the %BellmanFord algorithm from a root node \c s - /// in order to compute the shortest path to each node. The algorithm - /// computes - /// - The shortest path tree. - /// - The distance of each node from the root. + /// This method runs the Bellman-Ford algorithm from the given root + /// node \c s in order to compute the shortest path to each node. /// - /// \note d.run(s) is just a shortcut of the following code. - ///\code - /// d.init(); - /// d.addSource(s); - /// d.start(); - ///\endcode + /// The algorithm computes + /// - the shortest path tree (forest), + /// - the distance of each node from the root(s). + /// + /// \note bf.run(s) is just a shortcut of the following code. + /// \code + /// bf.init(); + /// bf.addSource(s); + /// bf.start(); + /// \endcode void run(Node s) { init(); addSource(s); start(); } - /// \brief Runs %BellmanFord algorithm with limited path length - /// from node \c s. + /// \brief Runs the algorithm from the given root node with arc + /// number limit. /// - /// This method runs the %BellmanFord algorithm from a root node \c s - /// in order to compute the shortest path with at most \c len arcs - /// to each node. The algorithm computes - /// - The shortest path tree. - /// - The distance of each node from the root. + /// This method runs the Bellman-Ford algorithm from the given root + /// node \c s in order to compute the shortest path distance for each + /// node using only the paths consisting of at most \c num arcs. /// - /// \note d.run(s, num) is just a shortcut of the following code. - ///\code - /// d.init(); - /// d.addSource(s); - /// d.limitedStart(num); - ///\endcode + /// The algorithm computes + /// - the limited distance of each node from the root(s), + /// - the predecessor arc for each node. + /// + /// \warning The paths with limited arc number cannot be retrieved + /// easily with \ref path() or \ref predArc() functions. If you also + /// need the shortest paths and not only the distances, you should + /// store the \ref predMap() "predecessor map" after each iteration + /// and build the path manually. + /// + /// \note bf.run(s, num) is just a shortcut of the following code. + /// \code + /// bf.init(); + /// bf.addSource(s); + /// bf.limitedStart(num); + /// \endcode void run(Node s, int num) { init(); addSource(s); @@ -586,27 +624,19 @@ ///@} - /// \name Query Functions - /// The result of the %BellmanFord algorithm can be obtained using these - /// functions.\n - /// Before the use of these functions, - /// either run() or start() must be called. - - ///@{ - - /// \brief Lemon iterator for get the active nodes. + /// \brief LEMON iterator for getting the active nodes. /// - /// Lemon iterator for get the active nodes. This class provides a - /// common style lemon iterator which gives back a subset of the - /// nodes. The iterated nodes are active in the algorithm after - /// the last phase so these should be checked in the next phase to - /// find augmenting arcs from these. + /// This class provides a common style LEMON iterator that traverses + /// the active nodes of the Bellman-Ford algorithm after the last + /// phase. These nodes should be checked in the next phase to + /// find augmenting arcs outgoing from them. class ActiveIt { public: /// \brief Constructor. /// - /// Constructor for get the nodeset of the variable. + /// Constructor for getting the active nodes of the given BellmanFord + /// instance. ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) { _index = _algorithm->_process.size() - 1; @@ -617,9 +647,9 @@ /// Invalid constructor. ActiveIt(Invalid) : _algorithm(0), _index(-1) {} - /// \brief Conversion to node. + /// \brief Conversion to \c Node. /// - /// Conversion to node. + /// Conversion to \c Node. operator Node() const { return _index >= 0 ? _algorithm->_process[_index] : INVALID; } @@ -646,394 +676,432 @@ const BellmanFord* _algorithm; int _index; }; + + /// \name Query Functions + /// The result of the Bellman-Ford algorithm can be obtained using these + /// functions.\n + /// Either \ref run() or \ref init() should be called before using them. + + ///@{ - typedef PredMapPath Path; + /// \brief The shortest path to the given node. + /// + /// Gives back the shortest path to the given node from the root(s). + /// + /// \warning \c t should be reached from the root(s). + /// + /// \pre Either \ref run() or \ref init() must be called before + /// using this function. + Path path(Node t) const + { + return Path(*_gr, *_pred, t); + } + + /// \brief The distance of the given node from the root(s). + /// + /// Returns the distance of the given node from the root(s). + /// + /// \warning If node \c v is not reached from the root(s), then + /// the return value of this function is undefined. + /// + /// \pre Either \ref run() or \ref init() must be called before + /// using this function. + Value dist(Node v) const { return (*_dist)[v]; } - /// \brief Gives back the shortest path. - /// - /// Gives back the shortest path. - /// \pre The \c t should be reachable from the source. - Path path(Node t) - { - return Path(*digraph, *_pred, t); + /// \brief Returns the 'previous arc' of the shortest path tree for + /// the given node. + /// + /// This function returns the 'previous arc' of the shortest path + /// tree for node \c v, i.e. it returns the last arc of a + /// shortest path from a root to \c v. It is \c INVALID if \c v + /// is not reached from the root(s) or if \c v is a root. + /// + /// The shortest path tree used here is equal to the shortest path + /// tree used in \ref predNode() and \predMap(). + /// + /// \pre Either \ref run() or \ref init() must be called before + /// using this function. + Arc predArc(Node v) const { return (*_pred)[v]; } + + /// \brief Returns the 'previous node' of the shortest path tree for + /// the given node. + /// + /// This function returns the 'previous node' of the shortest path + /// tree for node \c v, i.e. it returns the last but one node of + /// a shortest path from a root to \c v. It is \c INVALID if \c v + /// is not reached from the root(s) or if \c v is a root. + /// + /// The shortest path tree used here is equal to the shortest path + /// tree used in \ref predArc() and \predMap(). + /// + /// \pre Either \ref run() or \ref init() must be called before + /// using this function. + Node predNode(Node v) const { + return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); + } + + /// \brief Returns a const reference to the node map that stores the + /// distances of the nodes. + /// + /// Returns a const reference to the node map that stores the distances + /// of the nodes calculated by the algorithm. + /// + /// \pre Either \ref run() or \ref init() must be called before + /// using this function. + const DistMap &distMap() const { return *_dist;} + + /// \brief Returns a const reference to the node map that stores the + /// predecessor arcs. + /// + /// Returns a const reference to the node map that stores the predecessor + /// arcs, which form the shortest path tree (forest). + /// + /// \pre Either \ref run() or \ref init() must be called before + /// using this function. + const PredMap &predMap() const { return *_pred; } + + /// \brief Checks if a node is reached from the root(s). + /// + /// Returns \c true if \c v is reached from the root(s). + /// + /// \pre Either \ref run() or \ref init() must be called before + /// using this function. + bool reached(Node v) const { + return (*_dist)[v] != OperationTraits::infinity(); } - - // TODO : implement negative cycle -// /// \brief Gives back a negative cycle. -// /// -// /// This function gives back a negative cycle. -// /// If the algorithm have not found yet negative cycle it will give back -// /// an empty path. -// Path negativeCycle() { -// typename Digraph::template NodeMap state(*digraph, 0); -// for (ActiveIt it(*this); it != INVALID; ++it) { -// if (state[it] == 0) { -// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { -// if (state[t] == 0) { -// state[t] = 1; -// } else if (state[t] == 2) { -// break; -// } else { -// p.clear(); -// typename Path::Builder b(p); -// b.setStartNode(t); -// b.pushFront(predArc(t)); -// for(Node s = predNode(t); s != t; s = predNode(s)) { -// b.pushFront(predArc(s)); -// } -// b.commit(); -// return true; -// } -// } -// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { -// if (state[t] == 1) { -// state[t] = 2; -// } else { -// break; -// } -// } -// } -// } -// return false; -// } - - /// \brief The distance of a node from the root. - /// - /// Returns the distance of a node from the root. - /// \pre \ref run() must be called before using this function. - /// \warning If node \c v in unreachable from the root the return value - /// of this funcion is undefined. - Value dist(Node v) const { return (*_dist)[v]; } - - /// \brief Returns the 'previous arc' of the shortest path tree. - /// - /// For a node \c v it returns the 'previous arc' of the shortest path - /// tree, i.e. it returns the last arc of a shortest path from the root - /// to \c v. It is \ref INVALID if \c v is unreachable from the root or - /// if \c v=s. The shortest path tree used here is equal to the shortest - /// path tree used in \ref predNode(). - /// \pre \ref run() must be called before using - /// this function. - Arc predArc(Node v) const { return (*_pred)[v]; } - - /// \brief Returns the 'previous node' of the shortest path tree. - /// - /// For a node \c v it returns the 'previous node' of the shortest path - /// tree, i.e. it returns the last but one node from a shortest path from - /// the root to \c /v. It is INVALID if \c v is unreachable from the root - /// or if \c v=s. The shortest path tree used here is equal to the - /// shortest path tree used in \ref predArc(). \pre \ref run() must be - /// called before using this function. - Node predNode(Node v) const { - return (*_pred)[v] == INVALID ? INVALID : digraph->source((*_pred)[v]); - } - - /// \brief Returns a reference to the NodeMap of distances. - /// - /// Returns a reference to the NodeMap of distances. \pre \ref run() must - /// be called before using this function. - const DistMap &distMap() const { return *_dist;} - - /// \brief Returns a reference to the shortest path tree map. - /// - /// Returns a reference to the NodeMap of the arcs of the - /// shortest path tree. - /// \pre \ref run() must be called before using this function. - const PredMap &predMap() const { return *_pred; } - - /// \brief Checks if a node is reachable from the root. - /// - /// Returns \c true if \c v is reachable from the root. - /// \pre \ref run() must be called before using this function. - /// - bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); } + // TODO: implement negative cycle +// /// \brief Gives back a negative cycle. +// /// +// /// This function gives back a negative cycle. +// /// If the algorithm have not found yet negative cycle it will give back +// /// an empty path. +// Path negativeCycle() { +// typename Digraph::template NodeMap state(*digraph, 0); +// for (ActiveIt it(*this); it != INVALID; ++it) { +// if (state[it] == 0) { +// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { +// if (state[t] == 0) { +// state[t] = 1; +// } else if (state[t] == 2) { +// break; +// } else { +// p.clear(); +// typename Path::Builder b(p); +// b.setStartNode(t); +// b.pushFront(predArc(t)); +// for(Node s = predNode(t); s != t; s = predNode(s)) { +// b.pushFront(predArc(s)); +// } +// b.commit(); +// return true; +// } +// } +// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { +// if (state[t] == 1) { +// state[t] = 2; +// } else { +// break; +// } +// } +// } +// } +// return false; +// } ///@} }; - /// \brief Default traits class of BellmanFord function. + /// \brief Default traits class of bellmanFord() function. /// - /// Default traits class of BellmanFord function. - /// \param _Digraph Digraph type. - /// \param _LengthMap Type of length map. - template + /// Default traits class of bellmanFord() function. + /// \tparam GR The type of the digraph. + /// \tparam LEN The type of the length map. + template struct BellmanFordWizardDefaultTraits { - /// \brief The digraph type the algorithm runs on. - typedef _Digraph Digraph; + /// The type of the digraph the algorithm runs on. + typedef GR Digraph; /// \brief The type of the map that stores the arc lengths. /// /// The type of the map that stores the arc lengths. /// It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef _LengthMap LengthMap; + typedef LEN LengthMap; - /// \brief The value type of the length map. - typedef typename _LengthMap::Value Value; + /// The type of the arc lengths. + typedef typename LEN::Value Value; /// \brief Operation traits for Bellman-Ford algorithm. /// - /// It defines the infinity type on the given Value type - /// and the used operation. + /// It defines the used operations and the infinity value for the + /// given \c Value type. /// \see BellmanFordDefaultOperationTraits typedef BellmanFordDefaultOperationTraits OperationTraits; /// \brief The type of the map that stores the last /// arcs of the shortest paths. /// - /// The type of the map that stores the last - /// arcs of the shortest paths. - /// It must meet the \ref concepts::WriteMap "WriteMap" concept. - typedef NullMap PredMap; + /// The type of the map that stores the last arcs of the shortest paths. + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. + typedef typename GR::template NodeMap PredMap; - /// \brief Instantiates a PredMap. + /// \brief Instantiates a \c PredMap. /// - /// This function instantiates a \ref PredMap. - static PredMap *createPredMap(const _Digraph &) { - return new PredMap(); + /// This function instantiates a \ref PredMap. + /// \param g is the digraph to which we would like to define the + /// \ref PredMap. + static PredMap *createPredMap(const GR &g) { + return new PredMap(g); } - /// \brief The type of the map that stores the dists of the nodes. + + /// \brief The type of the map that stores the distances of the nodes. /// - /// The type of the map that stores the dists of the nodes. - /// It must meet the \ref concepts::WriteMap "WriteMap" concept. - typedef NullMap DistMap; - /// \brief Instantiates a DistMap. + /// The type of the map that stores the distances of the nodes. + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. + typedef typename GR::template NodeMap DistMap; + + /// \brief Instantiates a \c DistMap. /// /// This function instantiates a \ref DistMap. - static DistMap *createDistMap(const _Digraph &) { - return new DistMap(); + /// \param g is the digraph to which we would like to define the + /// \ref DistMap. + static DistMap *createDistMap(const GR &g) { + return new DistMap(g); } + + ///The type of the shortest paths. + + ///The type of the shortest paths. + ///It must meet the \ref concepts::Path "Path" concept. + typedef lemon::Path Path; }; - /// \brief Default traits used by \ref BellmanFordWizard + /// \brief Default traits class used by BellmanFordWizard. /// - /// To make it easier to use BellmanFord algorithm - /// we have created a wizard class. - /// This \ref BellmanFordWizard class needs default traits, - /// as well as the \ref BellmanFord class. - /// The \ref BellmanFordWizardBase is a class to be the default traits of the - /// \ref BellmanFordWizard class. - /// \todo More named parameters are required... - template + /// Default traits class used by BellmanFordWizard. + /// \tparam GR The type of the digraph. + /// \tparam LEN The type of the length map. + template class BellmanFordWizardBase - : public BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> { + : public BellmanFordWizardDefaultTraits { - typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base; + typedef BellmanFordWizardDefaultTraits Base; protected: - /// Type of the nodes in the digraph. + // Type of the nodes in the digraph. typedef typename Base::Digraph::Node Node; - /// Pointer to the underlying digraph. + // Pointer to the underlying digraph. void *_graph; - /// Pointer to the length map + // Pointer to the length map void *_length; - ///Pointer to the map of predecessors arcs. + // Pointer to the map of predecessors arcs. void *_pred; - ///Pointer to the map of distances. + // Pointer to the map of distances. void *_dist; - ///Pointer to the source node. - Node _source; + //Pointer to the shortest path to the target node. + void *_path; + //Pointer to the distance of the target node. + void *_di; public: /// Constructor. - /// This constructor does not require parameters, therefore it initiates - /// all of the attributes to default values (0, INVALID). - BellmanFordWizardBase() : _graph(0), _length(0), _pred(0), - _dist(0), _source(INVALID) {} + /// This constructor does not require parameters, it initiates + /// all of the attributes to default values \c 0. + BellmanFordWizardBase() : + _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {} /// Constructor. - /// This constructor requires some parameters, - /// listed in the parameters list. - /// Others are initiated to 0. - /// \param digraph is the initial value of \ref _graph - /// \param length is the initial value of \ref _length - /// \param source is the initial value of \ref _source - BellmanFordWizardBase(const _Digraph& digraph, - const _LengthMap& length, - Node source = INVALID) : - _graph(reinterpret_cast(const_cast<_Digraph*>(&digraph))), - _length(reinterpret_cast(const_cast<_LengthMap*>(&length))), - _pred(0), _dist(0), _source(source) {} + /// This constructor requires two parameters, + /// others are initiated to \c 0. + /// \param gr The digraph the algorithm runs on. + /// \param len The length map. + BellmanFordWizardBase(const GR& gr, + const LEN& len) : + _graph(reinterpret_cast(const_cast(&gr))), + _length(reinterpret_cast(const_cast(&len))), + _pred(0), _dist(0), _path(0), _di(0) {} }; - /// A class to make the usage of BellmanFord algorithm easier + /// \brief Auxiliary class for the function-type interface of the + /// \ref BellmanFord "Bellman-Ford" algorithm. + /// + /// This auxiliary class is created to implement the + /// \ref bellmanFord() "function-type interface" of the + /// \ref BellmanFord "Bellman-Ford" algorithm. + /// It does not have own \ref run() method, it uses the + /// functions and features of the plain \ref BellmanFord. + /// + /// This class should only be used through the \ref bellmanFord() + /// function, which makes it easier to use the algorithm. + template + class BellmanFordWizard : public TR { + typedef TR Base; - /// This class is created to make it easier to use BellmanFord algorithm. - /// It uses the functions and features of the plain \ref BellmanFord, - /// but it is much simpler to use it. - /// - /// Simplicity means that the way to change the types defined - /// in the traits class is based on functions that returns the new class - /// and not on templatable built-in classes. - /// When using the plain \ref BellmanFord - /// the new class with the modified type comes from - /// the original class by using the :: - /// operator. In the case of \ref BellmanFordWizard only - /// a function have to be called and it will - /// return the needed class. - /// - /// It does not have own \ref run method. When its \ref run method is called - /// it initiates a plain \ref BellmanFord class, and calls the \ref - /// BellmanFord::run method of it. - template - class BellmanFordWizard : public _Traits { - typedef _Traits Base; - - ///The type of the underlying digraph. - typedef typename _Traits::Digraph Digraph; + typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; typedef typename Digraph::NodeIt NodeIt; typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt ArcIt; - ///The type of the map that stores the arc lengths. - typedef typename _Traits::LengthMap LengthMap; - - ///The type of the length of the arcs. + typedef typename TR::LengthMap LengthMap; typedef typename LengthMap::Value Value; - - ///\brief The type of the map that stores the last - ///arcs of the shortest paths. - typedef typename _Traits::PredMap PredMap; - - ///The type of the map that stores the dists of the nodes. - typedef typename _Traits::DistMap DistMap; + typedef typename TR::PredMap PredMap; + typedef typename TR::DistMap DistMap; + typedef typename TR::Path Path; public: /// Constructor. - BellmanFordWizard() : _Traits() {} + BellmanFordWizard() : TR() {} /// \brief Constructor that requires parameters. /// /// Constructor that requires parameters. /// These parameters will be the default values for the traits class. - BellmanFordWizard(const Digraph& digraph, const LengthMap& length, - Node src = INVALID) - : _Traits(digraph, length, src) {} + /// \param gr The digraph the algorithm runs on. + /// \param len The length map. + BellmanFordWizard(const Digraph& gr, const LengthMap& len) + : TR(gr, len) {} /// \brief Copy constructor - BellmanFordWizard(const _Traits &b) : _Traits(b) {} + BellmanFordWizard(const TR &b) : TR(b) {} ~BellmanFordWizard() {} - /// \brief Runs BellmanFord algorithm from a given node. + /// \brief Runs the Bellman-Ford algorithm from the given source node. /// - /// Runs BellmanFord algorithm from a given node. - /// The node can be given by the \ref source function. - void run() { - LEMON_ASSERT(Base::_source != INVALID, "Source node is not given"); - BellmanFord + /// This method runs the Bellman-Ford algorithm from the given source + /// node in order to compute the shortest path to each node. + void run(Node s) { + BellmanFord bf(*reinterpret_cast(Base::_graph), *reinterpret_cast(Base::_length)); if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred)); if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist)); - bf.run(Base::_source); + bf.run(s); } - /// \brief Runs BellmanFord algorithm from the given node. + /// \brief Runs the Bellman-Ford algorithm to find the shortest path + /// between \c s and \c t. /// - /// Runs BellmanFord algorithm from the given node. - /// \param src is the given source. - void run(Node src) { - Base::_source = src; - run(); + /// This method runs the Bellman-Ford algorithm from node \c s + /// in order to compute the shortest path to node \c t. + /// Actually, it computes the shortest path to each node, but using + /// this function you can retrieve the distance and the shortest path + /// for a single target node easier. + /// + /// \return \c true if \c t is reachable form \c s. + bool run(Node s, Node t) { + BellmanFord + bf(*reinterpret_cast(Base::_graph), + *reinterpret_cast(Base::_length)); + if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist)); + bf.run(s); + if (Base::_path) *reinterpret_cast(Base::_path) = bf.path(t); + if (Base::_di) *reinterpret_cast(Base::_di) = bf.dist(t); + return bf.reached(t); } template - struct DefPredMapBase : public Base { + struct SetPredMapBase : public Base { typedef T PredMap; static PredMap *createPredMap(const Digraph &) { return 0; }; - DefPredMapBase(const _Traits &b) : _Traits(b) {} + SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting PredMap type + /// \brief \ref named-templ-param "Named parameter" for setting + /// the predecessor map. /// - /// \ref named-templ-param "Named parameter" - ///function for setting PredMap type - /// + /// \ref named-templ-param "Named parameter" for setting + /// the map that stores the predecessor arcs of the nodes. template - BellmanFordWizard > predMap(const T &t) - { + BellmanFordWizard > predMap(const T &t) { Base::_pred=reinterpret_cast(const_cast(&t)); - return BellmanFordWizard >(*this); + return BellmanFordWizard >(*this); } template - struct DefDistMapBase : public Base { + struct SetDistMapBase : public Base { typedef T DistMap; static DistMap *createDistMap(const Digraph &) { return 0; }; - DefDistMapBase(const _Traits &b) : _Traits(b) {} + SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting DistMap type + /// \brief \ref named-templ-param "Named parameter" for setting + /// the distance map. /// - /// \ref named-templ-param "Named parameter" - ///function for setting DistMap type - /// + /// \ref named-templ-param "Named parameter" for setting + /// the map that stores the distances of the nodes calculated + /// by the algorithm. template - BellmanFordWizard > distMap(const T &t) { + BellmanFordWizard > distMap(const T &t) { Base::_dist=reinterpret_cast(const_cast(&t)); - return BellmanFordWizard >(*this); + return BellmanFordWizard >(*this); } template - struct DefOperationTraitsBase : public Base { - typedef T OperationTraits; - DefOperationTraitsBase(const _Traits &b) : _Traits(b) {} + struct SetPathBase : public Base { + typedef T Path; + SetPathBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" - ///function for setting OperationTraits type + + /// \brief \ref named-func-param "Named parameter" for getting + /// the shortest path to the target node. /// - /// \ref named-templ-param "Named parameter" - ///function for setting OperationTraits type + /// \ref named-func-param "Named parameter" for getting + /// the shortest path to the target node. + template + BellmanFordWizard > path(const T &t) + { + Base::_path=reinterpret_cast(const_cast(&t)); + return BellmanFordWizard >(*this); + } + + /// \brief \ref named-func-param "Named parameter" for getting + /// the distance of the target node. /// - template - BellmanFordWizard > distMap() { - return BellmanFordWizard >(*this); - } - - /// \brief Sets the source node, from which the BellmanFord algorithm runs. - /// - /// Sets the source node, from which the BellmanFord algorithm runs. - /// \param src is the source node. - BellmanFordWizard<_Traits>& source(Node src) { - Base::_source = src; + /// \ref named-func-param "Named parameter" for getting + /// the distance of the target node. + BellmanFordWizard dist(const Value &d) + { + Base::_di=reinterpret_cast(const_cast(&d)); return *this; } }; - /// \brief Function type interface for BellmanFord algorithm. + /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" + /// algorithm. /// /// \ingroup shortest_path - /// Function type interface for BellmanFord algorithm. + /// Function type interface for the \ref BellmanFord "Bellman-Ford" + /// algorithm. /// /// This function also has several \ref named-templ-func-param /// "named parameters", they are declared as the members of class /// \ref BellmanFordWizard. - /// The following - /// example shows how to use these parameters. - ///\code - /// bellmanford(g,length,source).predMap(preds).run(); - ///\endcode + /// The following examples show how to use these parameters. + /// \code + /// // Compute shortest path from node s to each node + /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s); + /// + /// // Compute shortest path from s to t + /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t); + /// \endcode /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()" /// to the end of the parameter list. /// \sa BellmanFordWizard /// \sa BellmanFord - template - BellmanFordWizard > - bellmanFord(const _Digraph& digraph, - const _LengthMap& length, - typename _Digraph::Node source = INVALID) { - return BellmanFordWizard > - (digraph, length, source); + template + BellmanFordWizard > + bellmanFord(const GR& digraph, + const LEN& length) + { + return BellmanFordWizard >(digraph, length); } } //END OF NAMESPACE LEMON