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