diff options
Diffstat (limited to 'extern/quadriflow/3rd/lemon-1.3.1/lemon/bellman_ford.h')
| -rw-r--r-- | extern/quadriflow/3rd/lemon-1.3.1/lemon/bellman_ford.h | 1116 |
1 files changed, 1116 insertions, 0 deletions
diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bellman_ford.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bellman_ford.h new file mode 100644 index 00000000000..310758ebb59 --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bellman_ford.h @@ -0,0 +1,1116 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_BELLMAN_FORD_H +#define LEMON_BELLMAN_FORD_H + +/// \ingroup shortest_path +/// \file +/// \brief Bellman-Ford algorithm. + +#include <lemon/list_graph.h> +#include <lemon/bits/path_dump.h> +#include <lemon/core.h> +#include <lemon/error.h> +#include <lemon/maps.h> +#include <lemon/path.h> + +#include <limits> + +namespace lemon { + + /// \brief Default OperationTraits for the BellmanFord algorithm class. + /// + /// 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 V, + bool has_inf = std::numeric_limits<V>::has_infinity> + struct BellmanFordDefaultOperationTraits { + /// \e + typedef V Value; + /// \brief Gives back the zero value of the type. + static Value zero() { + return static_cast<Value>(0); + } + /// \brief Gives back the positive infinity value of the type. + static Value infinity() { + return std::numeric_limits<Value>::infinity(); + } + /// \brief Gives back the sum of the given two elements. + static Value plus(const Value& left, const Value& right) { + return left + right; + } + /// \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 <typename V> + struct BellmanFordDefaultOperationTraits<V, false> { + typedef V Value; + static Value zero() { + return static_cast<Value>(0); + } + static Value infinity() { + return std::numeric_limits<Value>::max(); + } + static Value plus(const Value& left, const Value& right) { + if (left == infinity() || right == infinity()) return infinity(); + return left + right; + } + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + /// \brief Default traits class of BellmanFord class. + /// + /// Default traits class of BellmanFord class. + /// \param GR The type of the digraph. + /// \param LEN The type of the length map. + template<typename GR, typename LEN> + struct BellmanFordDefaultTraits { + /// 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 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 used operations and the infinity value for the + /// given \c Value type. + /// \see BellmanFordDefaultOperationTraits + typedef BellmanFordDefaultOperationTraits<Value> 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 conform to the \ref concepts::WriteMap "WriteMap" concept. + typedef typename GR::template NodeMap<typename GR::Arc> PredMap; + + /// \brief Instantiates a \c 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 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<typename LEN::Value> DistMap; + + /// \brief Instantiates a \c DistMap. + /// + /// This function instantiates a \ref 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); + } + + }; + + /// \brief %BellmanFord algorithm class. + /// + /// \ingroup shortest_path + /// This class provides an efficient implementation of the Bellman-Ford + /// algorithm. The maximum time complexity of the algorithm is + /// <tt>O(nm)</tt>. + /// + /// 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 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<int>". + /// \tparam TR The traits class that defines various types used by the + /// algorithm. By default, it is \ref BellmanFordDefaultTraits + /// "BellmanFordDefaultTraits<GR, LEN>". + /// In most cases, this parameter should not be set directly, + /// consider to use the named template parameters instead. +#ifdef DOXYGEN + template <typename GR, typename LEN, typename TR> +#else + template <typename GR=ListDigraph, + typename LEN=typename GR::template ArcMap<int>, + typename TR=BellmanFordDefaultTraits<GR,LEN> > +#endif + class BellmanFord { + public: + + ///The type of the underlying 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<Digraph, PredMap> Path; + ///\brief The \ref lemon::BellmanFordDefaultOperationTraits + /// "operation traits class" of the algorithm. + typedef typename TR::OperationTraits OperationTraits; + + ///\brief The \ref lemon::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; + + // 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 _pred is locally allocated (true) or not. + bool _local_pred; + // Pointer to the map of distances. + DistMap *_dist; + // Indicates if _dist is locally allocated (true) or not. + bool _local_dist; + + typedef typename Digraph::template NodeMap<bool> MaskMap; + MaskMap *_mask; + + std::vector<Node> _process; + + // Creates the maps if necessary. + void create_maps() { + if(!_pred) { + _local_pred = true; + _pred = Traits::createPredMap(*_gr); + } + if(!_dist) { + _local_dist = true; + _dist = Traits::createDistMap(*_gr); + } + if(!_mask) { + _mask = new MaskMap(*_gr); + } + } + + public : + + typedef BellmanFord Create; + + /// \name Named Template Parameters + + ///@{ + + template <class T> + struct SetPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const Digraph&) { + LEMON_ASSERT(false, "PredMap is not initialized"); + return 0; // ignore warnings + } + }; + + /// \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 <class T> + struct SetPredMap + : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > { + typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create; + }; + + template <class T> + struct SetDistMapTraits : public Traits { + typedef T DistMap; + static DistMap *createDistMap(const Digraph&) { + LEMON_ASSERT(false, "DistMap is not initialized"); + return 0; // ignore warnings + } + }; + + /// \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 <class T> + struct SetDistMap + : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > { + typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create; + }; + + template <class T> + struct SetOperationTraitsTraits : public Traits { + typedef T OperationTraits; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// \c OperationTraits type. + /// + /// \ref named-templ-param "Named parameter" for setting + /// \c OperationTraits type. + /// For more information, see \ref BellmanFordDefaultOperationTraits. + template <class T> + struct SetOperationTraits + : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > { + typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > + Create; + }; + + ///@} + + protected: + + BellmanFord() {} + + public: + + /// \brief Constructor. + /// + /// 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(_mask) delete _mask; + } + + /// \brief Sets the length map. + /// + /// Sets the length map. + /// \return <tt>(*this)</tt> + BellmanFord &lengthMap(const LengthMap &map) { + _length = ↦ + return *this; + } + + /// \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 <tt>(*this)</tt> + BellmanFord &predMap(PredMap &map) { + if(_local_pred) { + delete _pred; + _local_pred=false; + } + _pred = ↦ + return *this; + } + + /// \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 <tt>(*this)</tt> + BellmanFord &distMap(DistMap &map) { + if(_local_dist) { + delete _dist; + _local_dist=false; + } + _dist = ↦ + return *this; + } + + /// \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. The optional parameter + /// is the initial distance of each node. + void init(const Value value = OperationTraits::infinity()) { + create_maps(); + 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(*_gr); it != INVALID; ++it) { + _process.push_back(it); + _mask->set(it, true); + } + } else { + for (NodeIt it(*_gr); it != INVALID; ++it) { + _mask->set(it, false); + } + } + } + + /// \brief Adds a new source node. + /// + /// 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]) { + _process.push_back(source); + _mask->set(source, true); + } + } + + /// \brief Executes one round from the Bellman-Ford algorithm. + /// + /// If the algoritm calculated the distances in the previous round + /// exactly for the paths of at most \c k arcs, then this function + /// will calculate the distances exactly for the paths of at most + /// <tt>k+1</tt> 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 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); + } + std::vector<Node> nextProcess; + std::vector<Value> values(_process.size()); + for (int i = 0; i < int(_process.size()); ++i) { + values[i] = (*_dist)[_process[i]]; + } + for (int i = 0; i < int(_process.size()); ++i) { + 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); + if (!(*_mask)[target]) { + _mask->set(target, true); + nextProcess.push_back(target); + } + } + } + } + _process.swap(nextProcess); + return _process.empty(); + } + + /// \brief Executes one weak round from the Bellman-Ford algorithm. + /// + /// 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 + /// <tt>k+1</tt> 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<Node> nextProcess; + for (int i = 0; i < int(_process.size()); ++i) { + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { + Node target = _gr->target(it); + Value relaxed = + OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); + if (OperationTraits::less(relaxed, (*_dist)[target])) { + _pred->set(target, it); + _dist->set(target, relaxed); + if (!(*_mask)[target]) { + _mask->set(target, true); + nextProcess.push_back(target); + } + } + } + } + _process.swap(nextProcess); + return _process.empty(); + } + + /// \brief Executes the algorithm. + /// + /// 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(*_gr) - 1; + for (int i = 0; i < num; ++i) { + if (processNextWeakRound()) break; + } + } + + /// \brief Executes the algorithm and checks the negative cycles. + /// + /// 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(*_gr); + for (int i = 0; i < num; ++i) { + if (processNextWeakRound()) return true; + } + return _process.empty(); + } + + /// \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 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) { + if (processNextRound()) break; + } + } + + /// \brief Runs the algorithm from the given root node. + /// + /// 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(); + addSource(s); + start(); + } + + /// \brief Runs the algorithm from the given root node with arc + /// number limit. + /// + /// 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(); + addSource(s); + limitedStart(num); + } + + ///@} + + /// \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 getting the active nodes of the given BellmanFord + /// instance. + ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) + { + _index = _algorithm->_process.size() - 1; + } + + /// \brief Invalid constructor. + /// + /// Invalid constructor. + ActiveIt(Invalid) : _algorithm(0), _index(-1) {} + + /// \brief Conversion to \c Node. + /// + /// Conversion to \c Node. + operator Node() const { + return _index >= 0 ? _algorithm->_process[_index] : INVALID; + } + + /// \brief Increment operator. + /// + /// Increment operator. + ActiveIt& operator++() { + --_index; + return *this; + } + + bool operator==(const ActiveIt& it) const { + return static_cast<Node>(*this) == static_cast<Node>(it); + } + bool operator!=(const ActiveIt& it) const { + return static_cast<Node>(*this) != static_cast<Node>(it); + } + bool operator<(const ActiveIt& it) const { + return static_cast<Node>(*this) < static_cast<Node>(it); + } + + private: + 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. + + ///@{ + + /// \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 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 \ref 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 \ref 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(); + } + + /// \brief Gives back a negative cycle. + /// + /// This function gives back a directed cycle with negative total + /// length if the algorithm has already found one. + /// Otherwise it gives back an empty path. + lemon::Path<Digraph> negativeCycle() const { + typename Digraph::template NodeMap<int> state(*_gr, -1); + lemon::Path<Digraph> cycle; + for (int i = 0; i < int(_process.size()); ++i) { + if (state[_process[i]] != -1) continue; + for (Node v = _process[i]; (*_pred)[v] != INVALID; + v = _gr->source((*_pred)[v])) { + if (state[v] == i) { + cycle.addFront((*_pred)[v]); + for (Node u = _gr->source((*_pred)[v]); u != v; + u = _gr->source((*_pred)[u])) { + cycle.addFront((*_pred)[u]); + } + return cycle; + } + else if (state[v] >= 0) { + break; + } + state[v] = i; + } + } + return cycle; + } + + ///@} + }; + + /// \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 <typename GR, typename LEN> + struct BellmanFordWizardDefaultTraits { + /// 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 LEN LengthMap; + + /// The type of the arc lengths. + typedef typename LEN::Value Value; + + /// \brief Operation traits for Bellman-Ford algorithm. + /// + /// It defines the used operations and the infinity value for the + /// given \c Value type. + /// \see BellmanFordDefaultOperationTraits + typedef BellmanFordDefaultOperationTraits<Value> 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 conform to the \ref concepts::WriteMap "WriteMap" concept. + typedef typename GR::template NodeMap<typename GR::Arc> PredMap; + + /// \brief Instantiates a \c 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 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<Value> DistMap; + + /// \brief Instantiates a \c DistMap. + /// + /// This function instantiates a \ref 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<Digraph> Path; + }; + + /// \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 <typename GR, typename LEN> + class BellmanFordWizardBase + : public BellmanFordWizardDefaultTraits<GR, LEN> { + + typedef BellmanFordWizardDefaultTraits<GR, LEN> Base; + protected: + // Type of the nodes in the digraph. + typedef typename Base::Digraph::Node Node; + + // Pointer to the underlying digraph. + void *_graph; + // Pointer to the length map + void *_length; + // Pointer to the map of predecessors arcs. + void *_pred; + // Pointer to the map of distances. + void *_dist; + //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, 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 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<void*>(const_cast<GR*>(&gr))), + _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), + _pred(0), _dist(0), _path(0), _di(0) {} + + }; + + /// \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. + /// + /// \tparam TR The traits class that defines various types used by the + /// algorithm. + template<class TR> + class BellmanFordWizard : public TR { + typedef TR Base; + + 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; + + typedef typename TR::LengthMap LengthMap; + typedef typename LengthMap::Value Value; + typedef typename TR::PredMap PredMap; + typedef typename TR::DistMap DistMap; + typedef typename TR::Path Path; + + public: + /// Constructor. + BellmanFordWizard() : TR() {} + + /// \brief Constructor that requires parameters. + /// + /// Constructor that requires parameters. + /// These parameters will be the default values for the traits class. + /// \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 TR &b) : TR(b) {} + + ~BellmanFordWizard() {} + + /// \brief Runs the Bellman-Ford algorithm from the given source node. + /// + /// 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<Digraph,LengthMap,TR> + bf(*reinterpret_cast<const Digraph*>(Base::_graph), + *reinterpret_cast<const LengthMap*>(Base::_length)); + if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); + if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); + 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<Digraph,LengthMap,TR> + bf(*reinterpret_cast<const Digraph*>(Base::_graph), + *reinterpret_cast<const LengthMap*>(Base::_length)); + if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); + if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); + bf.run(s); + if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t); + if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t); + return bf.reached(t); + } + + template<class T> + struct SetPredMapBase : public Base { + typedef T PredMap; + static PredMap *createPredMap(const Digraph &) { return 0; }; + SetPredMapBase(const TR &b) : TR(b) {} + }; + + /// \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<class T> + BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) { + Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); + return BellmanFordWizard<SetPredMapBase<T> >(*this); + } + + template<class T> + struct SetDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Digraph &) { return 0; }; + SetDistMapBase(const TR &b) : TR(b) {} + }; + + /// \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<class T> + BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) { + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); + return BellmanFordWizard<SetDistMapBase<T> >(*this); + } + + template<class T> + struct SetPathBase : public Base { + typedef T Path; + SetPathBase(const TR &b) : TR(b) {} + }; + + /// \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<class T> + BellmanFordWizard<SetPathBase<T> > path(const T &t) + { + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); + return BellmanFordWizard<SetPathBase<T> >(*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<void*>(const_cast<Value*>(&d)); + return *this; + } + + }; + + /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" + /// algorithm. + /// + /// \ingroup shortest_path + /// 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 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<typename GR, typename LEN> + BellmanFordWizard<BellmanFordWizardBase<GR,LEN> > + bellmanFord(const GR& digraph, + const LEN& length) + { + return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length); + } + +} //END OF NAMESPACE LEMON + +#endif + |