lemon/bellman_ford.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 06 Aug 2013 12:28:37 +0200
changeset 1079 5958cc5c0a98
parent 880 b89e46862dc2
child 1080 c5cd8960df74
permissions -rw-r--r--
Merge further fixes #470
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BELLMAN_FORD_H
    20 #define LEMON_BELLMAN_FORD_H
    21 
    22 /// \ingroup shortest_path
    23 /// \file
    24 /// \brief Bellman-Ford algorithm.
    25 
    26 #include <lemon/list_graph.h>
    27 #include <lemon/bits/path_dump.h>
    28 #include <lemon/core.h>
    29 #include <lemon/error.h>
    30 #include <lemon/maps.h>
    31 #include <lemon/path.h>
    32 
    33 #include <limits>
    34 
    35 namespace lemon {
    36 
    37   /// \brief Default OperationTraits for the BellmanFord algorithm class.
    38   ///
    39   /// This operation traits class defines all computational operations
    40   /// and constants that are used in the Bellman-Ford algorithm.
    41   /// The default implementation is based on the \c numeric_limits class.
    42   /// If the numeric type does not have infinity value, then the maximum
    43   /// value is used as extremal infinity value.
    44   template <
    45     typename V,
    46     bool has_inf = std::numeric_limits<V>::has_infinity>
    47   struct BellmanFordDefaultOperationTraits {
    48     /// \e
    49     typedef V Value;
    50     /// \brief Gives back the zero value of the type.
    51     static Value zero() {
    52       return static_cast<Value>(0);
    53     }
    54     /// \brief Gives back the positive infinity value of the type.
    55     static Value infinity() {
    56       return std::numeric_limits<Value>::infinity();
    57     }
    58     /// \brief Gives back the sum of the given two elements.
    59     static Value plus(const Value& left, const Value& right) {
    60       return left + right;
    61     }
    62     /// \brief Gives back \c true only if the first value is less than
    63     /// the second.
    64     static bool less(const Value& left, const Value& right) {
    65       return left < right;
    66     }
    67   };
    68 
    69   template <typename V>
    70   struct BellmanFordDefaultOperationTraits<V, false> {
    71     typedef V Value;
    72     static Value zero() {
    73       return static_cast<Value>(0);
    74     }
    75     static Value infinity() {
    76       return std::numeric_limits<Value>::max();
    77     }
    78     static Value plus(const Value& left, const Value& right) {
    79       if (left == infinity() || right == infinity()) return infinity();
    80       return left + right;
    81     }
    82     static bool less(const Value& left, const Value& right) {
    83       return left < right;
    84     }
    85   };
    86 
    87   /// \brief Default traits class of BellmanFord class.
    88   ///
    89   /// Default traits class of BellmanFord class.
    90   /// \param GR The type of the digraph.
    91   /// \param LEN The type of the length map.
    92   template<typename GR, typename LEN>
    93   struct BellmanFordDefaultTraits {
    94     /// The type of the digraph the algorithm runs on.
    95     typedef GR Digraph;
    96 
    97     /// \brief The type of the map that stores the arc lengths.
    98     ///
    99     /// The type of the map that stores the arc lengths.
   100     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
   101     typedef LEN LengthMap;
   102 
   103     /// The type of the arc lengths.
   104     typedef typename LEN::Value Value;
   105 
   106     /// \brief Operation traits for Bellman-Ford algorithm.
   107     ///
   108     /// It defines the used operations and the infinity value for the
   109     /// given \c Value type.
   110     /// \see BellmanFordDefaultOperationTraits
   111     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   112 
   113     /// \brief The type of the map that stores the last arcs of the
   114     /// shortest paths.
   115     ///
   116     /// The type of the map that stores the last
   117     /// arcs of the shortest paths.
   118     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   119     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   120 
   121     /// \brief Instantiates a \c PredMap.
   122     ///
   123     /// This function instantiates a \ref PredMap.
   124     /// \param g is the digraph to which we would like to define the
   125     /// \ref PredMap.
   126     static PredMap *createPredMap(const GR& g) {
   127       return new PredMap(g);
   128     }
   129 
   130     /// \brief The type of the map that stores the distances of the nodes.
   131     ///
   132     /// The type of the map that stores the distances of the nodes.
   133     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   134     typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
   135 
   136     /// \brief Instantiates a \c DistMap.
   137     ///
   138     /// This function instantiates a \ref DistMap.
   139     /// \param g is the digraph to which we would like to define the
   140     /// \ref DistMap.
   141     static DistMap *createDistMap(const GR& g) {
   142       return new DistMap(g);
   143     }
   144 
   145   };
   146 
   147   /// \brief %BellmanFord algorithm class.
   148   ///
   149   /// \ingroup shortest_path
   150   /// This class provides an efficient implementation of the Bellman-Ford
   151   /// algorithm. The maximum time complexity of the algorithm is
   152   /// <tt>O(ne)</tt>.
   153   ///
   154   /// The Bellman-Ford algorithm solves the single-source shortest path
   155   /// problem when the arcs can have negative lengths, but the digraph
   156   /// should not contain directed cycles with negative total length.
   157   /// If all arc costs are non-negative, consider to use the Dijkstra
   158   /// algorithm instead, since it is more efficient.
   159   ///
   160   /// The arc lengths are passed to the algorithm using a
   161   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
   162   /// kind of length. The type of the length values is determined by the
   163   /// \ref concepts::ReadMap::Value "Value" type of the length map.
   164   ///
   165   /// There is also a \ref bellmanFord() "function-type interface" for the
   166   /// Bellman-Ford algorithm, which is convenient in the simplier cases and
   167   /// it can be used easier.
   168   ///
   169   /// \tparam GR The type of the digraph the algorithm runs on.
   170   /// The default type is \ref ListDigraph.
   171   /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
   172   /// the lengths of the arcs. The default map type is
   173   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   174   /// \tparam TR The traits class that defines various types used by the
   175   /// algorithm. By default, it is \ref BellmanFordDefaultTraits
   176   /// "BellmanFordDefaultTraits<GR, LEN>".
   177   /// In most cases, this parameter should not be set directly,
   178   /// consider to use the named template parameters instead.
   179 #ifdef DOXYGEN
   180   template <typename GR, typename LEN, typename TR>
   181 #else
   182   template <typename GR=ListDigraph,
   183             typename LEN=typename GR::template ArcMap<int>,
   184             typename TR=BellmanFordDefaultTraits<GR,LEN> >
   185 #endif
   186   class BellmanFord {
   187   public:
   188 
   189     ///The type of the underlying digraph.
   190     typedef typename TR::Digraph Digraph;
   191 
   192     /// \brief The type of the arc lengths.
   193     typedef typename TR::LengthMap::Value Value;
   194     /// \brief The type of the map that stores the arc lengths.
   195     typedef typename TR::LengthMap LengthMap;
   196     /// \brief The type of the map that stores the last
   197     /// arcs of the shortest paths.
   198     typedef typename TR::PredMap PredMap;
   199     /// \brief The type of the map that stores the distances of the nodes.
   200     typedef typename TR::DistMap DistMap;
   201     /// The type of the paths.
   202     typedef PredMapPath<Digraph, PredMap> Path;
   203     ///\brief The \ref lemon::BellmanFordDefaultOperationTraits
   204     /// "operation traits class" of the algorithm.
   205     typedef typename TR::OperationTraits OperationTraits;
   206 
   207     ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class"
   208     ///of the algorithm.
   209     typedef TR Traits;
   210 
   211   private:
   212 
   213     typedef typename Digraph::Node Node;
   214     typedef typename Digraph::NodeIt NodeIt;
   215     typedef typename Digraph::Arc Arc;
   216     typedef typename Digraph::OutArcIt OutArcIt;
   217 
   218     // Pointer to the underlying digraph.
   219     const Digraph *_gr;
   220     // Pointer to the length map
   221     const LengthMap *_length;
   222     // Pointer to the map of predecessors arcs.
   223     PredMap *_pred;
   224     // Indicates if _pred is locally allocated (true) or not.
   225     bool _local_pred;
   226     // Pointer to the map of distances.
   227     DistMap *_dist;
   228     // Indicates if _dist is locally allocated (true) or not.
   229     bool _local_dist;
   230 
   231     typedef typename Digraph::template NodeMap<bool> MaskMap;
   232     MaskMap *_mask;
   233 
   234     std::vector<Node> _process;
   235 
   236     // Creates the maps if necessary.
   237     void create_maps() {
   238       if(!_pred) {
   239         _local_pred = true;
   240         _pred = Traits::createPredMap(*_gr);
   241       }
   242       if(!_dist) {
   243         _local_dist = true;
   244         _dist = Traits::createDistMap(*_gr);
   245       }
   246       if(!_mask) {
   247         _mask = new MaskMap(*_gr);
   248       }
   249     }
   250 
   251   public :
   252 
   253     typedef BellmanFord Create;
   254 
   255     /// \name Named Template Parameters
   256 
   257     ///@{
   258 
   259     template <class T>
   260     struct SetPredMapTraits : public Traits {
   261       typedef T PredMap;
   262       static PredMap *createPredMap(const Digraph&) {
   263         LEMON_ASSERT(false, "PredMap is not initialized");
   264         return 0; // ignore warnings
   265       }
   266     };
   267 
   268     /// \brief \ref named-templ-param "Named parameter" for setting
   269     /// \c PredMap type.
   270     ///
   271     /// \ref named-templ-param "Named parameter" for setting
   272     /// \c PredMap type.
   273     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   274     template <class T>
   275     struct SetPredMap
   276       : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
   277       typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   278     };
   279 
   280     template <class T>
   281     struct SetDistMapTraits : public Traits {
   282       typedef T DistMap;
   283       static DistMap *createDistMap(const Digraph&) {
   284         LEMON_ASSERT(false, "DistMap is not initialized");
   285         return 0; // ignore warnings
   286       }
   287     };
   288 
   289     /// \brief \ref named-templ-param "Named parameter" for setting
   290     /// \c DistMap type.
   291     ///
   292     /// \ref named-templ-param "Named parameter" for setting
   293     /// \c DistMap type.
   294     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   295     template <class T>
   296     struct SetDistMap
   297       : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
   298       typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   299     };
   300 
   301     template <class T>
   302     struct SetOperationTraitsTraits : public Traits {
   303       typedef T OperationTraits;
   304     };
   305 
   306     /// \brief \ref named-templ-param "Named parameter" for setting
   307     /// \c OperationTraits type.
   308     ///
   309     /// \ref named-templ-param "Named parameter" for setting
   310     /// \c OperationTraits type.
   311     /// For more information, see \ref BellmanFordDefaultOperationTraits.
   312     template <class T>
   313     struct SetOperationTraits
   314       : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   315       typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
   316       Create;
   317     };
   318 
   319     ///@}
   320 
   321   protected:
   322 
   323     BellmanFord() {}
   324 
   325   public:
   326 
   327     /// \brief Constructor.
   328     ///
   329     /// Constructor.
   330     /// \param g The digraph the algorithm runs on.
   331     /// \param length The length map used by the algorithm.
   332     BellmanFord(const Digraph& g, const LengthMap& length) :
   333       _gr(&g), _length(&length),
   334       _pred(0), _local_pred(false),
   335       _dist(0), _local_dist(false), _mask(0) {}
   336 
   337     ///Destructor.
   338     ~BellmanFord() {
   339       if(_local_pred) delete _pred;
   340       if(_local_dist) delete _dist;
   341       if(_mask) delete _mask;
   342     }
   343 
   344     /// \brief Sets the length map.
   345     ///
   346     /// Sets the length map.
   347     /// \return <tt>(*this)</tt>
   348     BellmanFord &lengthMap(const LengthMap &map) {
   349       _length = &map;
   350       return *this;
   351     }
   352 
   353     /// \brief Sets the map that stores the predecessor arcs.
   354     ///
   355     /// Sets the map that stores the predecessor arcs.
   356     /// If you don't use this function before calling \ref run()
   357     /// or \ref init(), an instance will be allocated automatically.
   358     /// The destructor deallocates this automatically allocated map,
   359     /// of course.
   360     /// \return <tt>(*this)</tt>
   361     BellmanFord &predMap(PredMap &map) {
   362       if(_local_pred) {
   363         delete _pred;
   364         _local_pred=false;
   365       }
   366       _pred = &map;
   367       return *this;
   368     }
   369 
   370     /// \brief Sets the map that stores the distances of the nodes.
   371     ///
   372     /// Sets the map that stores the distances of the nodes calculated
   373     /// by the algorithm.
   374     /// If you don't use this function before calling \ref run()
   375     /// or \ref init(), an instance will be allocated automatically.
   376     /// The destructor deallocates this automatically allocated map,
   377     /// of course.
   378     /// \return <tt>(*this)</tt>
   379     BellmanFord &distMap(DistMap &map) {
   380       if(_local_dist) {
   381         delete _dist;
   382         _local_dist=false;
   383       }
   384       _dist = &map;
   385       return *this;
   386     }
   387 
   388     /// \name Execution Control
   389     /// The simplest way to execute the Bellman-Ford algorithm is to use
   390     /// one of the member functions called \ref run().\n
   391     /// If you need better control on the execution, you have to call
   392     /// \ref init() first, then you can add several source nodes
   393     /// with \ref addSource(). Finally the actual path computation can be
   394     /// performed with \ref start(), \ref checkedStart() or
   395     /// \ref limitedStart().
   396 
   397     ///@{
   398 
   399     /// \brief Initializes the internal data structures.
   400     ///
   401     /// Initializes the internal data structures. The optional parameter
   402     /// is the initial distance of each node.
   403     void init(const Value value = OperationTraits::infinity()) {
   404       create_maps();
   405       for (NodeIt it(*_gr); it != INVALID; ++it) {
   406         _pred->set(it, INVALID);
   407         _dist->set(it, value);
   408       }
   409       _process.clear();
   410       if (OperationTraits::less(value, OperationTraits::infinity())) {
   411         for (NodeIt it(*_gr); it != INVALID; ++it) {
   412           _process.push_back(it);
   413           _mask->set(it, true);
   414         }
   415       } else {
   416         for (NodeIt it(*_gr); it != INVALID; ++it) {
   417           _mask->set(it, false);
   418         }
   419       }
   420     }
   421 
   422     /// \brief Adds a new source node.
   423     ///
   424     /// This function adds a new source node. The optional second parameter
   425     /// is the initial distance of the node.
   426     void addSource(Node source, Value dst = OperationTraits::zero()) {
   427       _dist->set(source, dst);
   428       if (!(*_mask)[source]) {
   429         _process.push_back(source);
   430         _mask->set(source, true);
   431       }
   432     }
   433 
   434     /// \brief Executes one round from the Bellman-Ford algorithm.
   435     ///
   436     /// If the algoritm calculated the distances in the previous round
   437     /// exactly for the paths of at most \c k arcs, then this function
   438     /// will calculate the distances exactly for the paths of at most
   439     /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
   440     /// calculates the shortest path distances exactly for the paths
   441     /// consisting of at most \c k arcs.
   442     ///
   443     /// \warning The paths with limited arc number cannot be retrieved
   444     /// easily with \ref path() or \ref predArc() functions. If you also
   445     /// need the shortest paths and not only the distances, you should
   446     /// store the \ref predMap() "predecessor map" after each iteration
   447     /// and build the path manually.
   448     ///
   449     /// \return \c true when the algorithm have not found more shorter
   450     /// paths.
   451     ///
   452     /// \see ActiveIt
   453     bool processNextRound() {
   454       for (int i = 0; i < int(_process.size()); ++i) {
   455         _mask->set(_process[i], false);
   456       }
   457       std::vector<Node> nextProcess;
   458       std::vector<Value> values(_process.size());
   459       for (int i = 0; i < int(_process.size()); ++i) {
   460         values[i] = (*_dist)[_process[i]];
   461       }
   462       for (int i = 0; i < int(_process.size()); ++i) {
   463         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   464           Node target = _gr->target(it);
   465           Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
   466           if (OperationTraits::less(relaxed, (*_dist)[target])) {
   467             _pred->set(target, it);
   468             _dist->set(target, relaxed);
   469             if (!(*_mask)[target]) {
   470               _mask->set(target, true);
   471               nextProcess.push_back(target);
   472             }
   473           }
   474         }
   475       }
   476       _process.swap(nextProcess);
   477       return _process.empty();
   478     }
   479 
   480     /// \brief Executes one weak round from the Bellman-Ford algorithm.
   481     ///
   482     /// If the algorithm calculated the distances in the previous round
   483     /// at least for the paths of at most \c k arcs, then this function
   484     /// will calculate the distances at least for the paths of at most
   485     /// <tt>k+1</tt> arcs.
   486     /// This function does not make it possible to calculate the shortest
   487     /// path distances exactly for paths consisting of at most \c k arcs,
   488     /// this is why it is called weak round.
   489     ///
   490     /// \return \c true when the algorithm have not found more shorter
   491     /// paths.
   492     ///
   493     /// \see ActiveIt
   494     bool processNextWeakRound() {
   495       for (int i = 0; i < int(_process.size()); ++i) {
   496         _mask->set(_process[i], false);
   497       }
   498       std::vector<Node> nextProcess;
   499       for (int i = 0; i < int(_process.size()); ++i) {
   500         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   501           Node target = _gr->target(it);
   502           Value relaxed =
   503             OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
   504           if (OperationTraits::less(relaxed, (*_dist)[target])) {
   505             _pred->set(target, it);
   506             _dist->set(target, relaxed);
   507             if (!(*_mask)[target]) {
   508               _mask->set(target, true);
   509               nextProcess.push_back(target);
   510             }
   511           }
   512         }
   513       }
   514       _process.swap(nextProcess);
   515       return _process.empty();
   516     }
   517 
   518     /// \brief Executes the algorithm.
   519     ///
   520     /// Executes the algorithm.
   521     ///
   522     /// This method runs the Bellman-Ford algorithm from the root node(s)
   523     /// in order to compute the shortest path to each node.
   524     ///
   525     /// The algorithm computes
   526     /// - the shortest path tree (forest),
   527     /// - the distance of each node from the root(s).
   528     ///
   529     /// \pre init() must be called and at least one root node should be
   530     /// added with addSource() before using this function.
   531     void start() {
   532       int num = countNodes(*_gr) - 1;
   533       for (int i = 0; i < num; ++i) {
   534         if (processNextWeakRound()) break;
   535       }
   536     }
   537 
   538     /// \brief Executes the algorithm and checks the negative cycles.
   539     ///
   540     /// Executes the algorithm and checks the negative cycles.
   541     ///
   542     /// This method runs the Bellman-Ford algorithm from the root node(s)
   543     /// in order to compute the shortest path to each node and also checks
   544     /// if the digraph contains cycles with negative total length.
   545     ///
   546     /// The algorithm computes
   547     /// - the shortest path tree (forest),
   548     /// - the distance of each node from the root(s).
   549     ///
   550     /// \return \c false if there is a negative cycle in the digraph.
   551     ///
   552     /// \pre init() must be called and at least one root node should be
   553     /// added with addSource() before using this function.
   554     bool checkedStart() {
   555       int num = countNodes(*_gr);
   556       for (int i = 0; i < num; ++i) {
   557         if (processNextWeakRound()) return true;
   558       }
   559       return _process.empty();
   560     }
   561 
   562     /// \brief Executes the algorithm with arc number limit.
   563     ///
   564     /// Executes the algorithm with arc number limit.
   565     ///
   566     /// This method runs the Bellman-Ford algorithm from the root node(s)
   567     /// in order to compute the shortest path distance for each node
   568     /// using only the paths consisting of at most \c num arcs.
   569     ///
   570     /// The algorithm computes
   571     /// - the limited distance of each node from the root(s),
   572     /// - the predecessor arc for each node.
   573     ///
   574     /// \warning The paths with limited arc number cannot be retrieved
   575     /// easily with \ref path() or \ref predArc() functions. If you also
   576     /// need the shortest paths and not only the distances, you should
   577     /// store the \ref predMap() "predecessor map" after each iteration
   578     /// and build the path manually.
   579     ///
   580     /// \pre init() must be called and at least one root node should be
   581     /// added with addSource() before using this function.
   582     void limitedStart(int num) {
   583       for (int i = 0; i < num; ++i) {
   584         if (processNextRound()) break;
   585       }
   586     }
   587 
   588     /// \brief Runs the algorithm from the given root node.
   589     ///
   590     /// This method runs the Bellman-Ford algorithm from the given root
   591     /// node \c s in order to compute the shortest path to each node.
   592     ///
   593     /// The algorithm computes
   594     /// - the shortest path tree (forest),
   595     /// - the distance of each node from the root(s).
   596     ///
   597     /// \note bf.run(s) is just a shortcut of the following code.
   598     /// \code
   599     ///   bf.init();
   600     ///   bf.addSource(s);
   601     ///   bf.start();
   602     /// \endcode
   603     void run(Node s) {
   604       init();
   605       addSource(s);
   606       start();
   607     }
   608 
   609     /// \brief Runs the algorithm from the given root node with arc
   610     /// number limit.
   611     ///
   612     /// This method runs the Bellman-Ford algorithm from the given root
   613     /// node \c s in order to compute the shortest path distance for each
   614     /// node using only the paths consisting of at most \c num arcs.
   615     ///
   616     /// The algorithm computes
   617     /// - the limited distance of each node from the root(s),
   618     /// - the predecessor arc for each node.
   619     ///
   620     /// \warning The paths with limited arc number cannot be retrieved
   621     /// easily with \ref path() or \ref predArc() functions. If you also
   622     /// need the shortest paths and not only the distances, you should
   623     /// store the \ref predMap() "predecessor map" after each iteration
   624     /// and build the path manually.
   625     ///
   626     /// \note bf.run(s, num) is just a shortcut of the following code.
   627     /// \code
   628     ///   bf.init();
   629     ///   bf.addSource(s);
   630     ///   bf.limitedStart(num);
   631     /// \endcode
   632     void run(Node s, int num) {
   633       init();
   634       addSource(s);
   635       limitedStart(num);
   636     }
   637 
   638     ///@}
   639 
   640     /// \brief LEMON iterator for getting the active nodes.
   641     ///
   642     /// This class provides a common style LEMON iterator that traverses
   643     /// the active nodes of the Bellman-Ford algorithm after the last
   644     /// phase. These nodes should be checked in the next phase to
   645     /// find augmenting arcs outgoing from them.
   646     class ActiveIt {
   647     public:
   648 
   649       /// \brief Constructor.
   650       ///
   651       /// Constructor for getting the active nodes of the given BellmanFord
   652       /// instance.
   653       ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
   654       {
   655         _index = _algorithm->_process.size() - 1;
   656       }
   657 
   658       /// \brief Invalid constructor.
   659       ///
   660       /// Invalid constructor.
   661       ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
   662 
   663       /// \brief Conversion to \c Node.
   664       ///
   665       /// Conversion to \c Node.
   666       operator Node() const {
   667         return _index >= 0 ? _algorithm->_process[_index] : INVALID;
   668       }
   669 
   670       /// \brief Increment operator.
   671       ///
   672       /// Increment operator.
   673       ActiveIt& operator++() {
   674         --_index;
   675         return *this;
   676       }
   677 
   678       bool operator==(const ActiveIt& it) const {
   679         return static_cast<Node>(*this) == static_cast<Node>(it);
   680       }
   681       bool operator!=(const ActiveIt& it) const {
   682         return static_cast<Node>(*this) != static_cast<Node>(it);
   683       }
   684       bool operator<(const ActiveIt& it) const {
   685         return static_cast<Node>(*this) < static_cast<Node>(it);
   686       }
   687 
   688     private:
   689       const BellmanFord* _algorithm;
   690       int _index;
   691     };
   692 
   693     /// \name Query Functions
   694     /// The result of the Bellman-Ford algorithm can be obtained using these
   695     /// functions.\n
   696     /// Either \ref run() or \ref init() should be called before using them.
   697 
   698     ///@{
   699 
   700     /// \brief The shortest path to the given node.
   701     ///
   702     /// Gives back the shortest path to the given node from the root(s).
   703     ///
   704     /// \warning \c t should be reached from the root(s).
   705     ///
   706     /// \pre Either \ref run() or \ref init() must be called before
   707     /// using this function.
   708     Path path(Node t) const
   709     {
   710       return Path(*_gr, *_pred, t);
   711     }
   712 
   713     /// \brief The distance of the given node from the root(s).
   714     ///
   715     /// Returns the distance of the given node from the root(s).
   716     ///
   717     /// \warning If node \c v is not reached from the root(s), then
   718     /// the return value of this function is undefined.
   719     ///
   720     /// \pre Either \ref run() or \ref init() must be called before
   721     /// using this function.
   722     Value dist(Node v) const { return (*_dist)[v]; }
   723 
   724     /// \brief Returns the 'previous arc' of the shortest path tree for
   725     /// the given node.
   726     ///
   727     /// This function returns the 'previous arc' of the shortest path
   728     /// tree for node \c v, i.e. it returns the last arc of a
   729     /// shortest path from a root to \c v. It is \c INVALID if \c v
   730     /// is not reached from the root(s) or if \c v is a root.
   731     ///
   732     /// The shortest path tree used here is equal to the shortest path
   733     /// tree used in \ref predNode() and \ref predMap().
   734     ///
   735     /// \pre Either \ref run() or \ref init() must be called before
   736     /// using this function.
   737     Arc predArc(Node v) const { return (*_pred)[v]; }
   738 
   739     /// \brief Returns the 'previous node' of the shortest path tree for
   740     /// the given node.
   741     ///
   742     /// This function returns the 'previous node' of the shortest path
   743     /// tree for node \c v, i.e. it returns the last but one node of
   744     /// a shortest path from a root to \c v. It is \c INVALID if \c v
   745     /// is not reached from the root(s) or if \c v is a root.
   746     ///
   747     /// The shortest path tree used here is equal to the shortest path
   748     /// tree used in \ref predArc() and \ref predMap().
   749     ///
   750     /// \pre Either \ref run() or \ref init() must be called before
   751     /// using this function.
   752     Node predNode(Node v) const {
   753       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
   754     }
   755 
   756     /// \brief Returns a const reference to the node map that stores the
   757     /// distances of the nodes.
   758     ///
   759     /// Returns a const reference to the node map that stores the distances
   760     /// of the nodes calculated by the algorithm.
   761     ///
   762     /// \pre Either \ref run() or \ref init() must be called before
   763     /// using this function.
   764     const DistMap &distMap() const { return *_dist;}
   765 
   766     /// \brief Returns a const reference to the node map that stores the
   767     /// predecessor arcs.
   768     ///
   769     /// Returns a const reference to the node map that stores the predecessor
   770     /// arcs, which form the shortest path tree (forest).
   771     ///
   772     /// \pre Either \ref run() or \ref init() must be called before
   773     /// using this function.
   774     const PredMap &predMap() const { return *_pred; }
   775 
   776     /// \brief Checks if a node is reached from the root(s).
   777     ///
   778     /// Returns \c true if \c v is reached from the root(s).
   779     ///
   780     /// \pre Either \ref run() or \ref init() must be called before
   781     /// using this function.
   782     bool reached(Node v) const {
   783       return (*_dist)[v] != OperationTraits::infinity();
   784     }
   785 
   786     /// \brief Gives back a negative cycle.
   787     ///
   788     /// This function gives back a directed cycle with negative total
   789     /// length if the algorithm has already found one.
   790     /// Otherwise it gives back an empty path.
   791     lemon::Path<Digraph> negativeCycle() const {
   792       typename Digraph::template NodeMap<int> state(*_gr, -1);
   793       lemon::Path<Digraph> cycle;
   794       for (int i = 0; i < int(_process.size()); ++i) {
   795         if (state[_process[i]] != -1) continue;
   796         for (Node v = _process[i]; (*_pred)[v] != INVALID;
   797              v = _gr->source((*_pred)[v])) {
   798           if (state[v] == i) {
   799             cycle.addFront((*_pred)[v]);
   800             for (Node u = _gr->source((*_pred)[v]); u != v;
   801                  u = _gr->source((*_pred)[u])) {
   802               cycle.addFront((*_pred)[u]);
   803             }
   804             return cycle;
   805           }
   806           else if (state[v] >= 0) {
   807             break;
   808           }
   809           state[v] = i;
   810         }
   811       }
   812       return cycle;
   813     }
   814 
   815     ///@}
   816   };
   817 
   818   /// \brief Default traits class of bellmanFord() function.
   819   ///
   820   /// Default traits class of bellmanFord() function.
   821   /// \tparam GR The type of the digraph.
   822   /// \tparam LEN The type of the length map.
   823   template <typename GR, typename LEN>
   824   struct BellmanFordWizardDefaultTraits {
   825     /// The type of the digraph the algorithm runs on.
   826     typedef GR Digraph;
   827 
   828     /// \brief The type of the map that stores the arc lengths.
   829     ///
   830     /// The type of the map that stores the arc lengths.
   831     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
   832     typedef LEN LengthMap;
   833 
   834     /// The type of the arc lengths.
   835     typedef typename LEN::Value Value;
   836 
   837     /// \brief Operation traits for Bellman-Ford algorithm.
   838     ///
   839     /// It defines the used operations and the infinity value for the
   840     /// given \c Value type.
   841     /// \see BellmanFordDefaultOperationTraits
   842     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   843 
   844     /// \brief The type of the map that stores the last
   845     /// arcs of the shortest paths.
   846     ///
   847     /// The type of the map that stores the last arcs of the shortest paths.
   848     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   849     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   850 
   851     /// \brief Instantiates a \c PredMap.
   852     ///
   853     /// This function instantiates a \ref PredMap.
   854     /// \param g is the digraph to which we would like to define the
   855     /// \ref PredMap.
   856     static PredMap *createPredMap(const GR &g) {
   857       return new PredMap(g);
   858     }
   859 
   860     /// \brief The type of the map that stores the distances of the nodes.
   861     ///
   862     /// The type of the map that stores the distances of the nodes.
   863     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   864     typedef typename GR::template NodeMap<Value> DistMap;
   865 
   866     /// \brief Instantiates a \c DistMap.
   867     ///
   868     /// This function instantiates a \ref DistMap.
   869     /// \param g is the digraph to which we would like to define the
   870     /// \ref DistMap.
   871     static DistMap *createDistMap(const GR &g) {
   872       return new DistMap(g);
   873     }
   874 
   875     ///The type of the shortest paths.
   876 
   877     ///The type of the shortest paths.
   878     ///It must meet the \ref concepts::Path "Path" concept.
   879     typedef lemon::Path<Digraph> Path;
   880   };
   881 
   882   /// \brief Default traits class used by BellmanFordWizard.
   883   ///
   884   /// Default traits class used by BellmanFordWizard.
   885   /// \tparam GR The type of the digraph.
   886   /// \tparam LEN The type of the length map.
   887   template <typename GR, typename LEN>
   888   class BellmanFordWizardBase
   889     : public BellmanFordWizardDefaultTraits<GR, LEN> {
   890 
   891     typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
   892   protected:
   893     // Type of the nodes in the digraph.
   894     typedef typename Base::Digraph::Node Node;
   895 
   896     // Pointer to the underlying digraph.
   897     void *_graph;
   898     // Pointer to the length map
   899     void *_length;
   900     // Pointer to the map of predecessors arcs.
   901     void *_pred;
   902     // Pointer to the map of distances.
   903     void *_dist;
   904     //Pointer to the shortest path to the target node.
   905     void *_path;
   906     //Pointer to the distance of the target node.
   907     void *_di;
   908 
   909     public:
   910     /// Constructor.
   911 
   912     /// This constructor does not require parameters, it initiates
   913     /// all of the attributes to default values \c 0.
   914     BellmanFordWizardBase() :
   915       _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
   916 
   917     /// Constructor.
   918 
   919     /// This constructor requires two parameters,
   920     /// others are initiated to \c 0.
   921     /// \param gr The digraph the algorithm runs on.
   922     /// \param len The length map.
   923     BellmanFordWizardBase(const GR& gr,
   924                           const LEN& len) :
   925       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
   926       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
   927       _pred(0), _dist(0), _path(0), _di(0) {}
   928 
   929   };
   930 
   931   /// \brief Auxiliary class for the function-type interface of the
   932   /// \ref BellmanFord "Bellman-Ford" algorithm.
   933   ///
   934   /// This auxiliary class is created to implement the
   935   /// \ref bellmanFord() "function-type interface" of the
   936   /// \ref BellmanFord "Bellman-Ford" algorithm.
   937   /// It does not have own \ref run() method, it uses the
   938   /// functions and features of the plain \ref BellmanFord.
   939   ///
   940   /// This class should only be used through the \ref bellmanFord()
   941   /// function, which makes it easier to use the algorithm.
   942   ///
   943   /// \tparam TR The traits class that defines various types used by the
   944   /// algorithm.
   945   template<class TR>
   946   class BellmanFordWizard : public TR {
   947     typedef TR Base;
   948 
   949     typedef typename TR::Digraph Digraph;
   950 
   951     typedef typename Digraph::Node Node;
   952     typedef typename Digraph::NodeIt NodeIt;
   953     typedef typename Digraph::Arc Arc;
   954     typedef typename Digraph::OutArcIt ArcIt;
   955 
   956     typedef typename TR::LengthMap LengthMap;
   957     typedef typename LengthMap::Value Value;
   958     typedef typename TR::PredMap PredMap;
   959     typedef typename TR::DistMap DistMap;
   960     typedef typename TR::Path Path;
   961 
   962   public:
   963     /// Constructor.
   964     BellmanFordWizard() : TR() {}
   965 
   966     /// \brief Constructor that requires parameters.
   967     ///
   968     /// Constructor that requires parameters.
   969     /// These parameters will be the default values for the traits class.
   970     /// \param gr The digraph the algorithm runs on.
   971     /// \param len The length map.
   972     BellmanFordWizard(const Digraph& gr, const LengthMap& len)
   973       : TR(gr, len) {}
   974 
   975     /// \brief Copy constructor
   976     BellmanFordWizard(const TR &b) : TR(b) {}
   977 
   978     ~BellmanFordWizard() {}
   979 
   980     /// \brief Runs the Bellman-Ford algorithm from the given source node.
   981     ///
   982     /// This method runs the Bellman-Ford algorithm from the given source
   983     /// node in order to compute the shortest path to each node.
   984     void run(Node s) {
   985       BellmanFord<Digraph,LengthMap,TR>
   986         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
   987            *reinterpret_cast<const LengthMap*>(Base::_length));
   988       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
   989       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   990       bf.run(s);
   991     }
   992 
   993     /// \brief Runs the Bellman-Ford algorithm to find the shortest path
   994     /// between \c s and \c t.
   995     ///
   996     /// This method runs the Bellman-Ford algorithm from node \c s
   997     /// in order to compute the shortest path to node \c t.
   998     /// Actually, it computes the shortest path to each node, but using
   999     /// this function you can retrieve the distance and the shortest path
  1000     /// for a single target node easier.
  1001     ///
  1002     /// \return \c true if \c t is reachable form \c s.
  1003     bool run(Node s, Node t) {
  1004       BellmanFord<Digraph,LengthMap,TR>
  1005         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
  1006            *reinterpret_cast<const LengthMap*>(Base::_length));
  1007       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1008       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1009       bf.run(s);
  1010       if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
  1011       if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
  1012       return bf.reached(t);
  1013     }
  1014 
  1015     template<class T>
  1016     struct SetPredMapBase : public Base {
  1017       typedef T PredMap;
  1018       static PredMap *createPredMap(const Digraph &) { return 0; };
  1019       SetPredMapBase(const TR &b) : TR(b) {}
  1020     };
  1021 
  1022     /// \brief \ref named-templ-param "Named parameter" for setting
  1023     /// the predecessor map.
  1024     ///
  1025     /// \ref named-templ-param "Named parameter" for setting
  1026     /// the map that stores the predecessor arcs of the nodes.
  1027     template<class T>
  1028     BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
  1029       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1030       return BellmanFordWizard<SetPredMapBase<T> >(*this);
  1031     }
  1032 
  1033     template<class T>
  1034     struct SetDistMapBase : public Base {
  1035       typedef T DistMap;
  1036       static DistMap *createDistMap(const Digraph &) { return 0; };
  1037       SetDistMapBase(const TR &b) : TR(b) {}
  1038     };
  1039 
  1040     /// \brief \ref named-templ-param "Named parameter" for setting
  1041     /// the distance map.
  1042     ///
  1043     /// \ref named-templ-param "Named parameter" for setting
  1044     /// the map that stores the distances of the nodes calculated
  1045     /// by the algorithm.
  1046     template<class T>
  1047     BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
  1048       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1049       return BellmanFordWizard<SetDistMapBase<T> >(*this);
  1050     }
  1051 
  1052     template<class T>
  1053     struct SetPathBase : public Base {
  1054       typedef T Path;
  1055       SetPathBase(const TR &b) : TR(b) {}
  1056     };
  1057 
  1058     /// \brief \ref named-func-param "Named parameter" for getting
  1059     /// the shortest path to the target node.
  1060     ///
  1061     /// \ref named-func-param "Named parameter" for getting
  1062     /// the shortest path to the target node.
  1063     template<class T>
  1064     BellmanFordWizard<SetPathBase<T> > path(const T &t)
  1065     {
  1066       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1067       return BellmanFordWizard<SetPathBase<T> >(*this);
  1068     }
  1069 
  1070     /// \brief \ref named-func-param "Named parameter" for getting
  1071     /// the distance of the target node.
  1072     ///
  1073     /// \ref named-func-param "Named parameter" for getting
  1074     /// the distance of the target node.
  1075     BellmanFordWizard dist(const Value &d)
  1076     {
  1077       Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
  1078       return *this;
  1079     }
  1080 
  1081   };
  1082 
  1083   /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
  1084   /// algorithm.
  1085   ///
  1086   /// \ingroup shortest_path
  1087   /// Function type interface for the \ref BellmanFord "Bellman-Ford"
  1088   /// algorithm.
  1089   ///
  1090   /// This function also has several \ref named-templ-func-param
  1091   /// "named parameters", they are declared as the members of class
  1092   /// \ref BellmanFordWizard.
  1093   /// The following examples show how to use these parameters.
  1094   /// \code
  1095   ///   // Compute shortest path from node s to each node
  1096   ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
  1097   ///
  1098   ///   // Compute shortest path from s to t
  1099   ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
  1100   /// \endcode
  1101   /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
  1102   /// to the end of the parameter list.
  1103   /// \sa BellmanFordWizard
  1104   /// \sa BellmanFord
  1105   template<typename GR, typename LEN>
  1106   BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
  1107   bellmanFord(const GR& digraph,
  1108               const LEN& length)
  1109   {
  1110     return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
  1111   }
  1112 
  1113 } //END OF NAMESPACE LEMON
  1114 
  1115 #endif
  1116