lemon/bellman_ford.h
changeset 877 141f9c0db4a3
parent 844 a6eb9698c321
child 881 b89e46862dc2
equal deleted inserted replaced
8:ad1fe6c84fef 9:fccaa9f67f54
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    34 #include <limits>
    34 #include <limits>
    35 
    35 
    36 namespace lemon {
    36 namespace lemon {
    37 
    37 
    38   /// \brief Default operation traits for the BellmanFord algorithm class.
    38   /// \brief Default operation traits for the BellmanFord algorithm class.
    39   ///  
    39   ///
    40   /// This operation traits class defines all computational operations
    40   /// This operation traits class defines all computational operations
    41   /// and constants that are used in the Bellman-Ford algorithm.
    41   /// and constants that are used in the Bellman-Ford algorithm.
    42   /// The default implementation is based on the \c numeric_limits class.
    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
    43   /// If the numeric type does not have infinity value, then the maximum
    44   /// value is used as extremal infinity value.
    44   /// value is used as extremal infinity value.
    45   ///
    45   ///
    46   /// \see BellmanFordToleranceOperationTraits
    46   /// \see BellmanFordToleranceOperationTraits
    47   template <
    47   template <
    48     typename V, 
    48     typename V,
    49     bool has_inf = std::numeric_limits<V>::has_infinity>
    49     bool has_inf = std::numeric_limits<V>::has_infinity>
    50   struct BellmanFordDefaultOperationTraits {
    50   struct BellmanFordDefaultOperationTraits {
    51     /// \brief Value type for the algorithm.
    51     /// \brief Value type for the algorithm.
    52     typedef V Value;
    52     typedef V Value;
    53     /// \brief Gives back the zero value of the type.
    53     /// \brief Gives back the zero value of the type.
    84     }
    84     }
    85     static bool less(const Value& left, const Value& right) {
    85     static bool less(const Value& left, const Value& right) {
    86       return left < right;
    86       return left < right;
    87     }
    87     }
    88   };
    88   };
    89   
    89 
    90   /// \brief Operation traits for the BellmanFord algorithm class
    90   /// \brief Operation traits for the BellmanFord algorithm class
    91   /// using tolerance.
    91   /// using tolerance.
    92   ///
    92   ///
    93   /// This operation traits class defines all computational operations
    93   /// This operation traits class defines all computational operations
    94   /// and constants that are used in the Bellman-Ford algorithm.
    94   /// and constants that are used in the Bellman-Ford algorithm.
   137   /// Default traits class of BellmanFord class.
   137   /// Default traits class of BellmanFord class.
   138   /// \param GR The type of the digraph.
   138   /// \param GR The type of the digraph.
   139   /// \param LEN The type of the length map.
   139   /// \param LEN The type of the length map.
   140   template<typename GR, typename LEN>
   140   template<typename GR, typename LEN>
   141   struct BellmanFordDefaultTraits {
   141   struct BellmanFordDefaultTraits {
   142     /// The type of the digraph the algorithm runs on. 
   142     /// The type of the digraph the algorithm runs on.
   143     typedef GR Digraph;
   143     typedef GR Digraph;
   144 
   144 
   145     /// \brief The type of the map that stores the arc lengths.
   145     /// \brief The type of the map that stores the arc lengths.
   146     ///
   146     ///
   147     /// The type of the map that stores the arc lengths.
   147     /// The type of the map that stores the arc lengths.
   156     /// It defines the used operations and the infinity value for the
   156     /// It defines the used operations and the infinity value for the
   157     /// given \c Value type.
   157     /// given \c Value type.
   158     /// \see BellmanFordDefaultOperationTraits,
   158     /// \see BellmanFordDefaultOperationTraits,
   159     /// BellmanFordToleranceOperationTraits
   159     /// BellmanFordToleranceOperationTraits
   160     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   160     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   161  
   161 
   162     /// \brief The type of the map that stores the last arcs of the 
   162     /// \brief The type of the map that stores the last arcs of the
   163     /// shortest paths.
   163     /// shortest paths.
   164     /// 
   164     ///
   165     /// The type of the map that stores the last
   165     /// The type of the map that stores the last
   166     /// arcs of the shortest paths.
   166     /// arcs of the shortest paths.
   167     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   167     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   168     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   168     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   169 
   169 
   170     /// \brief Instantiates a \c PredMap.
   170     /// \brief Instantiates a \c PredMap.
   171     /// 
   171     ///
   172     /// This function instantiates a \ref PredMap. 
   172     /// This function instantiates a \ref PredMap.
   173     /// \param g is the digraph to which we would like to define the
   173     /// \param g is the digraph to which we would like to define the
   174     /// \ref PredMap.
   174     /// \ref PredMap.
   175     static PredMap *createPredMap(const GR& g) {
   175     static PredMap *createPredMap(const GR& g) {
   176       return new PredMap(g);
   176       return new PredMap(g);
   177     }
   177     }
   182     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   182     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   183     typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
   183     typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
   184 
   184 
   185     /// \brief Instantiates a \c DistMap.
   185     /// \brief Instantiates a \c DistMap.
   186     ///
   186     ///
   187     /// This function instantiates a \ref DistMap. 
   187     /// This function instantiates a \ref DistMap.
   188     /// \param g is the digraph to which we would like to define the 
   188     /// \param g is the digraph to which we would like to define the
   189     /// \ref DistMap.
   189     /// \ref DistMap.
   190     static DistMap *createDistMap(const GR& g) {
   190     static DistMap *createDistMap(const GR& g) {
   191       return new DistMap(g);
   191       return new DistMap(g);
   192     }
   192     }
   193 
   193 
   194   };
   194   };
   195   
   195 
   196   /// \brief %BellmanFord algorithm class.
   196   /// \brief %BellmanFord algorithm class.
   197   ///
   197   ///
   198   /// \ingroup shortest_path
   198   /// \ingroup shortest_path
   199   /// This class provides an efficient implementation of the Bellman-Ford 
   199   /// This class provides an efficient implementation of the Bellman-Ford
   200   /// algorithm. The maximum time complexity of the algorithm is
   200   /// algorithm. The maximum time complexity of the algorithm is
   201   /// <tt>O(ne)</tt>.
   201   /// <tt>O(ne)</tt>.
   202   ///
   202   ///
   203   /// The Bellman-Ford algorithm solves the single-source shortest path
   203   /// The Bellman-Ford algorithm solves the single-source shortest path
   204   /// problem when the arcs can have negative lengths, but the digraph
   204   /// problem when the arcs can have negative lengths, but the digraph
   205   /// should not contain directed cycles with negative total length.
   205   /// should not contain directed cycles with negative total length.
   206   /// If all arc costs are non-negative, consider to use the Dijkstra
   206   /// If all arc costs are non-negative, consider to use the Dijkstra
   207   /// algorithm instead, since it is more efficient.
   207   /// algorithm instead, since it is more efficient.
   208   ///
   208   ///
   209   /// The arc lengths are passed to the algorithm using a
   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 
   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
   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.
   212   /// \ref concepts::ReadMap::Value "Value" type of the length map.
   213   ///
   213   ///
   214   /// There is also a \ref bellmanFord() "function-type interface" for the
   214   /// There is also a \ref bellmanFord() "function-type interface" for the
   215   /// Bellman-Ford algorithm, which is convenient in the simplier cases and
   215   /// Bellman-Ford algorithm, which is convenient in the simplier cases and
   235   class BellmanFord {
   235   class BellmanFord {
   236   public:
   236   public:
   237 
   237 
   238     ///The type of the underlying digraph.
   238     ///The type of the underlying digraph.
   239     typedef typename TR::Digraph Digraph;
   239     typedef typename TR::Digraph Digraph;
   240     
   240 
   241     /// \brief The type of the arc lengths.
   241     /// \brief The type of the arc lengths.
   242     typedef typename TR::LengthMap::Value Value;
   242     typedef typename TR::LengthMap::Value Value;
   243     /// \brief The type of the map that stores the arc lengths.
   243     /// \brief The type of the map that stores the arc lengths.
   244     typedef typename TR::LengthMap LengthMap;
   244     typedef typename TR::LengthMap LengthMap;
   245     /// \brief The type of the map that stores the last
   245     /// \brief The type of the map that stores the last
   282     std::vector<Node> _process;
   282     std::vector<Node> _process;
   283 
   283 
   284     // Creates the maps if necessary.
   284     // Creates the maps if necessary.
   285     void create_maps() {
   285     void create_maps() {
   286       if(!_pred) {
   286       if(!_pred) {
   287 	_local_pred = true;
   287         _local_pred = true;
   288 	_pred = Traits::createPredMap(*_gr);
   288         _pred = Traits::createPredMap(*_gr);
   289       }
   289       }
   290       if(!_dist) {
   290       if(!_dist) {
   291 	_local_dist = true;
   291         _local_dist = true;
   292 	_dist = Traits::createDistMap(*_gr);
   292         _dist = Traits::createDistMap(*_gr);
   293       }
   293       }
   294       if(!_mask) {
   294       if(!_mask) {
   295         _mask = new MaskMap(*_gr);
   295         _mask = new MaskMap(*_gr);
   296       }
   296       }
   297     }
   297     }
   298     
   298 
   299   public :
   299   public :
   300  
   300 
   301     typedef BellmanFord Create;
   301     typedef BellmanFord Create;
   302 
   302 
   303     /// \name Named Template Parameters
   303     /// \name Named Template Parameters
   304 
   304 
   305     ///@{
   305     ///@{
   318     ///
   318     ///
   319     /// \ref named-templ-param "Named parameter" for setting
   319     /// \ref named-templ-param "Named parameter" for setting
   320     /// \c PredMap type.
   320     /// \c PredMap type.
   321     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   321     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   322     template <class T>
   322     template <class T>
   323     struct SetPredMap 
   323     struct SetPredMap
   324       : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
   324       : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
   325       typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   325       typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   326     };
   326     };
   327     
   327 
   328     template <class T>
   328     template <class T>
   329     struct SetDistMapTraits : public Traits {
   329     struct SetDistMapTraits : public Traits {
   330       typedef T DistMap;
   330       typedef T DistMap;
   331       static DistMap *createDistMap(const Digraph&) {
   331       static DistMap *createDistMap(const Digraph&) {
   332         LEMON_ASSERT(false, "DistMap is not initialized");
   332         LEMON_ASSERT(false, "DistMap is not initialized");
   339     ///
   339     ///
   340     /// \ref named-templ-param "Named parameter" for setting
   340     /// \ref named-templ-param "Named parameter" for setting
   341     /// \c DistMap type.
   341     /// \c DistMap type.
   342     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   342     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   343     template <class T>
   343     template <class T>
   344     struct SetDistMap 
   344     struct SetDistMap
   345       : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
   345       : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
   346       typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   346       typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   347     };
   347     };
   348 
   348 
   349     template <class T>
   349     template <class T>
   350     struct SetOperationTraitsTraits : public Traits {
   350     struct SetOperationTraitsTraits : public Traits {
   351       typedef T OperationTraits;
   351       typedef T OperationTraits;
   352     };
   352     };
   353     
   353 
   354     /// \brief \ref named-templ-param "Named parameter" for setting 
   354     /// \brief \ref named-templ-param "Named parameter" for setting
   355     /// \c OperationTraits type.
   355     /// \c OperationTraits type.
   356     ///
   356     ///
   357     /// \ref named-templ-param "Named parameter" for setting
   357     /// \ref named-templ-param "Named parameter" for setting
   358     /// \c OperationTraits type.
   358     /// \c OperationTraits type.
   359     /// For more information, see \ref BellmanFordDefaultOperationTraits.
   359     /// For more information, see \ref BellmanFordDefaultOperationTraits.
   361     struct SetOperationTraits
   361     struct SetOperationTraits
   362       : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   362       : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   363       typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
   363       typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
   364       Create;
   364       Create;
   365     };
   365     };
   366     
   366 
   367     ///@}
   367     ///@}
   368 
   368 
   369   protected:
   369   protected:
   370     
   370 
   371     BellmanFord() {}
   371     BellmanFord() {}
   372 
   372 
   373   public:      
   373   public:
   374     
   374 
   375     /// \brief Constructor.
   375     /// \brief Constructor.
   376     ///
   376     ///
   377     /// Constructor.
   377     /// Constructor.
   378     /// \param g The digraph the algorithm runs on.
   378     /// \param g The digraph the algorithm runs on.
   379     /// \param length The length map used by the algorithm.
   379     /// \param length The length map used by the algorithm.
   380     BellmanFord(const Digraph& g, const LengthMap& length) :
   380     BellmanFord(const Digraph& g, const LengthMap& length) :
   381       _gr(&g), _length(&length),
   381       _gr(&g), _length(&length),
   382       _pred(0), _local_pred(false),
   382       _pred(0), _local_pred(false),
   383       _dist(0), _local_dist(false), _mask(0) {}
   383       _dist(0), _local_dist(false), _mask(0) {}
   384     
   384 
   385     ///Destructor.
   385     ///Destructor.
   386     ~BellmanFord() {
   386     ~BellmanFord() {
   387       if(_local_pred) delete _pred;
   387       if(_local_pred) delete _pred;
   388       if(_local_dist) delete _dist;
   388       if(_local_dist) delete _dist;
   389       if(_mask) delete _mask;
   389       if(_mask) delete _mask;
   406     /// The destructor deallocates this automatically allocated map,
   406     /// The destructor deallocates this automatically allocated map,
   407     /// of course.
   407     /// of course.
   408     /// \return <tt>(*this)</tt>
   408     /// \return <tt>(*this)</tt>
   409     BellmanFord &predMap(PredMap &map) {
   409     BellmanFord &predMap(PredMap &map) {
   410       if(_local_pred) {
   410       if(_local_pred) {
   411 	delete _pred;
   411         delete _pred;
   412 	_local_pred=false;
   412         _local_pred=false;
   413       }
   413       }
   414       _pred = &map;
   414       _pred = &map;
   415       return *this;
   415       return *this;
   416     }
   416     }
   417 
   417 
   424     /// The destructor deallocates this automatically allocated map,
   424     /// The destructor deallocates this automatically allocated map,
   425     /// of course.
   425     /// of course.
   426     /// \return <tt>(*this)</tt>
   426     /// \return <tt>(*this)</tt>
   427     BellmanFord &distMap(DistMap &map) {
   427     BellmanFord &distMap(DistMap &map) {
   428       if(_local_dist) {
   428       if(_local_dist) {
   429 	delete _dist;
   429         delete _dist;
   430 	_local_dist=false;
   430         _local_dist=false;
   431       }
   431       }
   432       _dist = &map;
   432       _dist = &map;
   433       return *this;
   433       return *this;
   434     }
   434     }
   435 
   435 
   443     /// \ref limitedStart().
   443     /// \ref limitedStart().
   444 
   444 
   445     ///@{
   445     ///@{
   446 
   446 
   447     /// \brief Initializes the internal data structures.
   447     /// \brief Initializes the internal data structures.
   448     /// 
   448     ///
   449     /// Initializes the internal data structures. The optional parameter
   449     /// Initializes the internal data structures. The optional parameter
   450     /// is the initial distance of each node.
   450     /// is the initial distance of each node.
   451     void init(const Value value = OperationTraits::infinity()) {
   451     void init(const Value value = OperationTraits::infinity()) {
   452       create_maps();
   452       create_maps();
   453       for (NodeIt it(*_gr); it != INVALID; ++it) {
   453       for (NodeIt it(*_gr); it != INVALID; ++it) {
   454 	_pred->set(it, INVALID);
   454         _pred->set(it, INVALID);
   455 	_dist->set(it, value);
   455         _dist->set(it, value);
   456       }
   456       }
   457       _process.clear();
   457       _process.clear();
   458       if (OperationTraits::less(value, OperationTraits::infinity())) {
   458       if (OperationTraits::less(value, OperationTraits::infinity())) {
   459 	for (NodeIt it(*_gr); it != INVALID; ++it) {
   459         for (NodeIt it(*_gr); it != INVALID; ++it) {
   460 	  _process.push_back(it);
   460           _process.push_back(it);
   461 	  _mask->set(it, true);
   461           _mask->set(it, true);
   462 	}
   462         }
   463       } else {
   463       } else {
   464 	for (NodeIt it(*_gr); it != INVALID; ++it) {
   464         for (NodeIt it(*_gr); it != INVALID; ++it) {
   465 	  _mask->set(it, false);
   465           _mask->set(it, false);
   466 	}
   466         }
   467       }
   467       }
   468     }
   468     }
   469     
   469 
   470     /// \brief Adds a new source node.
   470     /// \brief Adds a new source node.
   471     ///
   471     ///
   472     /// This function adds a new source node. The optional second parameter
   472     /// This function adds a new source node. The optional second parameter
   473     /// is the initial distance of the node.
   473     /// is the initial distance of the node.
   474     void addSource(Node source, Value dst = OperationTraits::zero()) {
   474     void addSource(Node source, Value dst = OperationTraits::zero()) {
   475       _dist->set(source, dst);
   475       _dist->set(source, dst);
   476       if (!(*_mask)[source]) {
   476       if (!(*_mask)[source]) {
   477 	_process.push_back(source);
   477         _process.push_back(source);
   478 	_mask->set(source, true);
   478         _mask->set(source, true);
   479       }
   479       }
   480     }
   480     }
   481 
   481 
   482     /// \brief Executes one round from the Bellman-Ford algorithm.
   482     /// \brief Executes one round from the Bellman-Ford algorithm.
   483     ///
   483     ///
   498     /// paths.
   498     /// paths.
   499     ///
   499     ///
   500     /// \see ActiveIt
   500     /// \see ActiveIt
   501     bool processNextRound() {
   501     bool processNextRound() {
   502       for (int i = 0; i < int(_process.size()); ++i) {
   502       for (int i = 0; i < int(_process.size()); ++i) {
   503 	_mask->set(_process[i], false);
   503         _mask->set(_process[i], false);
   504       }
   504       }
   505       std::vector<Node> nextProcess;
   505       std::vector<Node> nextProcess;
   506       std::vector<Value> values(_process.size());
   506       std::vector<Value> values(_process.size());
   507       for (int i = 0; i < int(_process.size()); ++i) {
   507       for (int i = 0; i < int(_process.size()); ++i) {
   508 	values[i] = (*_dist)[_process[i]];
   508         values[i] = (*_dist)[_process[i]];
   509       }
   509       }
   510       for (int i = 0; i < int(_process.size()); ++i) {
   510       for (int i = 0; i < int(_process.size()); ++i) {
   511 	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   511         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   512 	  Node target = _gr->target(it);
   512           Node target = _gr->target(it);
   513 	  Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
   513           Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
   514 	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
   514           if (OperationTraits::less(relaxed, (*_dist)[target])) {
   515 	    _pred->set(target, it);
   515             _pred->set(target, it);
   516 	    _dist->set(target, relaxed);
   516             _dist->set(target, relaxed);
   517 	    if (!(*_mask)[target]) {
   517             if (!(*_mask)[target]) {
   518 	      _mask->set(target, true);
   518               _mask->set(target, true);
   519 	      nextProcess.push_back(target);
   519               nextProcess.push_back(target);
   520 	    }
   520             }
   521 	  }	  
   521           }
   522 	}
   522         }
   523       }
   523       }
   524       _process.swap(nextProcess);
   524       _process.swap(nextProcess);
   525       return _process.empty();
   525       return _process.empty();
   526     }
   526     }
   527 
   527 
   539     /// paths.
   539     /// paths.
   540     ///
   540     ///
   541     /// \see ActiveIt
   541     /// \see ActiveIt
   542     bool processNextWeakRound() {
   542     bool processNextWeakRound() {
   543       for (int i = 0; i < int(_process.size()); ++i) {
   543       for (int i = 0; i < int(_process.size()); ++i) {
   544 	_mask->set(_process[i], false);
   544         _mask->set(_process[i], false);
   545       }
   545       }
   546       std::vector<Node> nextProcess;
   546       std::vector<Node> nextProcess;
   547       for (int i = 0; i < int(_process.size()); ++i) {
   547       for (int i = 0; i < int(_process.size()); ++i) {
   548 	for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   548         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
   549 	  Node target = _gr->target(it);
   549           Node target = _gr->target(it);
   550 	  Value relaxed = 
   550           Value relaxed =
   551 	    OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
   551             OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
   552 	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
   552           if (OperationTraits::less(relaxed, (*_dist)[target])) {
   553 	    _pred->set(target, it);
   553             _pred->set(target, it);
   554 	    _dist->set(target, relaxed);
   554             _dist->set(target, relaxed);
   555 	    if (!(*_mask)[target]) {
   555             if (!(*_mask)[target]) {
   556 	      _mask->set(target, true);
   556               _mask->set(target, true);
   557 	      nextProcess.push_back(target);
   557               nextProcess.push_back(target);
   558 	    }
   558             }
   559 	  }	  
   559           }
   560 	}
   560         }
   561       }
   561       }
   562       _process.swap(nextProcess);
   562       _process.swap(nextProcess);
   563       return _process.empty();
   563       return _process.empty();
   564     }
   564     }
   565 
   565 
   577     /// \pre init() must be called and at least one root node should be
   577     /// \pre init() must be called and at least one root node should be
   578     /// added with addSource() before using this function.
   578     /// added with addSource() before using this function.
   579     void start() {
   579     void start() {
   580       int num = countNodes(*_gr) - 1;
   580       int num = countNodes(*_gr) - 1;
   581       for (int i = 0; i < num; ++i) {
   581       for (int i = 0; i < num; ++i) {
   582 	if (processNextWeakRound()) break;
   582         if (processNextWeakRound()) break;
   583       }
   583       }
   584     }
   584     }
   585 
   585 
   586     /// \brief Executes the algorithm and checks the negative cycles.
   586     /// \brief Executes the algorithm and checks the negative cycles.
   587     ///
   587     ///
   589     ///
   589     ///
   590     /// This method runs the Bellman-Ford algorithm from the root node(s)
   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
   591     /// in order to compute the shortest path to each node and also checks
   592     /// if the digraph contains cycles with negative total length.
   592     /// if the digraph contains cycles with negative total length.
   593     ///
   593     ///
   594     /// The algorithm computes 
   594     /// The algorithm computes
   595     /// - the shortest path tree (forest),
   595     /// - the shortest path tree (forest),
   596     /// - the distance of each node from the root(s).
   596     /// - the distance of each node from the root(s).
   597     /// 
   597     ///
   598     /// \return \c false if there is a negative cycle in the digraph.
   598     /// \return \c false if there is a negative cycle in the digraph.
   599     ///
   599     ///
   600     /// \pre init() must be called and at least one root node should be
   600     /// \pre init() must be called and at least one root node should be
   601     /// added with addSource() before using this function. 
   601     /// added with addSource() before using this function.
   602     bool checkedStart() {
   602     bool checkedStart() {
   603       int num = countNodes(*_gr);
   603       int num = countNodes(*_gr);
   604       for (int i = 0; i < num; ++i) {
   604       for (int i = 0; i < num; ++i) {
   605 	if (processNextWeakRound()) return true;
   605         if (processNextWeakRound()) return true;
   606       }
   606       }
   607       return _process.empty();
   607       return _process.empty();
   608     }
   608     }
   609 
   609 
   610     /// \brief Executes the algorithm with arc number limit.
   610     /// \brief Executes the algorithm with arc number limit.
   624     /// need the shortest paths and not only the distances, you should
   624     /// need the shortest paths and not only the distances, you should
   625     /// store the \ref predMap() "predecessor map" after each iteration
   625     /// store the \ref predMap() "predecessor map" after each iteration
   626     /// and build the path manually.
   626     /// and build the path manually.
   627     ///
   627     ///
   628     /// \pre init() must be called and at least one root node should be
   628     /// \pre init() must be called and at least one root node should be
   629     /// added with addSource() before using this function. 
   629     /// added with addSource() before using this function.
   630     void limitedStart(int num) {
   630     void limitedStart(int num) {
   631       for (int i = 0; i < num; ++i) {
   631       for (int i = 0; i < num; ++i) {
   632 	if (processNextRound()) break;
   632         if (processNextRound()) break;
   633       }
   633       }
   634     }
   634     }
   635     
   635 
   636     /// \brief Runs the algorithm from the given root node.
   636     /// \brief Runs the algorithm from the given root node.
   637     ///    
   637     ///
   638     /// This method runs the Bellman-Ford algorithm from the given root
   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.
   639     /// node \c s in order to compute the shortest path to each node.
   640     ///
   640     ///
   641     /// The algorithm computes
   641     /// The algorithm computes
   642     /// - the shortest path tree (forest),
   642     /// - the shortest path tree (forest),
   651     void run(Node s) {
   651     void run(Node s) {
   652       init();
   652       init();
   653       addSource(s);
   653       addSource(s);
   654       start();
   654       start();
   655     }
   655     }
   656     
   656 
   657     /// \brief Runs the algorithm from the given root node with arc
   657     /// \brief Runs the algorithm from the given root node with arc
   658     /// number limit.
   658     /// number limit.
   659     ///    
   659     ///
   660     /// This method runs the Bellman-Ford algorithm from the given root
   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
   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.
   662     /// node using only the paths consisting of at most \c num arcs.
   663     ///
   663     ///
   664     /// The algorithm computes
   664     /// The algorithm computes
   680     void run(Node s, int num) {
   680     void run(Node s, int num) {
   681       init();
   681       init();
   682       addSource(s);
   682       addSource(s);
   683       limitedStart(num);
   683       limitedStart(num);
   684     }
   684     }
   685     
   685 
   686     ///@}
   686     ///@}
   687 
   687 
   688     /// \brief LEMON iterator for getting the active nodes.
   688     /// \brief LEMON iterator for getting the active nodes.
   689     ///
   689     ///
   690     /// This class provides a common style LEMON iterator that traverses
   690     /// This class provides a common style LEMON iterator that traverses
   695     public:
   695     public:
   696 
   696 
   697       /// \brief Constructor.
   697       /// \brief Constructor.
   698       ///
   698       ///
   699       /// Constructor for getting the active nodes of the given BellmanFord
   699       /// Constructor for getting the active nodes of the given BellmanFord
   700       /// instance. 
   700       /// instance.
   701       ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
   701       ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
   702       {
   702       {
   703         _index = _algorithm->_process.size() - 1;
   703         _index = _algorithm->_process.size() - 1;
   704       }
   704       }
   705 
   705 
   709       ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
   709       ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
   710 
   710 
   711       /// \brief Conversion to \c Node.
   711       /// \brief Conversion to \c Node.
   712       ///
   712       ///
   713       /// Conversion to \c Node.
   713       /// Conversion to \c Node.
   714       operator Node() const { 
   714       operator Node() const {
   715         return _index >= 0 ? _algorithm->_process[_index] : INVALID;
   715         return _index >= 0 ? _algorithm->_process[_index] : INVALID;
   716       }
   716       }
   717 
   717 
   718       /// \brief Increment operator.
   718       /// \brief Increment operator.
   719       ///
   719       ///
   720       /// Increment operator.
   720       /// Increment operator.
   721       ActiveIt& operator++() {
   721       ActiveIt& operator++() {
   722         --_index;
   722         --_index;
   723         return *this; 
   723         return *this;
   724       }
   724       }
   725 
   725 
   726       bool operator==(const ActiveIt& it) const { 
   726       bool operator==(const ActiveIt& it) const {
   727         return static_cast<Node>(*this) == static_cast<Node>(it); 
   727         return static_cast<Node>(*this) == static_cast<Node>(it);
   728       }
   728       }
   729       bool operator!=(const ActiveIt& it) const { 
   729       bool operator!=(const ActiveIt& it) const {
   730         return static_cast<Node>(*this) != static_cast<Node>(it); 
   730         return static_cast<Node>(*this) != static_cast<Node>(it);
   731       }
   731       }
   732       bool operator<(const ActiveIt& it) const { 
   732       bool operator<(const ActiveIt& it) const {
   733         return static_cast<Node>(*this) < static_cast<Node>(it); 
   733         return static_cast<Node>(*this) < static_cast<Node>(it);
   734       }
   734       }
   735       
   735 
   736     private:
   736     private:
   737       const BellmanFord* _algorithm;
   737       const BellmanFord* _algorithm;
   738       int _index;
   738       int _index;
   739     };
   739     };
   740     
   740 
   741     /// \name Query Functions
   741     /// \name Query Functions
   742     /// The result of the Bellman-Ford algorithm can be obtained using these
   742     /// The result of the Bellman-Ford algorithm can be obtained using these
   743     /// functions.\n
   743     /// functions.\n
   744     /// Either \ref run() or \ref init() should be called before using them.
   744     /// Either \ref run() or \ref init() should be called before using them.
   745     
   745 
   746     ///@{
   746     ///@{
   747 
   747 
   748     /// \brief The shortest path to the given node.
   748     /// \brief The shortest path to the given node.
   749     ///    
   749     ///
   750     /// Gives back the shortest path to the given node from the root(s).
   750     /// Gives back the shortest path to the given node from the root(s).
   751     ///
   751     ///
   752     /// \warning \c t should be reached from the root(s).
   752     /// \warning \c t should be reached from the root(s).
   753     ///
   753     ///
   754     /// \pre Either \ref run() or \ref init() must be called before
   754     /// \pre Either \ref run() or \ref init() must be called before
   755     /// using this function.
   755     /// using this function.
   756     Path path(Node t) const
   756     Path path(Node t) const
   757     {
   757     {
   758       return Path(*_gr, *_pred, t);
   758       return Path(*_gr, *_pred, t);
   759     }
   759     }
   760 	  
   760 
   761     /// \brief The distance of the given node from the root(s).
   761     /// \brief The distance of the given node from the root(s).
   762     ///
   762     ///
   763     /// Returns the distance of the given node from the root(s).
   763     /// Returns the distance of the given node from the root(s).
   764     ///
   764     ///
   765     /// \warning If node \c v is not reached from the root(s), then
   765     /// \warning If node \c v is not reached from the root(s), then
   795     /// The shortest path tree used here is equal to the shortest path
   795     /// The shortest path tree used here is equal to the shortest path
   796     /// tree used in \ref predArc() and \ref predMap().
   796     /// tree used in \ref predArc() and \ref predMap().
   797     ///
   797     ///
   798     /// \pre Either \ref run() or \ref init() must be called before
   798     /// \pre Either \ref run() or \ref init() must be called before
   799     /// using this function.
   799     /// using this function.
   800     Node predNode(Node v) const { 
   800     Node predNode(Node v) const {
   801       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
   801       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
   802     }
   802     }
   803     
   803 
   804     /// \brief Returns a const reference to the node map that stores the
   804     /// \brief Returns a const reference to the node map that stores the
   805     /// distances of the nodes.
   805     /// distances of the nodes.
   806     ///
   806     ///
   807     /// Returns a const reference to the node map that stores the distances
   807     /// Returns a const reference to the node map that stores the distances
   808     /// of the nodes calculated by the algorithm.
   808     /// of the nodes calculated by the algorithm.
   809     ///
   809     ///
   810     /// \pre Either \ref run() or \ref init() must be called before
   810     /// \pre Either \ref run() or \ref init() must be called before
   811     /// using this function.
   811     /// using this function.
   812     const DistMap &distMap() const { return *_dist;}
   812     const DistMap &distMap() const { return *_dist;}
   813  
   813 
   814     /// \brief Returns a const reference to the node map that stores the
   814     /// \brief Returns a const reference to the node map that stores the
   815     /// predecessor arcs.
   815     /// predecessor arcs.
   816     ///
   816     ///
   817     /// Returns a const reference to the node map that stores the predecessor
   817     /// Returns a const reference to the node map that stores the predecessor
   818     /// arcs, which form the shortest path tree (forest).
   818     /// arcs, which form the shortest path tree (forest).
   819     ///
   819     ///
   820     /// \pre Either \ref run() or \ref init() must be called before
   820     /// \pre Either \ref run() or \ref init() must be called before
   821     /// using this function.
   821     /// using this function.
   822     const PredMap &predMap() const { return *_pred; }
   822     const PredMap &predMap() const { return *_pred; }
   823  
   823 
   824     /// \brief Checks if a node is reached from the root(s).
   824     /// \brief Checks if a node is reached from the root(s).
   825     ///
   825     ///
   826     /// Returns \c true if \c v is reached from the root(s).
   826     /// Returns \c true if \c v is reached from the root(s).
   827     ///
   827     ///
   828     /// \pre Either \ref run() or \ref init() must be called before
   828     /// \pre Either \ref run() or \ref init() must be called before
   830     bool reached(Node v) const {
   830     bool reached(Node v) const {
   831       return (*_dist)[v] != OperationTraits::infinity();
   831       return (*_dist)[v] != OperationTraits::infinity();
   832     }
   832     }
   833 
   833 
   834     /// \brief Gives back a negative cycle.
   834     /// \brief Gives back a negative cycle.
   835     ///    
   835     ///
   836     /// This function gives back a directed cycle with negative total
   836     /// This function gives back a directed cycle with negative total
   837     /// length if the algorithm has already found one.
   837     /// length if the algorithm has already found one.
   838     /// Otherwise it gives back an empty path.
   838     /// Otherwise it gives back an empty path.
   839     lemon::Path<Digraph> negativeCycle() const {
   839     lemon::Path<Digraph> negativeCycle() const {
   840       typename Digraph::template NodeMap<int> state(*_gr, -1);
   840       typename Digraph::template NodeMap<int> state(*_gr, -1);
   857           state[v] = i;
   857           state[v] = i;
   858         }
   858         }
   859       }
   859       }
   860       return cycle;
   860       return cycle;
   861     }
   861     }
   862     
   862 
   863     ///@}
   863     ///@}
   864   };
   864   };
   865  
   865 
   866   /// \brief Default traits class of bellmanFord() function.
   866   /// \brief Default traits class of bellmanFord() function.
   867   ///
   867   ///
   868   /// Default traits class of bellmanFord() function.
   868   /// Default traits class of bellmanFord() function.
   869   /// \tparam GR The type of the digraph.
   869   /// \tparam GR The type of the digraph.
   870   /// \tparam LEN The type of the length map.
   870   /// \tparam LEN The type of the length map.
   871   template <typename GR, typename LEN>
   871   template <typename GR, typename LEN>
   872   struct BellmanFordWizardDefaultTraits {
   872   struct BellmanFordWizardDefaultTraits {
   873     /// The type of the digraph the algorithm runs on. 
   873     /// The type of the digraph the algorithm runs on.
   874     typedef GR Digraph;
   874     typedef GR Digraph;
   875 
   875 
   876     /// \brief The type of the map that stores the arc lengths.
   876     /// \brief The type of the map that stores the arc lengths.
   877     ///
   877     ///
   878     /// The type of the map that stores the arc lengths.
   878     /// The type of the map that stores the arc lengths.
   890     /// BellmanFordToleranceOperationTraits
   890     /// BellmanFordToleranceOperationTraits
   891     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   891     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
   892 
   892 
   893     /// \brief The type of the map that stores the last
   893     /// \brief The type of the map that stores the last
   894     /// arcs of the shortest paths.
   894     /// arcs of the shortest paths.
   895     /// 
   895     ///
   896     /// The type of the map that stores the last arcs of the shortest paths.
   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.
   897     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   898     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   898     typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
   899 
   899 
   900     /// \brief Instantiates a \c PredMap.
   900     /// \brief Instantiates a \c PredMap.
   901     /// 
   901     ///
   902     /// This function instantiates a \ref PredMap.
   902     /// This function instantiates a \ref PredMap.
   903     /// \param g is the digraph to which we would like to define the
   903     /// \param g is the digraph to which we would like to define the
   904     /// \ref PredMap.
   904     /// \ref PredMap.
   905     static PredMap *createPredMap(const GR &g) {
   905     static PredMap *createPredMap(const GR &g) {
   906       return new PredMap(g);
   906       return new PredMap(g);
   912     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   912     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   913     typedef typename GR::template NodeMap<Value> DistMap;
   913     typedef typename GR::template NodeMap<Value> DistMap;
   914 
   914 
   915     /// \brief Instantiates a \c DistMap.
   915     /// \brief Instantiates a \c DistMap.
   916     ///
   916     ///
   917     /// This function instantiates a \ref DistMap. 
   917     /// This function instantiates a \ref DistMap.
   918     /// \param g is the digraph to which we would like to define the
   918     /// \param g is the digraph to which we would like to define the
   919     /// \ref DistMap.
   919     /// \ref DistMap.
   920     static DistMap *createDistMap(const GR &g) {
   920     static DistMap *createDistMap(const GR &g) {
   921       return new DistMap(g);
   921       return new DistMap(g);
   922     }
   922     }
   925 
   925 
   926     ///The type of the shortest paths.
   926     ///The type of the shortest paths.
   927     ///It must meet the \ref concepts::Path "Path" concept.
   927     ///It must meet the \ref concepts::Path "Path" concept.
   928     typedef lemon::Path<Digraph> Path;
   928     typedef lemon::Path<Digraph> Path;
   929   };
   929   };
   930   
   930 
   931   /// \brief Default traits class used by BellmanFordWizard.
   931   /// \brief Default traits class used by BellmanFordWizard.
   932   ///
   932   ///
   933   /// Default traits class used by BellmanFordWizard.
   933   /// Default traits class used by BellmanFordWizard.
   934   /// \tparam GR The type of the digraph.
   934   /// \tparam GR The type of the digraph.
   935   /// \tparam LEN The type of the length map.
   935   /// \tparam LEN The type of the length map.
   936   template <typename GR, typename LEN>
   936   template <typename GR, typename LEN>
   937   class BellmanFordWizardBase 
   937   class BellmanFordWizardBase
   938     : public BellmanFordWizardDefaultTraits<GR, LEN> {
   938     : public BellmanFordWizardDefaultTraits<GR, LEN> {
   939 
   939 
   940     typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
   940     typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
   941   protected:
   941   protected:
   942     // Type of the nodes in the digraph.
   942     // Type of the nodes in the digraph.
   955     //Pointer to the distance of the target node.
   955     //Pointer to the distance of the target node.
   956     void *_di;
   956     void *_di;
   957 
   957 
   958     public:
   958     public:
   959     /// Constructor.
   959     /// Constructor.
   960     
   960 
   961     /// This constructor does not require parameters, it initiates
   961     /// This constructor does not require parameters, it initiates
   962     /// all of the attributes to default values \c 0.
   962     /// all of the attributes to default values \c 0.
   963     BellmanFordWizardBase() :
   963     BellmanFordWizardBase() :
   964       _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
   964       _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
   965 
   965 
   966     /// Constructor.
   966     /// Constructor.
   967     
   967 
   968     /// This constructor requires two parameters,
   968     /// This constructor requires two parameters,
   969     /// others are initiated to \c 0.
   969     /// others are initiated to \c 0.
   970     /// \param gr The digraph the algorithm runs on.
   970     /// \param gr The digraph the algorithm runs on.
   971     /// \param len The length map.
   971     /// \param len The length map.
   972     BellmanFordWizardBase(const GR& gr, 
   972     BellmanFordWizardBase(const GR& gr,
   973 			  const LEN& len) :
   973                           const LEN& len) :
   974       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
   974       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
   975       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
   975       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
   976       _pred(0), _dist(0), _path(0), _di(0) {}
   976       _pred(0), _dist(0), _path(0), _di(0) {}
   977 
   977 
   978   };
   978   };
   979   
   979 
   980   /// \brief Auxiliary class for the function-type interface of the
   980   /// \brief Auxiliary class for the function-type interface of the
   981   /// \ref BellmanFord "Bellman-Ford" algorithm.
   981   /// \ref BellmanFord "Bellman-Ford" algorithm.
   982   ///
   982   ///
   983   /// This auxiliary class is created to implement the
   983   /// This auxiliary class is created to implement the
   984   /// \ref bellmanFord() "function-type interface" of the
   984   /// \ref bellmanFord() "function-type interface" of the
   999 
   999 
  1000     typedef typename Digraph::Node Node;
  1000     typedef typename Digraph::Node Node;
  1001     typedef typename Digraph::NodeIt NodeIt;
  1001     typedef typename Digraph::NodeIt NodeIt;
  1002     typedef typename Digraph::Arc Arc;
  1002     typedef typename Digraph::Arc Arc;
  1003     typedef typename Digraph::OutArcIt ArcIt;
  1003     typedef typename Digraph::OutArcIt ArcIt;
  1004     
  1004 
  1005     typedef typename TR::LengthMap LengthMap;
  1005     typedef typename TR::LengthMap LengthMap;
  1006     typedef typename LengthMap::Value Value;
  1006     typedef typename LengthMap::Value Value;
  1007     typedef typename TR::PredMap PredMap;
  1007     typedef typename TR::PredMap PredMap;
  1008     typedef typename TR::DistMap DistMap;
  1008     typedef typename TR::DistMap DistMap;
  1009     typedef typename TR::Path Path;
  1009     typedef typename TR::Path Path;
  1016     ///
  1016     ///
  1017     /// Constructor that requires parameters.
  1017     /// Constructor that requires parameters.
  1018     /// These parameters will be the default values for the traits class.
  1018     /// These parameters will be the default values for the traits class.
  1019     /// \param gr The digraph the algorithm runs on.
  1019     /// \param gr The digraph the algorithm runs on.
  1020     /// \param len The length map.
  1020     /// \param len The length map.
  1021     BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
  1021     BellmanFordWizard(const Digraph& gr, const LengthMap& len)
  1022       : TR(gr, len) {}
  1022       : TR(gr, len) {}
  1023 
  1023 
  1024     /// \brief Copy constructor
  1024     /// \brief Copy constructor
  1025     BellmanFordWizard(const TR &b) : TR(b) {}
  1025     BellmanFordWizard(const TR &b) : TR(b) {}
  1026 
  1026 
  1027     ~BellmanFordWizard() {}
  1027     ~BellmanFordWizard() {}
  1028 
  1028 
  1029     /// \brief Runs the Bellman-Ford algorithm from the given source node.
  1029     /// \brief Runs the Bellman-Ford algorithm from the given source node.
  1030     ///    
  1030     ///
  1031     /// This method runs the Bellman-Ford algorithm from the given source
  1031     /// This method runs the Bellman-Ford algorithm from the given source
  1032     /// node in order to compute the shortest path to each node.
  1032     /// node in order to compute the shortest path to each node.
  1033     void run(Node s) {
  1033     void run(Node s) {
  1034       BellmanFord<Digraph,LengthMap,TR> 
  1034       BellmanFord<Digraph,LengthMap,TR>
  1035 	bf(*reinterpret_cast<const Digraph*>(Base::_graph), 
  1035         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
  1036            *reinterpret_cast<const LengthMap*>(Base::_length));
  1036            *reinterpret_cast<const LengthMap*>(Base::_length));
  1037       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1037       if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1038       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1038       if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1039       bf.run(s);
  1039       bf.run(s);
  1040     }
  1040     }
  1065     struct SetPredMapBase : public Base {
  1065     struct SetPredMapBase : public Base {
  1066       typedef T PredMap;
  1066       typedef T PredMap;
  1067       static PredMap *createPredMap(const Digraph &) { return 0; };
  1067       static PredMap *createPredMap(const Digraph &) { return 0; };
  1068       SetPredMapBase(const TR &b) : TR(b) {}
  1068       SetPredMapBase(const TR &b) : TR(b) {}
  1069     };
  1069     };
  1070     
  1070 
  1071     /// \brief \ref named-templ-param "Named parameter" for setting
  1071     /// \brief \ref named-templ-param "Named parameter" for setting
  1072     /// the predecessor map.
  1072     /// the predecessor map.
  1073     ///
  1073     ///
  1074     /// \ref named-templ-param "Named parameter" for setting
  1074     /// \ref named-templ-param "Named parameter" for setting
  1075     /// the map that stores the predecessor arcs of the nodes.
  1075     /// the map that stores the predecessor arcs of the nodes.
  1076     template<class T>
  1076     template<class T>
  1077     BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
  1077     BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
  1078       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1078       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1079       return BellmanFordWizard<SetPredMapBase<T> >(*this);
  1079       return BellmanFordWizard<SetPredMapBase<T> >(*this);
  1080     }
  1080     }
  1081     
  1081 
  1082     template<class T>
  1082     template<class T>
  1083     struct SetDistMapBase : public Base {
  1083     struct SetDistMapBase : public Base {
  1084       typedef T DistMap;
  1084       typedef T DistMap;
  1085       static DistMap *createDistMap(const Digraph &) { return 0; };
  1085       static DistMap *createDistMap(const Digraph &) { return 0; };
  1086       SetDistMapBase(const TR &b) : TR(b) {}
  1086       SetDistMapBase(const TR &b) : TR(b) {}
  1087     };
  1087     };
  1088     
  1088 
  1089     /// \brief \ref named-templ-param "Named parameter" for setting
  1089     /// \brief \ref named-templ-param "Named parameter" for setting
  1090     /// the distance map.
  1090     /// the distance map.
  1091     ///
  1091     ///
  1092     /// \ref named-templ-param "Named parameter" for setting
  1092     /// \ref named-templ-param "Named parameter" for setting
  1093     /// the map that stores the distances of the nodes calculated
  1093     /// the map that stores the distances of the nodes calculated
  1124     BellmanFordWizard dist(const Value &d)
  1124     BellmanFordWizard dist(const Value &d)
  1125     {
  1125     {
  1126       Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
  1126       Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
  1127       return *this;
  1127       return *this;
  1128     }
  1128     }
  1129     
  1129 
  1130   };
  1130   };
  1131   
  1131 
  1132   /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
  1132   /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
  1133   /// algorithm.
  1133   /// algorithm.
  1134   ///
  1134   ///
  1135   /// \ingroup shortest_path
  1135   /// \ingroup shortest_path
  1136   /// Function type interface for the \ref BellmanFord "Bellman-Ford"
  1136   /// Function type interface for the \ref BellmanFord "Bellman-Ford"
  1137   /// algorithm.
  1137   /// algorithm.
  1138   ///
  1138   ///
  1139   /// This function also has several \ref named-templ-func-param 
  1139   /// This function also has several \ref named-templ-func-param
  1140   /// "named parameters", they are declared as the members of class 
  1140   /// "named parameters", they are declared as the members of class
  1141   /// \ref BellmanFordWizard.
  1141   /// \ref BellmanFordWizard.
  1142   /// The following examples show how to use these parameters.
  1142   /// The following examples show how to use these parameters.
  1143   /// \code
  1143   /// \code
  1144   ///   // Compute shortest path from node s to each node
  1144   ///   // Compute shortest path from node s to each node
  1145   ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
  1145   ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
  1152   /// \sa BellmanFordWizard
  1152   /// \sa BellmanFordWizard
  1153   /// \sa BellmanFord
  1153   /// \sa BellmanFord
  1154   template<typename GR, typename LEN>
  1154   template<typename GR, typename LEN>
  1155   BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
  1155   BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
  1156   bellmanFord(const GR& digraph,
  1156   bellmanFord(const GR& digraph,
  1157 	      const LEN& length)
  1157               const LEN& length)
  1158   {
  1158   {
  1159     return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
  1159     return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
  1160   }
  1160   }
  1161 
  1161 
  1162 } //END OF NAMESPACE LEMON
  1162 } //END OF NAMESPACE LEMON