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