# Changeset 744:9496ed797f20 in lemon for lemon

Ignore:
Timestamp:
08/02/09 13:24:46 (11 years ago)
Branch:
default
Phase:
public
Message:

Improvements and unifications for BellmanFord? (#51)

• Rework the function type interface to fit to dijkstra().
• Rename named template parameters (Def* -> Set*).
• Simplify template parameter names.
• Many unifications and improvements in the doc.
File:
1 edited

### Legend:

Unmodified
 r743 */ #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 /// \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 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); /// /// 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; // The type of the length of the arcs. typedef typename _LengthMap::Value Value; /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef LEN LengthMap; /// 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; /// 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; /// \brief Instantiates a PredMap. /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename GR::template NodeMap 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); } /// \brief The type of the map that stores the dists 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; /// \brief Instantiates a DistMap. /// \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 distances of the nodes. /// /// 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. /// \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); } /// /// \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. /// /// 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. /// /// 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. /// kind of length. The type of the length values is determined by the /// \ref concepts::ReadMap::Value "Value" type of the length map. /// /// 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. /// /// \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::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; 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); } _mask = new MaskMap(*digraph, false); _local_dist = true; _dist = Traits::createDistMap(*_gr); } _mask = new MaskMap(*_gr, false); } 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&) { }; /// \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&) { }; /// \brief \ref named-templ-param "Named parameter" for setting DistMap /// type /// /// \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 /// \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 /// /// \ref named-templ-param "Named parameter" for setting OperationTraits /// type /// \c 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; }; /// \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; } /// /// 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. /// /// 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) { /// \brief Sets the map that stores the predecessor arcs. /// /// 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; } _pred = &m; _local_pred=false; } _pred = ↦ return *this; } /// \brief Sets the map storing the distances calculated by the algorithm. /// /// 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) { /// \brief Sets the map that stores the distances of the nodes. /// /// 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; } _dist = &m; _local_dist=false; } _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); /// \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 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) { } 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); /// \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) { 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); /// \brief Executes the algorithm. /// /// \pre init() must be called and at least one node should be added /// with addSource() before using this function. /// /// 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). /// Executes the algorithm. /// /// 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; /// \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. /// /// 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). /// Executes the algorithm and checks the negative cycles. /// /// 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; } /// \brief Executes the algorithm with path length limit. /// /// \pre init() must be called and at least one node should be added /// with addSource() before using this function. /// /// 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. /// \brief Executes the algorithm with arc number limit. /// /// Executes the algorithm with arc number limit. /// /// 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. /// /// The algorithm computes /// - The predecessor arc from each node. /// - The limited distance of each node from the root(s). /// 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. /// /// \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) { } /// \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. /// /// \note d.run(s) is just a shortcut of the following code. ///\code ///  d.init(); ///  d.addSource(s); ///  d.start(); ///\endcode /// This method runs the Bellman-Ford algorithm from the given root /// node \c 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). /// /// \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(); } /// \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. /// /// \note d.run(s, num) is just a shortcut of the following code. ///\code ///  d.init(); ///  d.addSource(s); ///  d.limitedStart(num); ///\endcode /// 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. /// /// 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(); ///@} /// \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. /// /// 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. /// \brief LEMON iterator for getting the active nodes. /// /// 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) { 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; int _index; }; typedef PredMapPath Path; /// \brief Gives back the shortest path. /// \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. ///@{ /// \brief The shortest path to the given node. /// /// Gives back the shortest path. /// \pre The \c t should be reachable from the source. Path path(Node t) /// 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(*digraph, *_pred, t); } // 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; //     } return Path(*_gr, *_pred, t); } /// \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. /// \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 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. /// \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 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. /// \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 : 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. 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 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. /// \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 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(); } /// \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 Default traits class of BellmanFord function. /// /// Default traits class of BellmanFord function. /// \param _Digraph Digraph type. /// \param _LengthMap Type of length map. template /// \brief Default traits class of bellmanFord() function. /// /// 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; /// \brief The value type of the length map. typedef typename _LengthMap::Value Value; typedef LEN LengthMap; /// 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; /// 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; /// \brief Instantiates a 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 \c PredMap. /// /// This function instantiates a \ref PredMap. static PredMap *createPredMap(const _Digraph &) { return new PredMap(); } /// \brief The type of the map that stores the dists 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. /// 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 distances of the nodes. /// /// 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 /// /// 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 /// \brief Default traits class used by BellmanFordWizard. /// /// 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> { typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base; : public BellmanFordWizardDefaultTraits { 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 /// 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; /// \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; typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; 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); } /// \brief Runs BellmanFord algorithm from the given node. /// /// Runs BellmanFord algorithm from the given node. /// \param src is the given source. void run(Node src) { Base::_source = src; run(); bf.run(s); } /// \brief Runs the Bellman-Ford algorithm to find the shortest path /// between \c s and \c t. /// /// 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 /// /// \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" 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 /// /// \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" 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 /// /// \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-func-param "Named parameter" for getting /// the shortest path to 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; 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. /// /// \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); }