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