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