lemon/bellman_ford.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 18 Nov 2009 14:21:35 +0100
changeset 790 1870cfd14fb6
parent 696 c9b9da1a90a0
child 699 75325dfccf38
permissions -rw-r--r--
Fix gcc-4.4 compilation warning
     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     // TODO: implement negative cycle
   774 //    /// \brief Gives back a negative cycle.
   775 //    ///    
   776 //    /// This function gives back a negative cycle.
   777 //    /// If the algorithm have not found yet negative cycle it will give back
   778 //    /// an empty path.
   779 //    Path negativeCycle() {
   780 //      typename Digraph::template NodeMap<int> state(*digraph, 0);
   781 //      for (ActiveIt it(*this); it != INVALID; ++it) {
   782 //        if (state[it] == 0) {
   783 //          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
   784 //            if (state[t] == 0) {
   785 //              state[t] = 1;
   786 //            } else if (state[t] == 2) {
   787 //              break;
   788 //            } else {
   789 //              p.clear();
   790 //              typename Path::Builder b(p);
   791 //              b.setStartNode(t);
   792 //              b.pushFront(predArc(t));
   793 //              for(Node s = predNode(t); s != t; s = predNode(s)) {
   794 //                b.pushFront(predArc(s));
   795 //              }
   796 //              b.commit();
   797 //              return true;
   798 //            }
   799 //          }
   800 //          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
   801 //            if (state[t] == 1) {
   802 //              state[t] = 2;
   803 //            } else {
   804 //              break;
   805 //            }
   806 //          }
   807 //        }
   808 //      }
   809 //      return false;
   810 //    }
   811     
   812     ///@}
   813   };
   814  
   815   /// \brief Default traits class of bellmanFord() function.
   816   ///
   817   /// Default traits class of bellmanFord() function.
   818   /// \tparam GR The type of the digraph.
   819   /// \tparam LEN The type of the length map.
   820   template <typename GR, typename LEN>
   821   struct BellmanFordWizardDefaultTraits {
   822     /// The type of the digraph the algorithm runs on. 
   823     typedef GR Digraph;
   824 
   825     /// \brief The type of the map that stores the arc lengths.
   826     ///
   827     /// The type of the map that stores the arc lengths.
   828     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
   829     typedef LEN LengthMap;
   830 
   831     /// The type of the arc lengths.
   832     typedef typename LEN::Value Value;
   833 
   834     /// \brief Operation traits for Bellman-Ford algorithm.
   835     ///
   836     /// It defines the used operations and the infinity value for the
   837     /// given \c Value type.
   838     /// \see BellmanFordDefaultOperationTraits
   839     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   840 
   841     /// \brief The type of the map that stores the last
   842     /// arcs of the shortest paths.
   843     /// 
   844     /// The type of the map that stores the last arcs of the shortest paths.
   845     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   846     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   847 
   848     /// \brief Instantiates a \c PredMap.
   849     /// 
   850     /// This function instantiates a \ref PredMap.
   851     /// \param g is the digraph to which we would like to define the
   852     /// \ref PredMap.
   853     static PredMap *createPredMap(const GR &g) {
   854       return new PredMap(g);
   855     }
   856 
   857     /// \brief The type of the map that stores the distances of the nodes.
   858     ///
   859     /// The type of the map that stores the distances of the nodes.
   860     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   861     typedef typename GR::template NodeMap<Value> DistMap;
   862 
   863     /// \brief Instantiates a \c DistMap.
   864     ///
   865     /// This function instantiates a \ref DistMap. 
   866     /// \param g is the digraph to which we would like to define the
   867     /// \ref DistMap.
   868     static DistMap *createDistMap(const GR &g) {
   869       return new DistMap(g);
   870     }
   871 
   872     ///The type of the shortest paths.
   873 
   874     ///The type of the shortest paths.
   875     ///It must meet the \ref concepts::Path "Path" concept.
   876     typedef lemon::Path<Digraph> Path;
   877   };
   878   
   879   /// \brief Default traits class used by BellmanFordWizard.
   880   ///
   881   /// Default traits class used by BellmanFordWizard.
   882   /// \tparam GR The type of the digraph.
   883   /// \tparam LEN The type of the length map.
   884   template <typename GR, typename LEN>
   885   class BellmanFordWizardBase 
   886     : public BellmanFordWizardDefaultTraits<GR, LEN> {
   887 
   888     typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
   889   protected:
   890     // Type of the nodes in the digraph.
   891     typedef typename Base::Digraph::Node Node;
   892 
   893     // Pointer to the underlying digraph.
   894     void *_graph;
   895     // Pointer to the length map
   896     void *_length;
   897     // Pointer to the map of predecessors arcs.
   898     void *_pred;
   899     // Pointer to the map of distances.
   900     void *_dist;
   901     //Pointer to the shortest path to the target node.
   902     void *_path;
   903     //Pointer to the distance of the target node.
   904     void *_di;
   905 
   906     public:
   907     /// Constructor.
   908     
   909     /// This constructor does not require parameters, it initiates
   910     /// all of the attributes to default values \c 0.
   911     BellmanFordWizardBase() :
   912       _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
   913 
   914     /// Constructor.
   915     
   916     /// This constructor requires two parameters,
   917     /// others are initiated to \c 0.
   918     /// \param gr The digraph the algorithm runs on.
   919     /// \param len The length map.
   920     BellmanFordWizardBase(const GR& gr, 
   921 			  const LEN& len) :
   922       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
   923       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
   924       _pred(0), _dist(0), _path(0), _di(0) {}
   925 
   926   };
   927   
   928   /// \brief Auxiliary class for the function-type interface of the
   929   /// \ref BellmanFord "Bellman-Ford" algorithm.
   930   ///
   931   /// This auxiliary class is created to implement the
   932   /// \ref bellmanFord() "function-type interface" of the
   933   /// \ref BellmanFord "Bellman-Ford" algorithm.
   934   /// It does not have own \ref run() method, it uses the
   935   /// functions and features of the plain \ref BellmanFord.
   936   ///
   937   /// This class should only be used through the \ref bellmanFord()
   938   /// function, which makes it easier to use the algorithm.
   939   template<class TR>
   940   class BellmanFordWizard : public TR {
   941     typedef TR Base;
   942 
   943     typedef typename TR::Digraph Digraph;
   944 
   945     typedef typename Digraph::Node Node;
   946     typedef typename Digraph::NodeIt NodeIt;
   947     typedef typename Digraph::Arc Arc;
   948     typedef typename Digraph::OutArcIt ArcIt;
   949     
   950     typedef typename TR::LengthMap LengthMap;
   951     typedef typename LengthMap::Value Value;
   952     typedef typename TR::PredMap PredMap;
   953     typedef typename TR::DistMap DistMap;
   954     typedef typename TR::Path Path;
   955 
   956   public:
   957     /// Constructor.
   958     BellmanFordWizard() : TR() {}
   959 
   960     /// \brief Constructor that requires parameters.
   961     ///
   962     /// Constructor that requires parameters.
   963     /// These parameters will be the default values for the traits class.
   964     /// \param gr The digraph the algorithm runs on.
   965     /// \param len The length map.
   966     BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
   967       : TR(gr, len) {}
   968 
   969     /// \brief Copy constructor
   970     BellmanFordWizard(const TR &b) : TR(b) {}
   971 
   972     ~BellmanFordWizard() {}
   973 
   974     /// \brief Runs the Bellman-Ford algorithm from the given source node.
   975     ///    
   976     /// This method runs the Bellman-Ford algorithm from the given source
   977     /// node in order to compute the shortest path to each node.
   978     void run(Node s) {
   979       BellmanFord<Digraph,LengthMap,TR> 
   980 	bf(*reinterpret_cast<const Digraph*>(Base::_graph), 
   981            *reinterpret_cast<const LengthMap*>(Base::_length));
   982       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
   983       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   984       bf.run(s);
   985     }
   986 
   987     /// \brief Runs the Bellman-Ford algorithm to find the shortest path
   988     /// between \c s and \c t.
   989     ///
   990     /// This method runs the Bellman-Ford algorithm from node \c s
   991     /// in order to compute the shortest path to node \c t.
   992     /// Actually, it computes the shortest path to each node, but using
   993     /// this function you can retrieve the distance and the shortest path
   994     /// for a single target node easier.
   995     ///
   996     /// \return \c true if \c t is reachable form \c s.
   997     bool run(Node s, Node t) {
   998       BellmanFord<Digraph,LengthMap,TR>
   999         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
  1000            *reinterpret_cast<const LengthMap*>(Base::_length));
  1001       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1002       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1003       bf.run(s);
  1004       if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
  1005       if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
  1006       return bf.reached(t);
  1007     }
  1008 
  1009     template<class T>
  1010     struct SetPredMapBase : public Base {
  1011       typedef T PredMap;
  1012       static PredMap *createPredMap(const Digraph &) { return 0; };
  1013       SetPredMapBase(const TR &b) : TR(b) {}
  1014     };
  1015     
  1016     /// \brief \ref named-templ-param "Named parameter" for setting
  1017     /// the predecessor map.
  1018     ///
  1019     /// \ref named-templ-param "Named parameter" for setting
  1020     /// the map that stores the predecessor arcs of the nodes.
  1021     template<class T>
  1022     BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
  1023       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1024       return BellmanFordWizard<SetPredMapBase<T> >(*this);
  1025     }
  1026     
  1027     template<class T>
  1028     struct SetDistMapBase : public Base {
  1029       typedef T DistMap;
  1030       static DistMap *createDistMap(const Digraph &) { return 0; };
  1031       SetDistMapBase(const TR &b) : TR(b) {}
  1032     };
  1033     
  1034     /// \brief \ref named-templ-param "Named parameter" for setting
  1035     /// the distance map.
  1036     ///
  1037     /// \ref named-templ-param "Named parameter" for setting
  1038     /// the map that stores the distances of the nodes calculated
  1039     /// by the algorithm.
  1040     template<class T>
  1041     BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
  1042       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1043       return BellmanFordWizard<SetDistMapBase<T> >(*this);
  1044     }
  1045 
  1046     template<class T>
  1047     struct SetPathBase : public Base {
  1048       typedef T Path;
  1049       SetPathBase(const TR &b) : TR(b) {}
  1050     };
  1051 
  1052     /// \brief \ref named-func-param "Named parameter" for getting
  1053     /// the shortest path to the target node.
  1054     ///
  1055     /// \ref named-func-param "Named parameter" for getting
  1056     /// the shortest path to the target node.
  1057     template<class T>
  1058     BellmanFordWizard<SetPathBase<T> > path(const T &t)
  1059     {
  1060       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1061       return BellmanFordWizard<SetPathBase<T> >(*this);
  1062     }
  1063 
  1064     /// \brief \ref named-func-param "Named parameter" for getting
  1065     /// the distance of the target node.
  1066     ///
  1067     /// \ref named-func-param "Named parameter" for getting
  1068     /// the distance of the target node.
  1069     BellmanFordWizard dist(const Value &d)
  1070     {
  1071       Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
  1072       return *this;
  1073     }
  1074     
  1075   };
  1076   
  1077   /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
  1078   /// algorithm.
  1079   ///
  1080   /// \ingroup shortest_path
  1081   /// Function type interface for the \ref BellmanFord "Bellman-Ford"
  1082   /// algorithm.
  1083   ///
  1084   /// This function also has several \ref named-templ-func-param 
  1085   /// "named parameters", they are declared as the members of class 
  1086   /// \ref BellmanFordWizard.
  1087   /// The following examples show how to use these parameters.
  1088   /// \code
  1089   ///   // Compute shortest path from node s to each node
  1090   ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
  1091   ///
  1092   ///   // Compute shortest path from s to t
  1093   ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
  1094   /// \endcode
  1095   /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
  1096   /// to the end of the parameter list.
  1097   /// \sa BellmanFordWizard
  1098   /// \sa BellmanFord
  1099   template<typename GR, typename LEN>
  1100   BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
  1101   bellmanFord(const GR& digraph,
  1102 	      const LEN& length)
  1103   {
  1104     return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
  1105   }
  1106 
  1107 } //END OF NAMESPACE LEMON
  1108 
  1109 #endif
  1110