diff --git a/lemon/bellman_ford.h b/lemon/bellman_ford.h --- a/lemon/bellman_ford.h +++ b/lemon/bellman_ford.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -36,7 +36,7 @@ namespace lemon { /// \brief Default operation traits 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. @@ -45,7 +45,7 @@ /// /// \see BellmanFordToleranceOperationTraits template < - typename V, + typename V, bool has_inf = std::numeric_limits::has_infinity> struct BellmanFordDefaultOperationTraits { /// \brief Value type for the algorithm. @@ -86,7 +86,7 @@ return left < right; } }; - + /// \brief Operation traits for the BellmanFord algorithm class /// using tolerance. /// @@ -139,7 +139,7 @@ /// \param LEN The type of the length map. template struct BellmanFordDefaultTraits { - /// The type of the digraph the algorithm runs on. + /// The type of the digraph the algorithm runs on. typedef GR Digraph; /// \brief The type of the map that stores the arc lengths. @@ -158,18 +158,18 @@ /// \see BellmanFordDefaultOperationTraits, /// BellmanFordToleranceOperationTraits typedef BellmanFordDefaultOperationTraits OperationTraits; - - /// \brief The type of the map that stores the last arcs of the + + /// \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 PredMap; /// \brief Instantiates a \c PredMap. - /// - /// This function instantiates a \ref 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) { @@ -184,19 +184,19 @@ /// \brief Instantiates a \c DistMap. /// - /// This function instantiates a \ref DistMap. - /// \param g is the digraph to which we would like to define the + /// 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 + /// This class provides an efficient implementation of the Bellman-Ford /// algorithm. The maximum time complexity of the algorithm is /// O(ne). /// @@ -207,7 +207,7 @@ /// 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 + /// \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. /// @@ -237,7 +237,7 @@ ///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. @@ -284,20 +284,20 @@ // Creates the maps if necessary. void create_maps() { if(!_pred) { - _local_pred = true; - _pred = Traits::createPredMap(*_gr); + _local_pred = true; + _pred = Traits::createPredMap(*_gr); } if(!_dist) { - _local_dist = true; - _dist = Traits::createDistMap(*_gr); + _local_dist = true; + _dist = Traits::createDistMap(*_gr); } if(!_mask) { _mask = new MaskMap(*_gr); } } - + public : - + typedef BellmanFord Create; /// \name Named Template Parameters @@ -320,11 +320,11 @@ /// \c PredMap type. /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. template - struct SetPredMap + struct SetPredMap : public BellmanFord< Digraph, LengthMap, SetPredMapTraits > { typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create; }; - + template struct SetDistMapTraits : public Traits { typedef T DistMap; @@ -341,7 +341,7 @@ /// \c DistMap type. /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. template - struct SetDistMap + struct SetDistMap : public BellmanFord< Digraph, LengthMap, SetDistMapTraits > { typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create; }; @@ -350,8 +350,8 @@ struct SetOperationTraitsTraits : public Traits { typedef T OperationTraits; }; - - /// \brief \ref named-templ-param "Named parameter" for setting + + /// \brief \ref named-templ-param "Named parameter" for setting /// \c OperationTraits type. /// /// \ref named-templ-param "Named parameter" for setting @@ -363,15 +363,15 @@ typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > Create; }; - + ///@} protected: - + BellmanFord() {} - public: - + public: + /// \brief Constructor. /// /// Constructor. @@ -381,7 +381,7 @@ _gr(&g), _length(&length), _pred(0), _local_pred(false), _dist(0), _local_dist(false), _mask(0) {} - + ///Destructor. ~BellmanFord() { if(_local_pred) delete _pred; @@ -408,8 +408,8 @@ /// \return (*this) BellmanFord &predMap(PredMap &map) { if(_local_pred) { - delete _pred; - _local_pred=false; + delete _pred; + _local_pred=false; } _pred = ↦ return *this; @@ -426,8 +426,8 @@ /// \return (*this) BellmanFord &distMap(DistMap &map) { if(_local_dist) { - delete _dist; - _local_dist=false; + delete _dist; + _local_dist=false; } _dist = ↦ return *this; @@ -445,28 +445,28 @@ ///@{ /// \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); + _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); - } + 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); - } + 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 @@ -474,8 +474,8 @@ void addSource(Node source, Value dst = OperationTraits::zero()) { _dist->set(source, dst); if (!(*_mask)[source]) { - _process.push_back(source); - _mask->set(source, true); + _process.push_back(source); + _mask->set(source, true); } } @@ -500,26 +500,26 @@ /// \see ActiveIt bool processNextRound() { for (int i = 0; i < int(_process.size()); ++i) { - _mask->set(_process[i], false); + _mask->set(_process[i], false); } std::vector nextProcess; std::vector values(_process.size()); for (int i = 0; i < int(_process.size()); ++i) { - values[i] = (*_dist)[_process[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); - } - } - } + 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(); @@ -541,23 +541,23 @@ /// \see ActiveIt bool processNextWeakRound() { for (int i = 0; i < int(_process.size()); ++i) { - _mask->set(_process[i], false); + _mask->set(_process[i], false); } std::vector 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); - } - } - } + 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(); @@ -579,7 +579,7 @@ void start() { int num = countNodes(*_gr) - 1; for (int i = 0; i < num; ++i) { - if (processNextWeakRound()) break; + if (processNextWeakRound()) break; } } @@ -591,18 +591,18 @@ /// 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 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. + /// added with addSource() before using this function. bool checkedStart() { int num = countNodes(*_gr); for (int i = 0; i < num; ++i) { - if (processNextWeakRound()) return true; + if (processNextWeakRound()) return true; } return _process.empty(); } @@ -626,15 +626,15 @@ /// 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. + /// added with addSource() before using this function. void limitedStart(int num) { for (int i = 0; i < num; ++i) { - if (processNextRound()) break; + 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. /// @@ -653,10 +653,10 @@ 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. @@ -682,7 +682,7 @@ addSource(s); limitedStart(num); } - + ///@} /// \brief LEMON iterator for getting the active nodes. @@ -697,7 +697,7 @@ /// \brief Constructor. /// /// Constructor for getting the active nodes of the given BellmanFord - /// instance. + /// instance. ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) { _index = _algorithm->_process.size() - 1; @@ -711,7 +711,7 @@ /// \brief Conversion to \c Node. /// /// Conversion to \c Node. - operator Node() const { + operator Node() const { return _index >= 0 ? _algorithm->_process[_index] : INVALID; } @@ -720,33 +720,33 @@ /// Increment operator. ActiveIt& operator++() { --_index; - return *this; + return *this; } - bool operator==(const ActiveIt& it) const { - return static_cast(*this) == static_cast(it); + bool operator==(const ActiveIt& it) const { + return static_cast(*this) == static_cast(it); } - bool operator!=(const ActiveIt& it) const { - return static_cast(*this) != static_cast(it); + bool operator!=(const ActiveIt& it) const { + return static_cast(*this) != static_cast(it); } - bool operator<(const ActiveIt& it) const { - return static_cast(*this) < static_cast(it); + bool operator<(const ActiveIt& it) const { + return static_cast(*this) < static_cast(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). @@ -757,7 +757,7 @@ { 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). @@ -797,10 +797,10 @@ /// /// \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]); + 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. /// @@ -810,7 +810,7 @@ /// \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. /// @@ -820,7 +820,7 @@ /// \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). @@ -832,7 +832,7 @@ } /// \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. @@ -859,10 +859,10 @@ } return cycle; } - + ///@} }; - + /// \brief Default traits class of bellmanFord() function. /// /// Default traits class of bellmanFord() function. @@ -870,7 +870,7 @@ /// \tparam LEN The type of the length map. template struct BellmanFordWizardDefaultTraits { - /// The type of the digraph the algorithm runs on. + /// The type of the digraph the algorithm runs on. typedef GR Digraph; /// \brief The type of the map that stores the arc lengths. @@ -892,13 +892,13 @@ /// \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 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. @@ -914,7 +914,7 @@ /// \brief Instantiates a \c DistMap. /// - /// This function instantiates a \ref 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) { @@ -927,14 +927,14 @@ ///It must meet the \ref concepts::Path "Path" concept. typedef lemon::Path 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 - class BellmanFordWizardBase + class BellmanFordWizardBase : public BellmanFordWizardDefaultTraits { typedef BellmanFordWizardDefaultTraits Base; @@ -957,26 +957,26 @@ 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(const_cast(&gr))), - _length(reinterpret_cast(const_cast(&len))), + 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) {} }; - + /// \brief Auxiliary class for the function-type interface of the /// \ref BellmanFord "Bellman-Ford" algorithm. /// @@ -1001,7 +1001,7 @@ 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; @@ -1018,7 +1018,7 @@ /// 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) + BellmanFordWizard(const Digraph& gr, const LengthMap& len) : TR(gr, len) {} /// \brief Copy constructor @@ -1027,12 +1027,12 @@ ~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 - bf(*reinterpret_cast(Base::_graph), + 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)); @@ -1067,7 +1067,7 @@ 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. /// @@ -1078,14 +1078,14 @@ Base::_pred=reinterpret_cast(const_cast(&t)); return BellmanFordWizard >(*this); } - + template 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. /// @@ -1126,9 +1126,9 @@ Base::_di=reinterpret_cast(const_cast(&d)); return *this; } - + }; - + /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" /// algorithm. /// @@ -1136,8 +1136,8 @@ /// 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 + /// 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 @@ -1154,7 +1154,7 @@ template BellmanFordWizard > bellmanFord(const GR& digraph, - const LEN& length) + const LEN& length) { return BellmanFordWizard >(digraph, length); }