lemon/bellman_ford.h
 author Balazs Dezso Thu, 04 Mar 2010 15:20:59 +0100 changeset 951 41d7ac528c3a parent 744 9496ed797f20 child 828 6f10c6ec5a21 child 833 e20173729589 permissions -rw-r--r--
Uniforming primal scale to 2 (#314)
     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2008

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    18

    19 #ifndef LEMON_BELLMAN_FORD_H

    20 #define LEMON_BELLMAN_FORD_H

    21

    22 /// \ingroup shortest_path

    23 /// \file

    24 /// \brief Bellman-Ford algorithm.

    25

    26 #include <lemon/bits/path_dump.h>

    27 #include <lemon/core.h>

    28 #include <lemon/error.h>

    29 #include <lemon/maps.h>

    30 #include <lemon/path.h>

    31

    32 #include <limits>

    33

    34 namespace lemon {

    35

    36   /// \brief Default OperationTraits for the BellmanFord algorithm class.

    37   ///

    38   /// This operation traits class defines all computational operations

    39   /// and constants that are used in the Bellman-Ford algorithm.

    40   /// The default implementation is based on the \c numeric_limits class.

    41   /// If the numeric type does not have infinity value, then the maximum

    42   /// value is used as extremal infinity value.

    43   template <

    44     typename V,

    45     bool has_inf = std::numeric_limits<V>::has_infinity>

    46   struct BellmanFordDefaultOperationTraits {

    47     /// \e

    48     typedef V Value;

    49     /// \brief Gives back the zero value of the type.

    50     static Value zero() {

    51       return static_cast<Value>(0);

    52     }

    53     /// \brief Gives back the positive infinity value of the type.

    54     static Value infinity() {

    55       return std::numeric_limits<Value>::infinity();

    56     }

    57     /// \brief Gives back the sum of the given two elements.

    58     static Value plus(const Value& left, const Value& right) {

    59       return left + right;

    60     }

    61     /// \brief Gives back \c true only if the first value is less than

    62     /// the second.

    63     static bool less(const Value& left, const Value& right) {

    64       return left < right;

    65     }

    66   };

    67

    68   template <typename V>

    69   struct BellmanFordDefaultOperationTraits<V, false> {

    70     typedef V Value;

    71     static Value zero() {

    72       return static_cast<Value>(0);

    73     }

    74     static Value infinity() {

    75       return std::numeric_limits<Value>::max();

    76     }

    77     static Value plus(const Value& left, const Value& right) {

    78       if (left == infinity() || right == infinity()) return infinity();

    79       return left + right;

    80     }

    81     static bool less(const Value& left, const Value& right) {

    82       return left < right;

    83     }

    84   };

    85

    86   /// \brief Default traits class of BellmanFord class.

    87   ///

    88   /// Default traits class of BellmanFord class.

    89   /// \param GR The type of the digraph.

    90   /// \param LEN The type of the length map.

    91   template<typename GR, typename LEN>

    92   struct BellmanFordDefaultTraits {

    93     /// The type of the digraph the algorithm runs on.

    94     typedef GR Digraph;

    95

    96     /// \brief The type of the map that stores the arc lengths.

    97     ///

    98     /// The type of the map that stores the arc lengths.

    99     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

   100     typedef LEN LengthMap;

   101

   102     /// The type of the arc lengths.

   103     typedef typename LEN::Value Value;

   104

   105     /// \brief Operation traits for Bellman-Ford algorithm.

   106     ///

   107     /// It defines the used operations and the infinity value for the

   108     /// given \c Value type.

   109     /// \see BellmanFordDefaultOperationTraits

   110     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;

   111

   112     /// \brief The type of the map that stores the last arcs of the

   113     /// shortest paths.

   114     ///

   115     /// The type of the map that stores the last

   116     /// arcs of the shortest paths.

   117     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

   118     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;

   119

   120     /// \brief Instantiates a \c PredMap.

   121     ///

   122     /// This function instantiates a \ref PredMap.

   123     /// \param g is the digraph to which we would like to define the

   124     /// \ref PredMap.

   125     static PredMap *createPredMap(const GR& g) {

   126       return new PredMap(g);

   127     }

   128

   129     /// \brief The type of the map that stores the distances of the nodes.

   130     ///

   131     /// The type of the map that stores the distances of the nodes.

   132     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

   133     typedef typename GR::template NodeMap<typename LEN::Value> DistMap;

   134

   135     /// \brief Instantiates a \c DistMap.

   136     ///

   137     /// This function instantiates a \ref DistMap.

   138     /// \param g is the digraph to which we would like to define the

   139     /// \ref DistMap.

   140     static DistMap *createDistMap(const GR& g) {

   141       return new DistMap(g);

   142     }

   143

   144   };

   145

   146   /// \brief %BellmanFord algorithm class.

   147   ///

   148   /// \ingroup shortest_path

   149   /// This class provides an efficient implementation of the Bellman-Ford

   150   /// algorithm. The maximum time complexity of the algorithm is

   151   /// <tt>O(ne)</tt>.

   152   ///

   153   /// The Bellman-Ford algorithm solves the single-source shortest path

   154   /// problem when the arcs can have negative lengths, but the digraph

   155   /// should not contain directed cycles with negative total length.

   156   /// If all arc costs are non-negative, consider to use the Dijkstra

   157   /// algorithm instead, since it is more efficient.

   158   ///

   159   /// The arc lengths are passed to the algorithm using a

   160   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any

   161   /// kind of length. The type of the length values is determined by the

   162   /// \ref concepts::ReadMap::Value "Value" type of the length map.

   163   ///

   164   /// There is also a \ref bellmanFord() "function-type interface" for the

   165   /// Bellman-Ford algorithm, which is convenient in the simplier cases and

   166   /// it can be used easier.

   167   ///

   168   /// \tparam GR The type of the digraph the algorithm runs on.

   169   /// The default type is \ref ListDigraph.

   170   /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies

   171   /// the lengths of the arcs. The default map type is

   172   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

   173 #ifdef DOXYGEN

   174   template <typename GR, typename LEN, typename TR>

   175 #else

   176   template <typename GR=ListDigraph,

   177             typename LEN=typename GR::template ArcMap<int>,

   178             typename TR=BellmanFordDefaultTraits<GR,LEN> >

   179 #endif

   180   class BellmanFord {

   181   public:

   182

   183     ///The type of the underlying digraph.

   184     typedef typename TR::Digraph Digraph;

   185

   186     /// \brief The type of the arc lengths.

   187     typedef typename TR::LengthMap::Value Value;

   188     /// \brief The type of the map that stores the arc lengths.

   189     typedef typename TR::LengthMap LengthMap;

   190     /// \brief The type of the map that stores the last

   191     /// arcs of the shortest paths.

   192     typedef typename TR::PredMap PredMap;

   193     /// \brief The type of the map that stores the distances of the nodes.

   194     typedef typename TR::DistMap DistMap;

   195     /// The type of the paths.

   196     typedef PredMapPath<Digraph, PredMap> Path;

   197     ///\brief The \ref BellmanFordDefaultOperationTraits

   198     /// "operation traits class" of the algorithm.

   199     typedef typename TR::OperationTraits OperationTraits;

   200

   201     ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.

   202     typedef TR Traits;

   203

   204   private:

   205

   206     typedef typename Digraph::Node Node;

   207     typedef typename Digraph::NodeIt NodeIt;

   208     typedef typename Digraph::Arc Arc;

   209     typedef typename Digraph::OutArcIt OutArcIt;

   210

   211     // Pointer to the underlying digraph.

   212     const Digraph *_gr;

   213     // Pointer to the length map

   214     const LengthMap *_length;

   215     // Pointer to the map of predecessors arcs.

   216     PredMap *_pred;

   217     // Indicates if _pred is locally allocated (true) or not.

   218     bool _local_pred;

   219     // Pointer to the map of distances.

   220     DistMap *_dist;

   221     // Indicates if _dist is locally allocated (true) or not.

   222     bool _local_dist;

   223

   224     typedef typename Digraph::template NodeMap<bool> MaskMap;

   225     MaskMap *_mask;

   226

   227     std::vector<Node> _process;

   228

   229     // Creates the maps if necessary.

   230     void create_maps() {

   231       if(!_pred) {

   232 	_local_pred = true;

   233 	_pred = Traits::createPredMap(*_gr);

   234       }

   235       if(!_dist) {

   236 	_local_dist = true;

   237 	_dist = Traits::createDistMap(*_gr);

   238       }

   239       _mask = new MaskMap(*_gr, false);

   240     }

   241

   242   public :

   243

   244     typedef BellmanFord Create;

   245

   246     /// \name Named Template Parameters

   247

   248     ///@{

   249

   250     template <class T>

   251     struct SetPredMapTraits : public Traits {

   252       typedef T PredMap;

   253       static PredMap *createPredMap(const Digraph&) {

   254         LEMON_ASSERT(false, "PredMap is not initialized");

   255         return 0; // ignore warnings

   256       }

   257     };

   258

   259     /// \brief \ref named-templ-param "Named parameter" for setting

   260     /// \c PredMap type.

   261     ///

   262     /// \ref named-templ-param "Named parameter" for setting

   263     /// \c PredMap type.

   264     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

   265     template <class T>

   266     struct SetPredMap

   267       : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {

   268       typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;

   269     };

   270

   271     template <class T>

   272     struct SetDistMapTraits : public Traits {

   273       typedef T DistMap;

   274       static DistMap *createDistMap(const Digraph&) {

   275         LEMON_ASSERT(false, "DistMap is not initialized");

   276         return 0; // ignore warnings

   277       }

   278     };

   279

   280     /// \brief \ref named-templ-param "Named parameter" for setting

   281     /// \c DistMap type.

   282     ///

   283     /// \ref named-templ-param "Named parameter" for setting

   284     /// \c DistMap type.

   285     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

   286     template <class T>

   287     struct SetDistMap

   288       : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {

   289       typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;

   290     };

   291

   292     template <class T>

   293     struct SetOperationTraitsTraits : public Traits {

   294       typedef T OperationTraits;

   295     };

   296

   297     /// \brief \ref named-templ-param "Named parameter" for setting

   298     /// \c OperationTraits type.

   299     ///

   300     /// \ref named-templ-param "Named parameter" for setting

   301     /// \c OperationTraits type.

   302     /// For more information see \ref BellmanFordDefaultOperationTraits.

   303     template <class T>

   304     struct SetOperationTraits

   305       : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {

   306       typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >

   307       Create;

   308     };

   309

   310     ///@}

   311

   312   protected:

   313

   314     BellmanFord() {}

   315

   316   public:

   317

   318     /// \brief Constructor.

   319     ///

   320     /// Constructor.

   321     /// \param g The digraph the algorithm runs on.

   322     /// \param length The length map used by the algorithm.

   323     BellmanFord(const Digraph& g, const LengthMap& length) :

   324       _gr(&g), _length(&length),

   325       _pred(0), _local_pred(false),

   326       _dist(0), _local_dist(false), _mask(0) {}

   327

   328     ///Destructor.

   329     ~BellmanFord() {

   330       if(_local_pred) delete _pred;

   331       if(_local_dist) delete _dist;

   332       if(_mask) delete _mask;

   333     }

   334

   335     /// \brief Sets the length map.

   336     ///

   337     /// Sets the length map.

   338     /// \return <tt>(*this)</tt>

   339     BellmanFord &lengthMap(const LengthMap &map) {

   340       _length = &map;

   341       return *this;

   342     }

   343

   344     /// \brief Sets the map that stores the predecessor arcs.

   345     ///

   346     /// Sets the map that stores the predecessor arcs.

   347     /// If you don't use this function before calling \ref run()

   348     /// or \ref init(), an instance will be allocated automatically.

   349     /// The destructor deallocates this automatically allocated map,

   350     /// of course.

   351     /// \return <tt>(*this)</tt>

   352     BellmanFord &predMap(PredMap &map) {

   353       if(_local_pred) {

   354 	delete _pred;

   355 	_local_pred=false;

   356       }

   357       _pred = &map;

   358       return *this;

   359     }

   360

   361     /// \brief Sets the map that stores the distances of the nodes.

   362     ///

   363     /// Sets the map that stores the distances of the nodes calculated

   364     /// by the algorithm.

   365     /// If you don't use this function before calling \ref run()

   366     /// or \ref init(), an instance will be allocated automatically.

   367     /// The destructor deallocates this automatically allocated map,

   368     /// of course.

   369     /// \return <tt>(*this)</tt>

   370     BellmanFord &distMap(DistMap &map) {

   371       if(_local_dist) {

   372 	delete _dist;

   373 	_local_dist=false;

   374       }

   375       _dist = &map;

   376       return *this;

   377     }

   378

   379     /// \name Execution Control

   380     /// The simplest way to execute the Bellman-Ford algorithm is to use

   381     /// one of the member functions called \ref run().\n

   382     /// If you need better control on the execution, you have to call

   383     /// \ref init() first, then you can add several source nodes

   384     /// with \ref addSource(). Finally the actual path computation can be

   385     /// performed with \ref start(), \ref checkedStart() or

   386     /// \ref limitedStart().

   387

   388     ///@{

   389

   390     /// \brief Initializes the internal data structures.

   391     ///

   392     /// Initializes the internal data structures. The optional parameter

   393     /// is the initial distance of each node.

   394     void init(const Value value = OperationTraits::infinity()) {

   395       create_maps();

   396       for (NodeIt it(*_gr); it != INVALID; ++it) {

   397 	_pred->set(it, INVALID);

   398 	_dist->set(it, value);

   399       }

   400       _process.clear();

   401       if (OperationTraits::less(value, OperationTraits::infinity())) {

   402 	for (NodeIt it(*_gr); it != INVALID; ++it) {

   403 	  _process.push_back(it);

   404 	  _mask->set(it, true);

   405 	}

   406       }

   407     }

   408

   409     /// \brief Adds a new source node.

   410     ///

   411     /// This function adds a new source node. The optional second parameter

   412     /// is the initial distance of the node.

   413     void addSource(Node source, Value dst = OperationTraits::zero()) {

   414       _dist->set(source, dst);

   415       if (!(*_mask)[source]) {

   416 	_process.push_back(source);

   417 	_mask->set(source, true);

   418       }

   419     }

   420

   421     /// \brief Executes one round from the Bellman-Ford algorithm.

   422     ///

   423     /// If the algoritm calculated the distances in the previous round

   424     /// exactly for the paths of at most \c k arcs, then this function

   425     /// will calculate the distances exactly for the paths of at most

   426     /// <tt>k+1</tt> arcs. Performing \c k iterations using this function

   427     /// calculates the shortest path distances exactly for the paths

   428     /// consisting of at most \c k arcs.

   429     ///

   430     /// \warning The paths with limited arc number cannot be retrieved

   431     /// easily with \ref path() or \ref predArc() functions. If you also

   432     /// need the shortest paths and not only the distances, you should

   433     /// store the \ref predMap() "predecessor map" after each iteration

   434     /// and build the path manually.

   435     ///

   436     /// \return \c true when the algorithm have not found more shorter

   437     /// paths.

   438     ///

   439     /// \see ActiveIt

   440     bool processNextRound() {

   441       for (int i = 0; i < int(_process.size()); ++i) {

   442 	_mask->set(_process[i], false);

   443       }

   444       std::vector<Node> nextProcess;

   445       std::vector<Value> values(_process.size());

   446       for (int i = 0; i < int(_process.size()); ++i) {

   447 	values[i] = (*_dist)[_process[i]];

   448       }

   449       for (int i = 0; i < int(_process.size()); ++i) {

   450 	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {

   451 	  Node target = _gr->target(it);

   452 	  Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);

   453 	  if (OperationTraits::less(relaxed, (*_dist)[target])) {

   454 	    _pred->set(target, it);

   455 	    _dist->set(target, relaxed);

   456 	    if (!(*_mask)[target]) {

   457 	      _mask->set(target, true);

   458 	      nextProcess.push_back(target);

   459 	    }

   460 	  }

   461 	}

   462       }

   463       _process.swap(nextProcess);

   464       return _process.empty();

   465     }

   466

   467     /// \brief Executes one weak round from the Bellman-Ford algorithm.

   468     ///

   469     /// If the algorithm calculated the distances in the previous round

   470     /// at least for the paths of at most \c k arcs, then this function

   471     /// will calculate the distances at least for the paths of at most

   472     /// <tt>k+1</tt> arcs.

   473     /// This function does not make it possible to calculate the shortest

   474     /// path distances exactly for paths consisting of at most \c k arcs,

   475     /// this is why it is called weak round.

   476     ///

   477     /// \return \c true when the algorithm have not found more shorter

   478     /// paths.

   479     ///

   480     /// \see ActiveIt

   481     bool processNextWeakRound() {

   482       for (int i = 0; i < int(_process.size()); ++i) {

   483 	_mask->set(_process[i], false);

   484       }

   485       std::vector<Node> nextProcess;

   486       for (int i = 0; i < int(_process.size()); ++i) {

   487 	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {

   488 	  Node target = _gr->target(it);

   489 	  Value relaxed =

   490 	    OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);

   491 	  if (OperationTraits::less(relaxed, (*_dist)[target])) {

   492 	    _pred->set(target, it);

   493 	    _dist->set(target, relaxed);

   494 	    if (!(*_mask)[target]) {

   495 	      _mask->set(target, true);

   496 	      nextProcess.push_back(target);

   497 	    }

   498 	  }

   499 	}

   500       }

   501       _process.swap(nextProcess);

   502       return _process.empty();

   503     }

   504

   505     /// \brief Executes the algorithm.

   506     ///

   507     /// Executes the algorithm.

   508     ///

   509     /// This method runs the Bellman-Ford algorithm from the root node(s)

   510     /// in order to compute the shortest path to each node.

   511     ///

   512     /// The algorithm computes

   513     /// - the shortest path tree (forest),

   514     /// - the distance of each node from the root(s).

   515     ///

   516     /// \pre init() must be called and at least one root node should be

   517     /// added with addSource() before using this function.

   518     void start() {

   519       int num = countNodes(*_gr) - 1;

   520       for (int i = 0; i < num; ++i) {

   521 	if (processNextWeakRound()) break;

   522       }

   523     }

   524

   525     /// \brief Executes the algorithm and checks the negative cycles.

   526     ///

   527     /// Executes the algorithm and checks the negative cycles.

   528     ///

   529     /// This method runs the Bellman-Ford algorithm from the root node(s)

   530     /// in order to compute the shortest path to each node and also checks

   531     /// if the digraph contains cycles with negative total length.

   532     ///

   533     /// The algorithm computes

   534     /// - the shortest path tree (forest),

   535     /// - the distance of each node from the root(s).

   536     ///

   537     /// \return \c false if there is a negative cycle in the digraph.

   538     ///

   539     /// \pre init() must be called and at least one root node should be

   540     /// added with addSource() before using this function.

   541     bool checkedStart() {

   542       int num = countNodes(*_gr);

   543       for (int i = 0; i < num; ++i) {

   544 	if (processNextWeakRound()) return true;

   545       }

   546       return _process.empty();

   547     }

   548

   549     /// \brief Executes the algorithm with arc number limit.

   550     ///

   551     /// Executes the algorithm with arc number limit.

   552     ///

   553     /// This method runs the Bellman-Ford algorithm from the root node(s)

   554     /// in order to compute the shortest path distance for each node

   555     /// using only the paths consisting of at most \c num arcs.

   556     ///

   557     /// The algorithm computes

   558     /// - the limited distance of each node from the root(s),

   559     /// - the predecessor arc for each node.

   560     ///

   561     /// \warning The paths with limited arc number cannot be retrieved

   562     /// easily with \ref path() or \ref predArc() functions. If you also

   563     /// need the shortest paths and not only the distances, you should

   564     /// store the \ref predMap() "predecessor map" after each iteration

   565     /// and build the path manually.

   566     ///

   567     /// \pre init() must be called and at least one root node should be

   568     /// added with addSource() before using this function.

   569     void limitedStart(int num) {

   570       for (int i = 0; i < num; ++i) {

   571 	if (processNextRound()) break;

   572       }

   573     }

   574

   575     /// \brief Runs the algorithm from the given root node.

   576     ///

   577     /// This method runs the Bellman-Ford algorithm from the given root

   578     /// node \c s in order to compute the shortest path to each node.

   579     ///

   580     /// The algorithm computes

   581     /// - the shortest path tree (forest),

   582     /// - the distance of each node from the root(s).

   583     ///

   584     /// \note bf.run(s) is just a shortcut of the following code.

   585     /// \code

   586     ///   bf.init();

   587     ///   bf.addSource(s);

   588     ///   bf.start();

   589     /// \endcode

   590     void run(Node s) {

   591       init();

   592       addSource(s);

   593       start();

   594     }

   595

   596     /// \brief Runs the algorithm from the given root node with arc

   597     /// number limit.

   598     ///

   599     /// This method runs the Bellman-Ford algorithm from the given root

   600     /// node \c s in order to compute the shortest path distance for each

   601     /// node using only the paths consisting of at most \c num arcs.

   602     ///

   603     /// The algorithm computes

   604     /// - the limited distance of each node from the root(s),

   605     /// - the predecessor arc for each node.

   606     ///

   607     /// \warning The paths with limited arc number cannot be retrieved

   608     /// easily with \ref path() or \ref predArc() functions. If you also

   609     /// need the shortest paths and not only the distances, you should

   610     /// store the \ref predMap() "predecessor map" after each iteration

   611     /// and build the path manually.

   612     ///

   613     /// \note bf.run(s, num) is just a shortcut of the following code.

   614     /// \code

   615     ///   bf.init();

   616     ///   bf.addSource(s);

   617     ///   bf.limitedStart(num);

   618     /// \endcode

   619     void run(Node s, int num) {

   620       init();

   621       addSource(s);

   622       limitedStart(num);

   623     }

   624

   625     ///@}

   626

   627     /// \brief LEMON iterator for getting the active nodes.

   628     ///

   629     /// This class provides a common style LEMON iterator that traverses

   630     /// the active nodes of the Bellman-Ford algorithm after the last

   631     /// phase. These nodes should be checked in the next phase to

   632     /// find augmenting arcs outgoing from them.

   633     class ActiveIt {

   634     public:

   635

   636       /// \brief Constructor.

   637       ///

   638       /// Constructor for getting the active nodes of the given BellmanFord

   639       /// instance.

   640       ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)

   641       {

   642         _index = _algorithm->_process.size() - 1;

   643       }

   644

   645       /// \brief Invalid constructor.

   646       ///

   647       /// Invalid constructor.

   648       ActiveIt(Invalid) : _algorithm(0), _index(-1) {}

   649

   650       /// \brief Conversion to \c Node.

   651       ///

   652       /// Conversion to \c Node.

   653       operator Node() const {

   654         return _index >= 0 ? _algorithm->_process[_index] : INVALID;

   655       }

   656

   657       /// \brief Increment operator.

   658       ///

   659       /// Increment operator.

   660       ActiveIt& operator++() {

   661         --_index;

   662         return *this;

   663       }

   664

   665       bool operator==(const ActiveIt& it) const {

   666         return static_cast<Node>(*this) == static_cast<Node>(it);

   667       }

   668       bool operator!=(const ActiveIt& it) const {

   669         return static_cast<Node>(*this) != static_cast<Node>(it);

   670       }

   671       bool operator<(const ActiveIt& it) const {

   672         return static_cast<Node>(*this) < static_cast<Node>(it);

   673       }

   674

   675     private:

   676       const BellmanFord* _algorithm;

   677       int _index;

   678     };

   679

   680     /// \name Query Functions

   681     /// The result of the Bellman-Ford algorithm can be obtained using these

   682     /// functions.\n

   683     /// Either \ref run() or \ref init() should be called before using them.

   684

   685     ///@{

   686

   687     /// \brief The shortest path to the given node.

   688     ///

   689     /// Gives back the shortest path to the given node from the root(s).

   690     ///

   691     /// \warning \c t should be reached from the root(s).

   692     ///

   693     /// \pre Either \ref run() or \ref init() must be called before

   694     /// using this function.

   695     Path path(Node t) const

   696     {

   697       return Path(*_gr, *_pred, t);

   698     }

   699

   700     /// \brief The distance of the given node from the root(s).

   701     ///

   702     /// Returns the distance of the given node from the root(s).

   703     ///

   704     /// \warning If node \c v is not reached from the root(s), then

   705     /// the return value of this function is undefined.

   706     ///

   707     /// \pre Either \ref run() or \ref init() must be called before

   708     /// using this function.

   709     Value dist(Node v) const { return (*_dist)[v]; }

   710

   711     /// \brief Returns the 'previous arc' of the shortest path tree for

   712     /// the given node.

   713     ///

   714     /// This function returns the 'previous arc' of the shortest path

   715     /// tree for node \c v, i.e. it returns the last arc of a

   716     /// shortest path from a root to \c v. It is \c INVALID if \c v

   717     /// is not reached from the root(s) or if \c v is a root.

   718     ///

   719     /// The shortest path tree used here is equal to the shortest path

   720     /// tree used in \ref predNode() and \predMap().

   721     ///

   722     /// \pre Either \ref run() or \ref init() must be called before

   723     /// using this function.

   724     Arc predArc(Node v) const { return (*_pred)[v]; }

   725

   726     /// \brief Returns the 'previous node' of the shortest path tree for

   727     /// the given node.

   728     ///

   729     /// This function returns the 'previous node' of the shortest path

   730     /// tree for node \c v, i.e. it returns the last but one node of

   731     /// a shortest path from a root to \c v. It is \c INVALID if \c v

   732     /// is not reached from the root(s) or if \c v is a root.

   733     ///

   734     /// The shortest path tree used here is equal to the shortest path

   735     /// tree used in \ref predArc() and \predMap().

   736     ///

   737     /// \pre Either \ref run() or \ref init() must be called before

   738     /// using this function.

   739     Node predNode(Node v) const {

   740       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);

   741     }

   742

   743     /// \brief Returns a const reference to the node map that stores the

   744     /// distances of the nodes.

   745     ///

   746     /// Returns a const reference to the node map that stores the distances

   747     /// of the nodes calculated by the algorithm.

   748     ///

   749     /// \pre Either \ref run() or \ref init() must be called before

   750     /// using this function.

   751     const DistMap &distMap() const { return *_dist;}

   752

   753     /// \brief Returns a const reference to the node map that stores the

   754     /// predecessor arcs.

   755     ///

   756     /// Returns a const reference to the node map that stores the predecessor

   757     /// arcs, which form the shortest path tree (forest).

   758     ///

   759     /// \pre Either \ref run() or \ref init() must be called before

   760     /// using this function.

   761     const PredMap &predMap() const { return *_pred; }

   762

   763     /// \brief Checks if a node is reached from the root(s).

   764     ///

   765     /// Returns \c true if \c v is reached from the root(s).

   766     ///

   767     /// \pre Either \ref run() or \ref init() must be called before

   768     /// using this function.

   769     bool reached(Node v) const {

   770       return (*_dist)[v] != OperationTraits::infinity();

   771     }

   772

   773     /// \brief Gives back a negative cycle.

   774     ///

   775     /// This function gives back a directed cycle with negative total

   776     /// length if the algorithm has already found one.

   777     /// Otherwise it gives back an empty path.

   778     lemon::Path<Digraph> negativeCycle() {

   779       typename Digraph::template NodeMap<int> state(*_gr, -1);

   780       lemon::Path<Digraph> cycle;

   781       for (int i = 0; i < int(_process.size()); ++i) {

   782         if (state[_process[i]] != -1) continue;

   783         for (Node v = _process[i]; (*_pred)[v] != INVALID;

   784              v = _gr->source((*_pred)[v])) {

   785           if (state[v] == i) {

   786             cycle.addFront((*_pred)[v]);

   787             for (Node u = _gr->source((*_pred)[v]); u != v;

   788                  u = _gr->source((*_pred)[u])) {

   789               cycle.addFront((*_pred)[u]);

   790             }

   791             return cycle;

   792           }

   793           else if (state[v] >= 0) {

   794             break;

   795           }

   796           state[v] = i;

   797         }

   798       }

   799       return cycle;

   800     }

   801

   802     ///@}

   803   };

   804

   805   /// \brief Default traits class of bellmanFord() function.

   806   ///

   807   /// Default traits class of bellmanFord() function.

   808   /// \tparam GR The type of the digraph.

   809   /// \tparam LEN The type of the length map.

   810   template <typename GR, typename LEN>

   811   struct BellmanFordWizardDefaultTraits {

   812     /// The type of the digraph the algorithm runs on.

   813     typedef GR Digraph;

   814

   815     /// \brief The type of the map that stores the arc lengths.

   816     ///

   817     /// The type of the map that stores the arc lengths.

   818     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.

   819     typedef LEN LengthMap;

   820

   821     /// The type of the arc lengths.

   822     typedef typename LEN::Value Value;

   823

   824     /// \brief Operation traits for Bellman-Ford algorithm.

   825     ///

   826     /// It defines the used operations and the infinity value for the

   827     /// given \c Value type.

   828     /// \see BellmanFordDefaultOperationTraits

   829     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;

   830

   831     /// \brief The type of the map that stores the last

   832     /// arcs of the shortest paths.

   833     ///

   834     /// The type of the map that stores the last arcs of the shortest paths.

   835     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

   836     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;

   837

   838     /// \brief Instantiates a \c PredMap.

   839     ///

   840     /// This function instantiates a \ref PredMap.

   841     /// \param g is the digraph to which we would like to define the

   842     /// \ref PredMap.

   843     static PredMap *createPredMap(const GR &g) {

   844       return new PredMap(g);

   845     }

   846

   847     /// \brief The type of the map that stores the distances of the nodes.

   848     ///

   849     /// The type of the map that stores the distances of the nodes.

   850     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

   851     typedef typename GR::template NodeMap<Value> DistMap;

   852

   853     /// \brief Instantiates a \c DistMap.

   854     ///

   855     /// This function instantiates a \ref DistMap.

   856     /// \param g is the digraph to which we would like to define the

   857     /// \ref DistMap.

   858     static DistMap *createDistMap(const GR &g) {

   859       return new DistMap(g);

   860     }

   861

   862     ///The type of the shortest paths.

   863

   864     ///The type of the shortest paths.

   865     ///It must meet the \ref concepts::Path "Path" concept.

   866     typedef lemon::Path<Digraph> Path;

   867   };

   868

   869   /// \brief Default traits class used by BellmanFordWizard.

   870   ///

   871   /// Default traits class used by BellmanFordWizard.

   872   /// \tparam GR The type of the digraph.

   873   /// \tparam LEN The type of the length map.

   874   template <typename GR, typename LEN>

   875   class BellmanFordWizardBase

   876     : public BellmanFordWizardDefaultTraits<GR, LEN> {

   877

   878     typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;

   879   protected:

   880     // Type of the nodes in the digraph.

   881     typedef typename Base::Digraph::Node Node;

   882

   883     // Pointer to the underlying digraph.

   884     void *_graph;

   885     // Pointer to the length map

   886     void *_length;

   887     // Pointer to the map of predecessors arcs.

   888     void *_pred;

   889     // Pointer to the map of distances.

   890     void *_dist;

   891     //Pointer to the shortest path to the target node.

   892     void *_path;

   893     //Pointer to the distance of the target node.

   894     void *_di;

   895

   896     public:

   897     /// Constructor.

   898

   899     /// This constructor does not require parameters, it initiates

   900     /// all of the attributes to default values \c 0.

   901     BellmanFordWizardBase() :

   902       _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}

   903

   904     /// Constructor.

   905

   906     /// This constructor requires two parameters,

   907     /// others are initiated to \c 0.

   908     /// \param gr The digraph the algorithm runs on.

   909     /// \param len The length map.

   910     BellmanFordWizardBase(const GR& gr,

   911 			  const LEN& len) :

   912       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),

   913       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),

   914       _pred(0), _dist(0), _path(0), _di(0) {}

   915

   916   };

   917

   918   /// \brief Auxiliary class for the function-type interface of the

   919   /// \ref BellmanFord "Bellman-Ford" algorithm.

   920   ///

   921   /// This auxiliary class is created to implement the

   922   /// \ref bellmanFord() "function-type interface" of the

   923   /// \ref BellmanFord "Bellman-Ford" algorithm.

   924   /// It does not have own \ref run() method, it uses the

   925   /// functions and features of the plain \ref BellmanFord.

   926   ///

   927   /// This class should only be used through the \ref bellmanFord()

   928   /// function, which makes it easier to use the algorithm.

   929   template<class TR>

   930   class BellmanFordWizard : public TR {

   931     typedef TR Base;

   932

   933     typedef typename TR::Digraph Digraph;

   934

   935     typedef typename Digraph::Node Node;

   936     typedef typename Digraph::NodeIt NodeIt;

   937     typedef typename Digraph::Arc Arc;

   938     typedef typename Digraph::OutArcIt ArcIt;

   939

   940     typedef typename TR::LengthMap LengthMap;

   941     typedef typename LengthMap::Value Value;

   942     typedef typename TR::PredMap PredMap;

   943     typedef typename TR::DistMap DistMap;

   944     typedef typename TR::Path Path;

   945

   946   public:

   947     /// Constructor.

   948     BellmanFordWizard() : TR() {}

   949

   950     /// \brief Constructor that requires parameters.

   951     ///

   952     /// Constructor that requires parameters.

   953     /// These parameters will be the default values for the traits class.

   954     /// \param gr The digraph the algorithm runs on.

   955     /// \param len The length map.

   956     BellmanFordWizard(const Digraph& gr, const LengthMap& len)

   957       : TR(gr, len) {}

   958

   959     /// \brief Copy constructor

   960     BellmanFordWizard(const TR &b) : TR(b) {}

   961

   962     ~BellmanFordWizard() {}

   963

   964     /// \brief Runs the Bellman-Ford algorithm from the given source node.

   965     ///

   966     /// This method runs the Bellman-Ford algorithm from the given source

   967     /// node in order to compute the shortest path to each node.

   968     void run(Node s) {

   969       BellmanFord<Digraph,LengthMap,TR>

   970 	bf(*reinterpret_cast<const Digraph*>(Base::_graph),

   971            *reinterpret_cast<const LengthMap*>(Base::_length));

   972       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

   973       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

   974       bf.run(s);

   975     }

   976

   977     /// \brief Runs the Bellman-Ford algorithm to find the shortest path

   978     /// between \c s and \c t.

   979     ///

   980     /// This method runs the Bellman-Ford algorithm from node \c s

   981     /// in order to compute the shortest path to node \c t.

   982     /// Actually, it computes the shortest path to each node, but using

   983     /// this function you can retrieve the distance and the shortest path

   984     /// for a single target node easier.

   985     ///

   986     /// \return \c true if \c t is reachable form \c s.

   987     bool run(Node s, Node t) {

   988       BellmanFord<Digraph,LengthMap,TR>

   989         bf(*reinterpret_cast<const Digraph*>(Base::_graph),

   990            *reinterpret_cast<const LengthMap*>(Base::_length));

   991       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

   992       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

   993       bf.run(s);

   994       if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);

   995       if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);

   996       return bf.reached(t);

   997     }

   998

   999     template<class T>

  1000     struct SetPredMapBase : public Base {

  1001       typedef T PredMap;

  1002       static PredMap *createPredMap(const Digraph &) { return 0; };

  1003       SetPredMapBase(const TR &b) : TR(b) {}

  1004     };

  1005

  1006     /// \brief \ref named-templ-param "Named parameter" for setting

  1007     /// the predecessor map.

  1008     ///

  1009     /// \ref named-templ-param "Named parameter" for setting

  1010     /// the map that stores the predecessor arcs of the nodes.

  1011     template<class T>

  1012     BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {

  1013       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));

  1014       return BellmanFordWizard<SetPredMapBase<T> >(*this);

  1015     }

  1016

  1017     template<class T>

  1018     struct SetDistMapBase : public Base {

  1019       typedef T DistMap;

  1020       static DistMap *createDistMap(const Digraph &) { return 0; };

  1021       SetDistMapBase(const TR &b) : TR(b) {}

  1022     };

  1023

  1024     /// \brief \ref named-templ-param "Named parameter" for setting

  1025     /// the distance map.

  1026     ///

  1027     /// \ref named-templ-param "Named parameter" for setting

  1028     /// the map that stores the distances of the nodes calculated

  1029     /// by the algorithm.

  1030     template<class T>

  1031     BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {

  1032       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));

  1033       return BellmanFordWizard<SetDistMapBase<T> >(*this);

  1034     }

  1035

  1036     template<class T>

  1037     struct SetPathBase : public Base {

  1038       typedef T Path;

  1039       SetPathBase(const TR &b) : TR(b) {}

  1040     };

  1041

  1042     /// \brief \ref named-func-param "Named parameter" for getting

  1043     /// the shortest path to the target node.

  1044     ///

  1045     /// \ref named-func-param "Named parameter" for getting

  1046     /// the shortest path to the target node.

  1047     template<class T>

  1048     BellmanFordWizard<SetPathBase<T> > path(const T &t)

  1049     {

  1050       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));

  1051       return BellmanFordWizard<SetPathBase<T> >(*this);

  1052     }

  1053

  1054     /// \brief \ref named-func-param "Named parameter" for getting

  1055     /// the distance of the target node.

  1056     ///

  1057     /// \ref named-func-param "Named parameter" for getting

  1058     /// the distance of the target node.

  1059     BellmanFordWizard dist(const Value &d)

  1060     {

  1061       Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));

  1062       return *this;

  1063     }

  1064

  1065   };

  1066

  1067   /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"

  1068   /// algorithm.

  1069   ///

  1070   /// \ingroup shortest_path

  1071   /// Function type interface for the \ref BellmanFord "Bellman-Ford"

  1072   /// algorithm.

  1073   ///

  1074   /// This function also has several \ref named-templ-func-param

  1075   /// "named parameters", they are declared as the members of class

  1076   /// \ref BellmanFordWizard.

  1077   /// The following examples show how to use these parameters.

  1078   /// \code

  1079   ///   // Compute shortest path from node s to each node

  1080   ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);

  1081   ///

  1082   ///   // Compute shortest path from s to t

  1083   ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);

  1084   /// \endcode

  1085   /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"

  1086   /// to the end of the parameter list.

  1087   /// \sa BellmanFordWizard

  1088   /// \sa BellmanFord

  1089   template<typename GR, typename LEN>

  1090   BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >

  1091   bellmanFord(const GR& digraph,

  1092 	      const LEN& length)

  1093   {

  1094     return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);

  1095   }

  1096

  1097 } //END OF NAMESPACE LEMON

  1098

  1099 #endif

  1100