COIN-OR::LEMON - Graph Library

Changeset 697:9496ed797f20 in lemon-main


Ignore:
Timestamp:
08/02/09 13:24:46 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements and unifications for BellmanFord? (#51)

  • Rework the function type interface to fit to dijkstra().
  • Rename named template parameters (Def* -> Set*).
  • Rename some private member variables (to start with an underscore).
  • Simplify template parameter names.
  • Many unifications and improvements in the doc.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bellman_ford.h

    r696 r697  
    1717 */
    1818
    19 #ifndef LEMON_BELMANN_FORD_H
    20 #define LEMON_BELMANN_FORD_H
     19#ifndef LEMON_BELLMAN_FORD_H
     20#define LEMON_BELLMAN_FORD_H
    2121
    2222/// \ingroup shortest_path
    2323/// \file
    2424/// \brief Bellman-Ford algorithm.
    25 ///
    2625
    2726#include <lemon/bits/path_dump.h>
     
    2928#include <lemon/error.h>
    3029#include <lemon/maps.h>
     30#include <lemon/path.h>
    3131
    3232#include <limits>
     
    3636  /// \brief Default OperationTraits for the BellmanFord algorithm class.
    3737  /// 
    38   /// It defines all computational operations and constants which are
    39   /// used in the Bellman-Ford algorithm. The default implementation
    40   /// is based on the numeric_limits class. If the numeric type does not
    41   /// have infinity value then the maximum value is used as extremal
    42   /// infinity value.
     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.
    4343  template <
    44     typename Value,
    45     bool has_infinity = std::numeric_limits<Value>::has_infinity>
     44    typename V,
     45    bool has_inf = std::numeric_limits<V>::has_infinity>
    4646  struct BellmanFordDefaultOperationTraits {
     47    /// \e
     48    typedef V Value;
    4749    /// \brief Gives back the zero value of the type.
    4850    static Value zero() {
     
    5759      return left + right;
    5860    }
    59     /// \brief Gives back true only if the first value less than the second.
     61    /// \brief Gives back \c true only if the first value is less than
     62    /// the second.
    6063    static bool less(const Value& left, const Value& right) {
    6164      return left < right;
     
    6366  };
    6467
    65   template <typename Value>
    66   struct BellmanFordDefaultOperationTraits<Value, false> {
     68  template <typename V>
     69  struct BellmanFordDefaultOperationTraits<V, false> {
     70    typedef V Value;
    6771    static Value zero() {
    6872      return static_cast<Value>(0);
     
    8387  ///
    8488  /// Default traits class of BellmanFord class.
    85   /// \param _Digraph Digraph type.
    86   /// \param _LegthMap Type of length map.
    87   template<class _Digraph, class _LengthMap>
     89  /// \param GR The type of the digraph.
     90  /// \param LEN The type of the length map.
     91  template<typename GR, typename LEN>
    8892  struct BellmanFordDefaultTraits {
    89     /// The digraph type the algorithm runs on.
    90     typedef _Digraph Digraph;
     93    /// The type of the digraph the algorithm runs on.
     94    typedef GR Digraph;
    9195
    9296    /// \brief The type of the map that stores the arc lengths.
    9397    ///
    9498    /// The type of the map that stores the arc lengths.
    95     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    96     typedef _LengthMap LengthMap;
    97 
    98     // The type of the length of the arcs.
    99     typedef typename _LengthMap::Value Value;
     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;
    100104
    101105    /// \brief Operation traits for Bellman-Ford algorithm.
    102106    ///
    103     /// It defines the infinity type on the given Value type
    104     /// and the used operation.
     107    /// It defines the used operations and the infinity value for the
     108    /// given \c Value type.
    105109    /// \see BellmanFordDefaultOperationTraits
    106110    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
     
    111115    /// The type of the map that stores the last
    112116    /// arcs of the shortest paths.
    113     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    114     ///
    115     typedef typename Digraph::template NodeMap<typename _Digraph::Arc> PredMap;
    116 
    117     /// \brief Instantiates a PredMap.
     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.
    118121    ///
    119122    /// This function instantiates a \ref PredMap.
    120     /// \param digraph is the digraph, to which we would like to define the PredMap.
    121     static PredMap *createPredMap(const _Digraph& digraph) {
    122       return new PredMap(digraph);
    123     }
    124 
    125     /// \brief The type of the map that stores the dists of the nodes.
    126     ///
    127     /// The type of the map that stores the dists of the nodes.
    128     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    129     ///
    130     typedef typename Digraph::template NodeMap<typename _LengthMap::Value>
    131     DistMap;
    132 
    133     /// \brief Instantiates a DistMap.
     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.
    134136    ///
    135137    /// This function instantiates a \ref DistMap.
    136     /// \param digraph is the digraph, to which we would like to define the
    137     /// \ref DistMap
    138     static DistMap *createDistMap(const _Digraph& digraph) {
    139       return new DistMap(digraph);
     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);
    140142    }
    141143
     
    145147  ///
    146148  /// \ingroup shortest_path
    147   /// This class provides an efficient implementation of \c Bellman-Ford
    148   /// algorithm. The arc lengths are passed to the algorithm using a
     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
    149160  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
    150   /// kind of length.
    151   ///
    152   /// The Bellman-Ford algorithm solves the shortest path from one node
    153   /// problem when the arcs can have negative length but the digraph should
    154   /// not contain cycles with negative sum of length. If we can assume
    155   /// that all arc is non-negative in the digraph then the dijkstra algorithm
    156   /// should be used rather.
    157   ///
    158   /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
    159   ///
    160   /// The type of the length is determined by the
    161   /// \ref concepts::ReadMap::Value "Value" of the length map.
    162   ///
    163   /// \param _Digraph The digraph type the algorithm runs on. The default value
    164   /// is \ref ListDigraph. The value of _Digraph is not used directly by
    165   /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
    166   /// \param _LengthMap This read-only ArcMap determines the lengths of the
    167   /// arcs. The default map type is \ref concepts::Digraph::ArcMap
    168   /// "Digraph::ArcMap<int>".  The value of _LengthMap is not used directly
    169   /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. 
    170   /// \param _Traits Traits class to set various data types used by the
    171   /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
    172   /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>".  See \ref
    173   /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
    174   /// class.
     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>".
    175173#ifdef DOXYGEN
    176   template <typename _Digraph, typename _LengthMap, typename _Traits>
     174  template <typename GR, typename LEN, typename TR>
    177175#else
    178   template <typename _Digraph,
    179             typename _LengthMap=typename _Digraph::template ArcMap<int>,
    180             typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> >
     176  template <typename GR=ListDigraph,
     177            typename LEN=typename GR::template ArcMap<int>,
     178            typename TR=BellmanFordDefaultTraits<GR,LEN> >
    181179#endif
    182180  class BellmanFord {
    183181  public:
    184182
    185     typedef _Traits Traits;
    186183    ///The type of the underlying digraph.
    187     typedef typename _Traits::Digraph 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:
    188205
    189206    typedef typename Digraph::Node Node;
     
    191208    typedef typename Digraph::Arc Arc;
    192209    typedef typename Digraph::OutArcIt OutArcIt;
    193    
    194     /// \brief The type of the length of the arcs.
    195     typedef typename _Traits::LengthMap::Value Value;
    196     /// \brief The type of the map that stores the arc lengths.
    197     typedef typename _Traits::LengthMap LengthMap;
    198     /// \brief The type of the map that stores the last
    199     /// arcs of the shortest paths.
    200     typedef typename _Traits::PredMap PredMap;
    201     /// \brief The type of the map that stores the dists of the nodes.
    202     typedef typename _Traits::DistMap DistMap;
    203     /// \brief The operation traits.
    204     typedef typename _Traits::OperationTraits OperationTraits;
    205   private:
    206     /// Pointer to the underlying digraph.
    207     const Digraph *digraph;
    208     /// Pointer to the length map
    209     const LengthMap *length;
    210     ///Pointer to the map of predecessors arcs.
     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.
    211216    PredMap *_pred;
    212     ///Indicates if \ref _pred is locally allocated (\c true) or not.
    213     bool local_pred;
    214     ///Pointer to the map of distances.
     217    // Indicates if _pred is locally allocated (true) or not.
     218    bool _local_pred;
     219    // Pointer to the map of distances.
    215220    DistMap *_dist;
    216     ///Indicates if \ref _dist is locally allocated (\c true) or not.
    217     bool local_dist;
     221    // Indicates if _dist is locally allocated (true) or not.
     222    bool _local_dist;
    218223
    219224    typedef typename Digraph::template NodeMap<bool> MaskMap;
     
    222227    std::vector<Node> _process;
    223228
    224     /// Creates the maps if necessary.
     229    // Creates the maps if necessary.
    225230    void create_maps() {
    226231      if(!_pred) {
    227         local_pred = true;
    228         _pred = Traits::createPredMap(*digraph);
     232        _local_pred = true;
     233        _pred = Traits::createPredMap(*_gr);
    229234      }
    230235      if(!_dist) {
    231         local_dist = true;
    232         _dist = Traits::createDistMap(*digraph);
    233       }
    234       _mask = new MaskMap(*digraph, false);
     236        _local_dist = true;
     237        _dist = Traits::createDistMap(*_gr);
     238      }
     239      _mask = new MaskMap(*_gr, false);
    235240    }
    236241   
     
    239244    typedef BellmanFord Create;
    240245
    241     /// \name Named template parameters
     246    /// \name Named Template Parameters
    242247
    243248    ///@{
    244249
    245250    template <class T>
    246     struct DefPredMapTraits : public Traits {
     251    struct SetPredMapTraits : public Traits {
    247252      typedef T PredMap;
    248253      static PredMap *createPredMap(const Digraph&) {
     
    252257    };
    253258
    254     /// \brief \ref named-templ-param "Named parameter" for setting PredMap
    255     /// type
    256     /// \ref named-templ-param "Named parameter" for setting PredMap type
    257     ///
     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.
    258265    template <class T>
    259266    struct SetPredMap
    260       : public BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > {
    261       typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > Create;
     267      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
     268      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
    262269    };
    263270   
    264271    template <class T>
    265     struct DefDistMapTraits : public Traits {
     272    struct SetDistMapTraits : public Traits {
    266273      typedef T DistMap;
    267274      static DistMap *createDistMap(const Digraph&) {
     
    271278    };
    272279
    273     /// \brief \ref named-templ-param "Named parameter" for setting DistMap
    274     /// type
    275     ///
    276     /// \ref named-templ-param "Named parameter" for setting DistMap type
    277     ///
     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.
    278286    template <class T>
    279287    struct SetDistMap
    280       : public BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > {
    281       typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > Create;
     288      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
     289      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
    282290    };
    283    
     291
    284292    template <class T>
    285     struct DefOperationTraitsTraits : public Traits {
     293    struct SetOperationTraitsTraits : public Traits {
    286294      typedef T OperationTraits;
    287295    };
    288296   
    289297    /// \brief \ref named-templ-param "Named parameter" for setting
    290     /// OperationTraits type
    291     ///
    292     /// \ref named-templ-param "Named parameter" for setting OperationTraits
    293     /// type
     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.
    294303    template <class T>
    295304    struct SetOperationTraits
    296       : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> > {
    297       typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> >
     305      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
     306      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
    298307      Create;
    299308    };
     
    309318    /// \brief Constructor.
    310319    ///
    311     /// \param _graph the digraph the algorithm will run on.
    312     /// \param _length the length map used by the algorithm.
    313     BellmanFord(const Digraph& _graph, const LengthMap& _length) :
    314       digraph(&_graph), length(&_length),
    315       _pred(0), local_pred(false),
    316       _dist(0), local_dist(false), _mask(0) {}
     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) {}
    317327   
    318328    ///Destructor.
    319329    ~BellmanFord() {
    320       if(local_pred) delete _pred;
    321       if(local_dist) delete _dist;
     330      if(_local_pred) delete _pred;
     331      if(_local_dist) delete _dist;
    322332      if(_mask) delete _mask;
    323333    }
     
    326336    ///
    327337    /// Sets the length map.
    328     /// \return \c (*this)
    329     BellmanFord &lengthMap(const LengthMap &m) {
    330       length = &m;
     338    /// \return <tt>(*this)</tt>
     339    BellmanFord &lengthMap(const LengthMap &map) {
     340      _length = &map;
    331341      return *this;
    332342    }
    333343
    334     /// \brief Sets the map storing the predecessor arcs.
    335     ///
    336     /// Sets the map storing the predecessor arcs.
    337     /// If you don't use this function before calling \ref run(),
    338     /// it will allocate one. The destuctor deallocates this
    339     /// automatically allocated map, of course.
    340     /// \return \c (*this)
    341     BellmanFord &predMap(PredMap &m) {
    342       if(local_pred) {
     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) {
    343354        delete _pred;
    344         local_pred=false;
    345       }
    346       _pred = &m;
     355        _local_pred=false;
     356      }
     357      _pred = &map;
    347358      return *this;
    348359    }
    349360
    350     /// \brief Sets the map storing the distances calculated by the algorithm.
    351     ///
    352     /// Sets the map storing the distances calculated by the algorithm.
    353     /// If you don't use this function before calling \ref run(),
    354     /// it will allocate one. The destuctor deallocates this
    355     /// automatically allocated map, of course.
    356     /// \return \c (*this)
    357     BellmanFord &distMap(DistMap &m) {
    358       if(local_dist) {
     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) {
    359372        delete _dist;
    360         local_dist=false;
    361       }
    362       _dist = &m;
     373        _local_dist=false;
     374      }
     375      _dist = &map;
    363376      return *this;
    364377    }
    365378
    366     /// \name Execution control
    367     /// The simplest way to execute the algorithm is to use
    368     /// one of the member functions called \c run(...).
    369     /// \n
    370     /// If you need more control on the execution,
    371     /// first you must call \ref init(), then you can add several source nodes
    372     /// with \ref addSource().
    373     /// Finally \ref start() will perform the actual path
    374     /// computation.
     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().
    375387
    376388    ///@{
     
    378390    /// \brief Initializes the internal data structures.
    379391    ///
    380     /// Initializes the internal data structures.
     392    /// Initializes the internal data structures. The optional parameter
     393    /// is the initial distance of each node.
    381394    void init(const Value value = OperationTraits::infinity()) {
    382395      create_maps();
    383       for (NodeIt it(*digraph); it != INVALID; ++it) {
     396      for (NodeIt it(*_gr); it != INVALID; ++it) {
    384397        _pred->set(it, INVALID);
    385398        _dist->set(it, value);
     
    387400      _process.clear();
    388401      if (OperationTraits::less(value, OperationTraits::infinity())) {
    389         for (NodeIt it(*digraph); it != INVALID; ++it) {
     402        for (NodeIt it(*_gr); it != INVALID; ++it) {
    390403          _process.push_back(it);
    391404          _mask->set(it, true);
     
    396409    /// \brief Adds a new source node.
    397410    ///
    398     /// Adds a new source node. The optional second parameter is the
    399     /// initial distance of the node. It just sets the distance of the
    400     /// node to the given value.
     411    /// This function adds a new source node. The optional second parameter
     412    /// is the initial distance of the node.
    401413    void addSource(Node source, Value dst = OperationTraits::zero()) {
    402414      _dist->set(source, dst);
     
    410422    ///
    411423    /// If the algoritm calculated the distances in the previous round
    412     /// exactly for all at most \f$ k \f$ length path lengths then it will
    413     /// calculate the distances exactly for all at most \f$ k + 1 \f$
    414     /// length path lengths. With \f$ k \f$ iteration this function
    415     /// calculates the at most \f$ k \f$ length path lengths.
     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.
    416429    ///
    417430    /// \warning The paths with limited arc number cannot be retrieved
    418     /// easily with \ref path() or \ref predArc() functions. If you
    419     /// need the shortest path and not just the distance you should store
    420     /// after each iteration the \ref predMap() map and manually build
    421     /// the path.
     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.
    422435    ///
    423436    /// \return \c true when the algorithm have not found more shorter
    424437    /// paths.
     438    ///
     439    /// \see ActiveIt
    425440    bool processNextRound() {
    426441      for (int i = 0; i < int(_process.size()); ++i) {
     
    433448      }
    434449      for (int i = 0; i < int(_process.size()); ++i) {
    435         for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
    436           Node target = digraph->target(it);
    437           Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
     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]);
    438453          if (OperationTraits::less(relaxed, (*_dist)[target])) {
    439454            _pred->set(target, it);
     
    452467    /// \brief Executes one weak round from the Bellman-Ford algorithm.
    453468    ///
    454     /// If the algorithm calculated the distances in the
    455     /// previous round at least for all at most k length paths then it will
    456     /// calculate the distances at least for all at most k + 1 length paths.
    457     /// This function does not make it possible to calculate strictly the
    458     /// at most k length minimal paths, this is why it is
    459     /// called just weak round.
    460     /// \return \c true when the algorithm have not found more shorter paths.
     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
    461481    bool processNextWeakRound() {
    462482      for (int i = 0; i < int(_process.size()); ++i) {
     
    465485      std::vector<Node> nextProcess;
    466486      for (int i = 0; i < int(_process.size()); ++i) {
    467         for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
    468           Node target = digraph->target(it);
     487        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     488          Node target = _gr->target(it);
    469489          Value relaxed =
    470             OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
     490            OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
    471491          if (OperationTraits::less(relaxed, (*_dist)[target])) {
    472492            _pred->set(target, it);
     
    485505    /// \brief Executes the algorithm.
    486506    ///
    487     /// \pre init() must be called and at least one node should be added
    488     /// with addSource() before using this function.
    489     ///
    490     /// This method runs the %BellmanFord algorithm from the root node(s)
    491     /// in order to compute the shortest path to each node. The algorithm
    492     /// computes
    493     /// - The shortest path tree.
    494     /// - The distance of each node from the root(s).
     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.
    495518    void start() {
    496       int num = countNodes(*digraph) - 1;
     519      int num = countNodes(*_gr) - 1;
    497520      for (int i = 0; i < num; ++i) {
    498521        if (processNextWeakRound()) break;
     
    502525    /// \brief Executes the algorithm and checks the negative cycles.
    503526    ///
    504     /// \pre init() must be called and at least one node should be added
    505     /// with addSource() before using this function.
    506     ///
    507     /// This method runs the %BellmanFord algorithm from the root node(s)
    508     /// in order to compute the shortest path to each node. The algorithm
    509     /// computes
    510     /// - The shortest path tree.
    511     /// - The distance of each node from the root(s).
     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).
    512536    ///
    513537    /// \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.
    514541    bool checkedStart() {
    515       int num = countNodes(*digraph);
     542      int num = countNodes(*_gr);
    516543      for (int i = 0; i < num; ++i) {
    517544        if (processNextWeakRound()) return true;
     
    520547    }
    521548
    522     /// \brief Executes the algorithm with path length limit.
    523     ///
    524     /// \pre init() must be called and at least one node should be added
    525     /// with addSource() before using this function.
    526     ///
    527     /// This method runs the %BellmanFord algorithm from the root
    528     /// node(s) in order to compute the shortest path lengths with at
    529     /// most \c num arc.
     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.
    530560    ///
    531561    /// \warning The paths with limited arc number cannot be retrieved
    532     /// easily with \ref path() or \ref predArc() functions. If you
    533     /// need the shortest path and not just the distance you should store
    534     /// after each iteration the \ref predMap() map and manually build
    535     /// the path.
    536     ///
    537     /// The algorithm computes
    538     /// - The predecessor arc from each node.
    539     /// - The limited distance of each node from the root(s).
     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.
    540569    void limitedStart(int num) {
    541570      for (int i = 0; i < num; ++i) {
     
    544573    }
    545574   
    546     /// \brief Runs %BellmanFord algorithm from node \c s.
     575    /// \brief Runs the algorithm from the given root node.
    547576    ///   
    548     /// This method runs the %BellmanFord algorithm from a root node \c s
    549     /// in order to compute the shortest path to each node. The algorithm
    550     /// computes
    551     /// - The shortest path tree.
    552     /// - The distance of each node from the root.
    553     ///
    554     /// \note d.run(s) is just a shortcut of the following code.
    555     ///\code
    556     ///  d.init();
    557     ///  d.addSource(s);
    558     ///  d.start();
    559     ///\endcode
     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
    560590    void run(Node s) {
    561591      init();
     
    564594    }
    565595   
    566     /// \brief Runs %BellmanFord algorithm with limited path length
    567     /// from node \c s.
     596    /// \brief Runs the algorithm from the given root node with arc
     597    /// number limit.
    568598    ///   
    569     /// This method runs the %BellmanFord algorithm from a root node \c s
    570     /// in order to compute the shortest path with at most \c len arcs
    571     /// to each node. The algorithm computes
    572     /// - The shortest path tree.
    573     /// - The distance of each node from the root.
    574     ///
    575     /// \note d.run(s, num) is just a shortcut of the following code.
    576     ///\code
    577     ///  d.init();
    578     ///  d.addSource(s);
    579     ///  d.limitedStart(num);
    580     ///\endcode
     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
    581619    void run(Node s, int num) {
    582620      init();
     
    587625    ///@}
    588626
    589     /// \name Query Functions
    590     /// The result of the %BellmanFord algorithm can be obtained using these
    591     /// functions.\n
    592     /// Before the use of these functions,
    593     /// either run() or start() must be called.
    594    
    595     ///@{
    596 
    597     /// \brief Lemon iterator for get the active nodes.
    598     ///
    599     /// Lemon iterator for get the active nodes. This class provides a
    600     /// common style lemon iterator which gives back a subset of the
    601     /// nodes. The iterated nodes are active in the algorithm after
    602     /// the last phase so these should be checked in the next phase to
    603     /// find augmenting arcs from these.
     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.
    604633    class ActiveIt {
    605634    public:
     
    607636      /// \brief Constructor.
    608637      ///
    609       /// Constructor for get the nodeset of the variable.
     638      /// Constructor for getting the active nodes of the given BellmanFord
     639      /// instance.
    610640      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
    611641      {
     
    618648      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
    619649
    620       /// \brief Conversion to node.
     650      /// \brief Conversion to \c Node.
    621651      ///
    622       /// Conversion to node.
     652      /// Conversion to \c Node.
    623653      operator Node() const {
    624654        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
     
    647677      int _index;
    648678    };
    649 
    650     typedef PredMapPath<Digraph, PredMap> Path;
    651 
    652     /// \brief Gives back the shortest path.
     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.
    653688    ///   
    654     /// Gives back the shortest path.
    655     /// \pre The \c t should be reachable from the source.
    656     Path path(Node t)
     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
    657696    {
    658       return Path(*digraph, *_pred, t);
    659     }
    660 
    661 
    662     // TODO : implement negative cycle
    663 //     /// \brief Gives back a negative cycle.
    664 //     ///   
    665 //     /// This function gives back a negative cycle.
    666 //     /// If the algorithm have not found yet negative cycle it will give back
    667 //     /// an empty path.
    668 //     Path negativeCycle() {
    669 //       typename Digraph::template NodeMap<int> state(*digraph, 0);
    670 //       for (ActiveIt it(*this); it != INVALID; ++it) {
    671 //         if (state[it] == 0) {
    672 //           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
    673 //             if (state[t] == 0) {
    674 //               state[t] = 1;
    675 //             } else if (state[t] == 2) {
    676 //               break;
    677 //             } else {
    678 //               p.clear();
    679 //               typename Path::Builder b(p);
    680 //               b.setStartNode(t);
    681 //               b.pushFront(predArc(t));
    682 //               for(Node s = predNode(t); s != t; s = predNode(s)) {
    683 //                 b.pushFront(predArc(s));
    684 //               }
    685 //               b.commit();
    686 //               return true;
    687 //             }
    688 //           }
    689 //           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
    690 //             if (state[t] == 1) {
    691 //               state[t] = 2;
    692 //             } else {
    693 //               break;
    694 //             }
    695 //           }
    696 //         }
    697 //       }
    698 //       return false;
    699 //     }
     697      return Path(*_gr, *_pred, t);
     698    }
    700699         
    701     /// \brief The distance of a node from the root.
    702     ///
    703     /// Returns the distance of a node from the root.
    704     /// \pre \ref run() must be called before using this function.
    705     /// \warning If node \c v in unreachable from the root the return value
    706     /// of this funcion is undefined.
     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.
    707709    Value dist(Node v) const { return (*_dist)[v]; }
    708710
    709     /// \brief Returns the 'previous arc' of the shortest path tree.
    710     ///
    711     /// For a node \c v it returns the 'previous arc' of the shortest path
    712     /// tree, i.e. it returns the last arc of a shortest path from the root
    713     /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
    714     /// if \c v=s. The shortest path tree used here is equal to the shortest
    715     /// path tree used in \ref predNode().
    716     /// \pre \ref run() must be called before using
    717     /// this function.
     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.
    718724    Arc predArc(Node v) const { return (*_pred)[v]; }
    719725
    720     /// \brief Returns the 'previous node' of the shortest path tree.
    721     ///
    722     /// For a node \c v it returns the 'previous node' of the shortest path
    723     /// tree, i.e. it returns the last but one node from a shortest path from
    724     /// the root to \c /v. It is INVALID if \c v is unreachable from the root
    725     /// or if \c v=s. The shortest path tree used here is equal to the
    726     /// shortest path tree used in \ref predArc().  \pre \ref run() must be
    727     /// called before using this function.
     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.
    728739    Node predNode(Node v) const {
    729       return (*_pred)[v] == INVALID ? INVALID : digraph->source((*_pred)[v]);
    730     }
    731    
    732     /// \brief Returns a reference to the NodeMap of distances.
    733     ///
    734     /// Returns a reference to the NodeMap of distances. \pre \ref run() must
    735     /// be called before using this function.
     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.
    736751    const DistMap &distMap() const { return *_dist;}
    737752 
    738     /// \brief Returns a reference to the shortest path tree map.
    739     ///
    740     /// Returns a reference to the NodeMap of the arcs of the
    741     /// shortest path tree.
    742     /// \pre \ref run() must be called before using this function.
     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.
    743761    const PredMap &predMap() const { return *_pred; }
    744762 
    745     /// \brief Checks if a node is reachable from the root.
    746     ///
    747     /// Returns \c true if \c v is reachable from the root.
    748     /// \pre \ref run() must be called before using this function.
    749     ///
    750     bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
     763    /// \brief Checks if a node is reached from the root(s).
     764    ///
     765    /// Returns \c true if \c v is reached from the root(s).
     766    ///
     767    /// \pre Either \ref run() or \ref init() must be called before
     768    /// using this function.
     769    bool reached(Node v) const {
     770      return (*_dist)[v] != OperationTraits::infinity();
     771    }
     772
     773    // TODO: implement negative cycle
     774//    /// \brief Gives back a negative cycle.
     775//    ///   
     776//    /// This function gives back a negative cycle.
     777//    /// If the algorithm have not found yet negative cycle it will give back
     778//    /// an empty path.
     779//    Path negativeCycle() {
     780//      typename Digraph::template NodeMap<int> state(*digraph, 0);
     781//      for (ActiveIt it(*this); it != INVALID; ++it) {
     782//        if (state[it] == 0) {
     783//          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
     784//            if (state[t] == 0) {
     785//              state[t] = 1;
     786//            } else if (state[t] == 2) {
     787//              break;
     788//            } else {
     789//              p.clear();
     790//              typename Path::Builder b(p);
     791//              b.setStartNode(t);
     792//              b.pushFront(predArc(t));
     793//              for(Node s = predNode(t); s != t; s = predNode(s)) {
     794//                b.pushFront(predArc(s));
     795//              }
     796//              b.commit();
     797//              return true;
     798//            }
     799//          }
     800//          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
     801//            if (state[t] == 1) {
     802//              state[t] = 2;
     803//            } else {
     804//              break;
     805//            }
     806//          }
     807//        }
     808//      }
     809//      return false;
     810//    }
    751811   
    752812    ///@}
    753813  };
    754814 
    755   /// \brief Default traits class of BellmanFord function.
    756   ///
    757   /// Default traits class of BellmanFord function.
    758   /// \param _Digraph Digraph type.
    759   /// \param _LengthMap Type of length map.
    760   template <typename _Digraph, typename _LengthMap>
     815  /// \brief Default traits class of bellmanFord() function.
     816  ///
     817  /// Default traits class of bellmanFord() function.
     818  /// \tparam GR The type of the digraph.
     819  /// \tparam LEN The type of the length map.
     820  template <typename GR, typename LEN>
    761821  struct BellmanFordWizardDefaultTraits {
    762     /// \brief The digraph type the algorithm runs on.
    763     typedef _Digraph Digraph;
     822    /// The type of the digraph the algorithm runs on.
     823    typedef GR Digraph;
    764824
    765825    /// \brief The type of the map that stores the arc lengths.
     
    767827    /// The type of the map that stores the arc lengths.
    768828    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    769     typedef _LengthMap LengthMap;
    770 
    771     /// \brief The value type of the length map.
    772     typedef typename _LengthMap::Value Value;
     829    typedef LEN LengthMap;
     830
     831    /// The type of the arc lengths.
     832    typedef typename LEN::Value Value;
    773833
    774834    /// \brief Operation traits for Bellman-Ford algorithm.
    775835    ///
    776     /// It defines the infinity type on the given Value type
    777     /// and the used operation.
     836    /// It defines the used operations and the infinity value for the
     837    /// given \c Value type.
    778838    /// \see BellmanFordDefaultOperationTraits
    779839    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
     
    782842    /// arcs of the shortest paths.
    783843    ///
    784     /// The type of the map that stores the last
    785     /// arcs of the shortest paths.
    786     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    787     typedef NullMap <typename _Digraph::Node,typename _Digraph::Arc> PredMap;
    788 
    789     /// \brief Instantiates a PredMap.
     844    /// The type of the map that stores the last arcs of the shortest paths.
     845    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     846    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
     847
     848    /// \brief Instantiates a \c PredMap.
    790849    ///
    791     /// This function instantiates a \ref PredMap.
    792     static PredMap *createPredMap(const _Digraph &) {
    793       return new PredMap();
    794     }
    795     /// \brief The type of the map that stores the dists of the nodes.
    796     ///
    797     /// The type of the map that stores the dists of the nodes.
    798     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    799     typedef NullMap<typename Digraph::Node, Value> DistMap;
    800     /// \brief Instantiates a DistMap.
     850    /// This function instantiates a \ref PredMap.
     851    /// \param g is the digraph to which we would like to define the
     852    /// \ref PredMap.
     853    static PredMap *createPredMap(const GR &g) {
     854      return new PredMap(g);
     855    }
     856
     857    /// \brief The type of the map that stores the distances of the nodes.
     858    ///
     859    /// The type of the map that stores the distances of the nodes.
     860    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     861    typedef typename GR::template NodeMap<Value> DistMap;
     862
     863    /// \brief Instantiates a \c DistMap.
    801864    ///
    802865    /// This function instantiates a \ref DistMap.
    803     static DistMap *createDistMap(const _Digraph &) {
    804       return new DistMap();
    805     }
     866    /// \param g is the digraph to which we would like to define the
     867    /// \ref DistMap.
     868    static DistMap *createDistMap(const GR &g) {
     869      return new DistMap(g);
     870    }
     871
     872    ///The type of the shortest paths.
     873
     874    ///The type of the shortest paths.
     875    ///It must meet the \ref concepts::Path "Path" concept.
     876    typedef lemon::Path<Digraph> Path;
    806877  };
    807878 
    808   /// \brief Default traits used by \ref BellmanFordWizard
    809   ///
    810   /// To make it easier to use BellmanFord algorithm
    811   /// we have created a wizard class.
    812   /// This \ref BellmanFordWizard class needs default traits,
    813   /// as well as the \ref BellmanFord class.
    814   /// The \ref BellmanFordWizardBase is a class to be the default traits of the
    815   /// \ref BellmanFordWizard class.
    816   /// \todo More named parameters are required...
    817   template<class _Digraph,class _LengthMap>
     879  /// \brief Default traits class used by BellmanFordWizard.
     880  ///
     881  /// Default traits class used by BellmanFordWizard.
     882  /// \tparam GR The type of the digraph.
     883  /// \tparam LEN The type of the length map.
     884  template <typename GR, typename LEN>
    818885  class BellmanFordWizardBase
    819     : public BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> {
    820 
    821     typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base;
     886    : public BellmanFordWizardDefaultTraits<GR, LEN> {
     887
     888    typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
    822889  protected:
    823     /// Type of the nodes in the digraph.
     890    // Type of the nodes in the digraph.
    824891    typedef typename Base::Digraph::Node Node;
    825892
    826     /// Pointer to the underlying digraph.
     893    // Pointer to the underlying digraph.
    827894    void *_graph;
    828     /// Pointer to the length map
     895    // Pointer to the length map
    829896    void *_length;
    830     ///Pointer to the map of predecessors arcs.
     897    // Pointer to the map of predecessors arcs.
    831898    void *_pred;
    832     ///Pointer to the map of distances.
     899    // Pointer to the map of distances.
    833900    void *_dist;
    834     ///Pointer to the source node.
    835     Node _source;
     901    //Pointer to the shortest path to the target node.
     902    void *_path;
     903    //Pointer to the distance of the target node.
     904    void *_di;
    836905
    837906    public:
    838907    /// Constructor.
    839908   
    840     /// This constructor does not require parameters, therefore it initiates
    841     /// all of the attributes to default values (0, INVALID).
    842     BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
    843                            _dist(0), _source(INVALID) {}
     909    /// This constructor does not require parameters, it initiates
     910    /// all of the attributes to default values \c 0.
     911    BellmanFordWizardBase() :
     912      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
    844913
    845914    /// Constructor.
    846915   
    847     /// This constructor requires some parameters,
    848     /// listed in the parameters list.
    849     /// Others are initiated to 0.
    850     /// \param digraph is the initial value of  \ref _graph
    851     /// \param length is the initial value of  \ref _length
    852     /// \param source is the initial value of  \ref _source
    853     BellmanFordWizardBase(const _Digraph& digraph,
    854                           const _LengthMap& length,
    855                           Node source = INVALID) :
    856       _graph(reinterpret_cast<void*>(const_cast<_Digraph*>(&digraph))),
    857       _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))),
    858       _pred(0), _dist(0), _source(source) {}
     916    /// This constructor requires two parameters,
     917    /// others are initiated to \c 0.
     918    /// \param gr The digraph the algorithm runs on.
     919    /// \param len The length map.
     920    BellmanFordWizardBase(const GR& gr,
     921                          const LEN& len) :
     922      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
     923      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
     924      _pred(0), _dist(0), _path(0), _di(0) {}
    859925
    860926  };
    861927 
    862   /// A class to make the usage of BellmanFord algorithm easier
    863 
    864   /// This class is created to make it easier to use BellmanFord algorithm.
    865   /// It uses the functions and features of the plain \ref BellmanFord,
    866   /// but it is much simpler to use it.
    867   ///
    868   /// Simplicity means that the way to change the types defined
    869   /// in the traits class is based on functions that returns the new class
    870   /// and not on templatable built-in classes.
    871   /// When using the plain \ref BellmanFord
    872   /// the new class with the modified type comes from
    873   /// the original class by using the ::
    874   /// operator. In the case of \ref BellmanFordWizard only
    875   /// a function have to be called and it will
    876   /// return the needed class.
    877   ///
    878   /// It does not have own \ref run method. When its \ref run method is called
    879   /// it initiates a plain \ref BellmanFord class, and calls the \ref
    880   /// BellmanFord::run method of it.
    881   template<class _Traits>
    882   class BellmanFordWizard : public _Traits {
    883     typedef _Traits Base;
    884 
    885     ///The type of the underlying digraph.
    886     typedef typename _Traits::Digraph Digraph;
     928  /// \brief Auxiliary class for the function-type interface of the
     929  /// \ref BellmanFord "Bellman-Ford" algorithm.
     930  ///
     931  /// This auxiliary class is created to implement the
     932  /// \ref bellmanFord() "function-type interface" of the
     933  /// \ref BellmanFord "Bellman-Ford" algorithm.
     934  /// It does not have own \ref run() method, it uses the
     935  /// functions and features of the plain \ref BellmanFord.
     936  ///
     937  /// This class should only be used through the \ref bellmanFord()
     938  /// function, which makes it easier to use the algorithm.
     939  template<class TR>
     940  class BellmanFordWizard : public TR {
     941    typedef TR Base;
     942
     943    typedef typename TR::Digraph Digraph;
    887944
    888945    typedef typename Digraph::Node Node;
     
    891948    typedef typename Digraph::OutArcIt ArcIt;
    892949   
    893     ///The type of the map that stores the arc lengths.
    894     typedef typename _Traits::LengthMap LengthMap;
    895 
    896     ///The type of the length of the arcs.
     950    typedef typename TR::LengthMap LengthMap;
    897951    typedef typename LengthMap::Value Value;
    898 
    899     ///\brief The type of the map that stores the last
    900     ///arcs of the shortest paths.
    901     typedef typename _Traits::PredMap PredMap;
    902 
    903     ///The type of the map that stores the dists of the nodes.
    904     typedef typename _Traits::DistMap DistMap;
     952    typedef typename TR::PredMap PredMap;
     953    typedef typename TR::DistMap DistMap;
     954    typedef typename TR::Path Path;
    905955
    906956  public:
    907957    /// Constructor.
    908     BellmanFordWizard() : _Traits() {}
     958    BellmanFordWizard() : TR() {}
    909959
    910960    /// \brief Constructor that requires parameters.
     
    912962    /// Constructor that requires parameters.
    913963    /// These parameters will be the default values for the traits class.
    914     BellmanFordWizard(const Digraph& digraph, const LengthMap& length,
    915                       Node src = INVALID)
    916       : _Traits(digraph, length, src) {}
     964    /// \param gr The digraph the algorithm runs on.
     965    /// \param len The length map.
     966    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
     967      : TR(gr, len) {}
    917968
    918969    /// \brief Copy constructor
    919     BellmanFordWizard(const _Traits &b) : _Traits(b) {}
     970    BellmanFordWizard(const TR &b) : TR(b) {}
    920971
    921972    ~BellmanFordWizard() {}
    922973
    923     /// \brief Runs BellmanFord algorithm from a given node.
     974    /// \brief Runs the Bellman-Ford algorithm from the given source node.
    924975    ///   
    925     /// Runs BellmanFord algorithm from a given node.
    926     /// The node can be given by the \ref source function.
    927     void run() {
    928       LEMON_ASSERT(Base::_source != INVALID, "Source node is not given");
    929       BellmanFord<Digraph,LengthMap,_Traits>
     976    /// This method runs the Bellman-Ford algorithm from the given source
     977    /// node in order to compute the shortest path to each node.
     978    void run(Node s) {
     979      BellmanFord<Digraph,LengthMap,TR>
    930980        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
    931981           *reinterpret_cast<const LengthMap*>(Base::_length));
    932982      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    933983      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    934       bf.run(Base::_source);
    935     }
    936 
    937     /// \brief Runs BellmanFord algorithm from the given node.
    938     ///
    939     /// Runs BellmanFord algorithm from the given node.
    940     /// \param src is the given source.
    941     void run(Node src) {
    942       Base::_source = src;
    943       run();
     984      bf.run(s);
     985    }
     986
     987    /// \brief Runs the Bellman-Ford algorithm to find the shortest path
     988    /// between \c s and \c t.
     989    ///
     990    /// This method runs the Bellman-Ford algorithm from node \c s
     991    /// in order to compute the shortest path to node \c t.
     992    /// Actually, it computes the shortest path to each node, but using
     993    /// this function you can retrieve the distance and the shortest path
     994    /// for a single target node easier.
     995    ///
     996    /// \return \c true if \c t is reachable form \c s.
     997    bool run(Node s, Node t) {
     998      BellmanFord<Digraph,LengthMap,TR>
     999        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
     1000           *reinterpret_cast<const LengthMap*>(Base::_length));
     1001      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1002      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1003      bf.run(s);
     1004      if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
     1005      if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
     1006      return bf.reached(t);
    9441007    }
    9451008
    9461009    template<class T>
    947     struct DefPredMapBase : public Base {
     1010    struct SetPredMapBase : public Base {
    9481011      typedef T PredMap;
    9491012      static PredMap *createPredMap(const Digraph &) { return 0; };
    950       DefPredMapBase(const _Traits &b) : _Traits(b) {}
     1013      SetPredMapBase(const TR &b) : TR(b) {}
    9511014    };
    9521015   
    953     ///\brief \ref named-templ-param "Named parameter"
    954     ///function for setting PredMap type
    955     ///
    956     /// \ref named-templ-param "Named parameter"
    957     ///function for setting PredMap type
    958     ///
     1016    /// \brief \ref named-templ-param "Named parameter" for setting
     1017    /// the predecessor map.
     1018    ///
     1019    /// \ref named-templ-param "Named parameter" for setting
     1020    /// the map that stores the predecessor arcs of the nodes.
    9591021    template<class T>
    960     BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
    961     {
     1022    BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
    9621023      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    963       return BellmanFordWizard<DefPredMapBase<T> >(*this);
     1024      return BellmanFordWizard<SetPredMapBase<T> >(*this);
    9641025    }
    9651026   
    9661027    template<class T>
    967     struct DefDistMapBase : public Base {
     1028    struct SetDistMapBase : public Base {
    9681029      typedef T DistMap;
    9691030      static DistMap *createDistMap(const Digraph &) { return 0; };
    970       DefDistMapBase(const _Traits &b) : _Traits(b) {}
     1031      SetDistMapBase(const TR &b) : TR(b) {}
    9711032    };
    9721033   
    973     ///\brief \ref named-templ-param "Named parameter"
    974     ///function for setting DistMap type
    975     ///
    976     /// \ref named-templ-param "Named parameter"
    977     ///function for setting DistMap type
    978     ///
     1034    /// \brief \ref named-templ-param "Named parameter" for setting
     1035    /// the distance map.
     1036    ///
     1037    /// \ref named-templ-param "Named parameter" for setting
     1038    /// the map that stores the distances of the nodes calculated
     1039    /// by the algorithm.
    9791040    template<class T>
    980     BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
     1041    BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
    9811042      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    982       return BellmanFordWizard<DefDistMapBase<T> >(*this);
     1043      return BellmanFordWizard<SetDistMapBase<T> >(*this);
    9831044    }
    9841045
    9851046    template<class T>
    986     struct DefOperationTraitsBase : public Base {
    987       typedef T OperationTraits;
    988       DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
     1047    struct SetPathBase : public Base {
     1048      typedef T Path;
     1049      SetPathBase(const TR &b) : TR(b) {}
    9891050    };
    990    
    991     ///\brief \ref named-templ-param "Named parameter"
    992     ///function for setting OperationTraits type
    993     ///
    994     /// \ref named-templ-param "Named parameter"
    995     ///function for setting OperationTraits type
    996     ///
     1051
     1052    /// \brief \ref named-func-param "Named parameter" for getting
     1053    /// the shortest path to the target node.
     1054    ///
     1055    /// \ref named-func-param "Named parameter" for getting
     1056    /// the shortest path to the target node.
    9971057    template<class T>
    998     BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
    999       return BellmanFordWizard<DefDistMapBase<T> >(*this);
    1000     }
    1001    
    1002     /// \brief Sets the source node, from which the BellmanFord algorithm runs.
    1003     ///
    1004     /// Sets the source node, from which the BellmanFord algorithm runs.
    1005     /// \param src is the source node.
    1006     BellmanFordWizard<_Traits>& source(Node src) {
    1007       Base::_source = src;
     1058    BellmanFordWizard<SetPathBase<T> > path(const T &t)
     1059    {
     1060      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1061      return BellmanFordWizard<SetPathBase<T> >(*this);
     1062    }
     1063
     1064    /// \brief \ref named-func-param "Named parameter" for getting
     1065    /// the distance of the target node.
     1066    ///
     1067    /// \ref named-func-param "Named parameter" for getting
     1068    /// the distance of the target node.
     1069    BellmanFordWizard dist(const Value &d)
     1070    {
     1071      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
    10081072      return *this;
    10091073    }
     
    10111075  };
    10121076 
    1013   /// \brief Function type interface for BellmanFord algorithm.
     1077  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
     1078  /// algorithm.
    10141079  ///
    10151080  /// \ingroup shortest_path
    1016   /// Function type interface for BellmanFord algorithm.
     1081  /// Function type interface for the \ref BellmanFord "Bellman-Ford"
     1082  /// algorithm.
    10171083  ///
    10181084  /// This function also has several \ref named-templ-func-param
    10191085  /// "named parameters", they are declared as the members of class
    10201086  /// \ref BellmanFordWizard.
    1021   /// The following
    1022   /// example shows how to use these parameters.
    1023   ///\code
    1024   /// bellmanford(g,length,source).predMap(preds).run();
    1025   ///\endcode
     1087  /// The following examples show how to use these parameters.
     1088  /// \code
     1089  ///   // Compute shortest path from node s to each node
     1090  ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
     1091  ///
     1092  ///   // Compute shortest path from s to t
     1093  ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
     1094  /// \endcode
    10261095  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
    10271096  /// to the end of the parameter list.
    10281097  /// \sa BellmanFordWizard
    10291098  /// \sa BellmanFord
    1030   template<class _Digraph, class _LengthMap>
    1031   BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
    1032   bellmanFord(const _Digraph& digraph,
    1033               const _LengthMap& length,
    1034               typename _Digraph::Node source = INVALID) {
    1035     return BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
    1036       (digraph, length, source);
     1099  template<typename GR, typename LEN>
     1100  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
     1101  bellmanFord(const GR& digraph,
     1102              const LEN& length)
     1103  {
     1104    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
    10371105  }
    10381106
Note: See TracChangeset for help on using the changeset viewer.