lemon/belmann_ford.h
author deba
Fri, 04 Nov 2005 16:10:23 +0000
changeset 1769 a67ec111236c
parent 1763 49045f2d28d4
child 1781 dca4c8a54e0a
permissions -rw-r--r--
Removed todo
Moved to topology module
     1 /* -*- C++ -*-
     2  * lemon/belmann_ford.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_BELMANN_FORD_H
    18 #define LEMON_BELMANN_FORD_H
    19 
    20 ///\ingroup flowalgs
    21 /// \file
    22 /// \brief BelmannFord algorithm.
    23 ///
    24 
    25 #include <lemon/list_graph.h>
    26 #include <lemon/invalid.h>
    27 #include <lemon/error.h>
    28 #include <lemon/maps.h>
    29 
    30 #include <limits>
    31 
    32 namespace lemon {
    33 
    34   /// \brief Default OperationTraits for the BelmannFord algorithm class.
    35   ///  
    36   /// It defines all computational operations and constants which are
    37   /// used in the belmann ford algorithm. The default implementation
    38   /// is based on the numeric_limits class. If the numeric type does not
    39   /// have infinity value then the maximum value is used as extremal
    40   /// infinity value.
    41   template <
    42     typename Value, 
    43     bool has_infinity = std::numeric_limits<Value>::has_infinity>
    44   struct BelmannFordDefaultOperationTraits {
    45     /// \brief Gives back the zero value of the type.
    46     static Value zero() {
    47       return static_cast<Value>(0);
    48     }
    49     /// \brief Gives back the positive infinity value of the type.
    50     static Value infinity() {
    51       return std::numeric_limits<Value>::infinity();
    52     }
    53     /// \brief Gives back the sum of the given two elements.
    54     static Value plus(const Value& left, const Value& right) {
    55       return left + right;
    56     }
    57     /// \brief Gives back true only if the first value less than the second.
    58     static bool less(const Value& left, const Value& right) {
    59       return left < right;
    60     }
    61   };
    62 
    63   template <typename Value>
    64   struct BelmannFordDefaultOperationTraits<Value, false> {
    65     static Value zero() {
    66       return static_cast<Value>(0);
    67     }
    68     static Value infinity() {
    69       return std::numeric_limits<Value>::max();
    70     }
    71     static Value plus(const Value& left, const Value& right) {
    72       if (left == infinity() || right == infinity()) return infinity();
    73       return left + right;
    74     }
    75     static bool less(const Value& left, const Value& right) {
    76       return left < right;
    77     }
    78   };
    79   
    80   /// \brief Default traits class of BelmannFord class.
    81   ///
    82   /// Default traits class of BelmannFord class.
    83   /// \param _Graph Graph type.
    84   /// \param _LegthMap Type of length map.
    85   template<class _Graph, class _LengthMap>
    86   struct BelmannFordDefaultTraits {
    87     /// The graph type the algorithm runs on. 
    88     typedef _Graph Graph;
    89 
    90     /// \brief The type of the map that stores the edge lengths.
    91     ///
    92     /// The type of the map that stores the edge lengths.
    93     /// It must meet the \ref concept::ReadMap "ReadMap" concept.
    94     typedef _LengthMap LengthMap;
    95 
    96     // The type of the length of the edges.
    97     typedef typename _LengthMap::Value Value;
    98 
    99     /// \brief Operation traits for belmann-ford algorithm.
   100     ///
   101     /// It defines the infinity type on the given Value type
   102     /// and the used operation.
   103     /// \see BelmannFordDefaultOperationTraits
   104     typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
   105  
   106     /// \brief The type of the map that stores the last edges of the 
   107     /// shortest paths.
   108     /// 
   109     /// The type of the map that stores the last
   110     /// edges of the shortest paths.
   111     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   112     ///
   113     typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
   114 
   115     /// \brief Instantiates a PredMap.
   116     /// 
   117     /// This function instantiates a \ref PredMap. 
   118     /// \param G is the graph, to which we would like to define the PredMap.
   119     /// \todo The graph alone may be insufficient for the initialization
   120     static PredMap *createPredMap(const _Graph& graph) {
   121       return new PredMap(graph);
   122     }
   123 
   124     /// \brief The type of the map that stores the dists of the nodes.
   125     ///
   126     /// The type of the map that stores the dists of the nodes.
   127     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   128     ///
   129     typedef typename Graph::template NodeMap<typename _LengthMap::Value> 
   130     DistMap;
   131 
   132     /// \brief Instantiates a DistMap.
   133     ///
   134     /// This function instantiates a \ref DistMap. 
   135     /// \param G is the graph, to which we would like to define the 
   136     /// \ref DistMap
   137     static DistMap *createDistMap(const _Graph& graph) {
   138       return new DistMap(graph);
   139     }
   140 
   141   };
   142   
   143   /// \brief %BelmannFord algorithm class.
   144   ///
   145   /// \ingroup flowalgs
   146   /// This class provides an efficient implementation of \c Belmann-Ford 
   147   /// algorithm. The edge lengths are passed to the algorithm using a
   148   /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
   149   /// kind of length.
   150   ///
   151   /// The Belmann-Ford algorithm solves the shortest path from one node
   152   /// problem when the edges can have negative length but the graph should
   153   /// not contain cycles with negative sum of length. If we can assume
   154   /// that all edge is non-negative in the graph then the dijkstra algorithm
   155   /// should be used rather.
   156   ///
   157   /// The complexity of the algorithm is O(n * e).
   158   ///
   159   /// The type of the length is determined by the
   160   /// \ref concept::ReadMap::Value "Value" of the length map.
   161   ///
   162   /// \param _Graph The graph type the algorithm runs on. The default value
   163   /// is \ref ListGraph. The value of _Graph is not used directly by
   164   /// BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.
   165   /// \param _LengthMap This read-only EdgeMap determines the lengths of the
   166   /// edges. The default map type is \ref concept::StaticGraph::EdgeMap 
   167   /// "Graph::EdgeMap<int>".  The value of _LengthMap is not used directly 
   168   /// by BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.  
   169   /// \param _Traits Traits class to set various data types used by the 
   170   /// algorithm.  The default traits class is \ref BelmannFordDefaultTraits
   171   /// "BelmannFordDefaultTraits<_Graph,_LengthMap>".  See \ref
   172   /// BelmannFordDefaultTraits for the documentation of a BelmannFord traits
   173   /// class.
   174   ///
   175   /// \author Balazs Dezso
   176 
   177 #ifdef DOXYGEN
   178   template <typename _Graph, typename _LengthMap, typename _Traits>
   179 #else
   180   template <typename _Graph=ListGraph,
   181 	    typename _LengthMap=typename _Graph::template EdgeMap<int>,
   182 	    typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> >
   183 #endif
   184   class BelmannFord {
   185   public:
   186     
   187     /// \brief \ref Exception for uninitialized parameters.
   188     ///
   189     /// This error represents problems in the initialization
   190     /// of the parameters of the algorithms.
   191 
   192     class UninitializedParameter : public lemon::UninitializedParameter {
   193     public:
   194       virtual const char* exceptionName() const {
   195 	return "lemon::BelmannFord::UninitializedParameter";
   196       }
   197     };
   198 
   199     typedef _Traits Traits;
   200     ///The type of the underlying graph.
   201     typedef typename _Traits::Graph Graph;
   202 
   203     typedef typename Graph::Node Node;
   204     typedef typename Graph::NodeIt NodeIt;
   205     typedef typename Graph::Edge Edge;
   206     typedef typename Graph::EdgeIt EdgeIt;
   207     
   208     /// \brief The type of the length of the edges.
   209     typedef typename _Traits::LengthMap::Value Value;
   210     /// \brief The type of the map that stores the edge lengths.
   211     typedef typename _Traits::LengthMap LengthMap;
   212     /// \brief The type of the map that stores the last
   213     /// edges of the shortest paths.
   214     typedef typename _Traits::PredMap PredMap;
   215     /// \brief The type of the map that stores the dists of the nodes.
   216     typedef typename _Traits::DistMap DistMap;
   217     /// \brief The operation traits.
   218     typedef typename _Traits::OperationTraits OperationTraits;
   219   private:
   220     /// Pointer to the underlying graph.
   221     const Graph *graph;
   222     /// Pointer to the length map
   223     const LengthMap *length;
   224     ///Pointer to the map of predecessors edges.
   225     PredMap *_pred;
   226     ///Indicates if \ref _pred is locally allocated (\c true) or not.
   227     bool local_pred;
   228     ///Pointer to the map of distances.
   229     DistMap *_dist;
   230     ///Indicates if \ref _dist is locally allocated (\c true) or not.
   231     bool local_dist;
   232 
   233     /// Creates the maps if necessary.
   234     void create_maps() {
   235       if(!_pred) {
   236 	local_pred = true;
   237 	_pred = Traits::createPredMap(*graph);
   238       }
   239       if(!_dist) {
   240 	local_dist = true;
   241 	_dist = Traits::createDistMap(*graph);
   242       }
   243     }
   244     
   245   public :
   246  
   247     typedef BelmannFord Create;
   248 
   249     /// \name Named template parameters
   250 
   251     ///@{
   252 
   253     template <class T>
   254     struct DefPredMapTraits : public Traits {
   255       typedef T PredMap;
   256       static PredMap *createPredMap(const Graph&) {
   257 	throw UninitializedParameter();
   258       }
   259     };
   260 
   261     /// \brief \ref named-templ-param "Named parameter" for setting PredMap 
   262     /// type
   263     /// \ref named-templ-param "Named parameter" for setting PredMap type
   264     ///
   265     template <class T>
   266     struct DefPredMap {
   267       typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
   268     };
   269     
   270     template <class T>
   271     struct DefDistMapTraits : public Traits {
   272       typedef T DistMap;
   273       static DistMap *createDistMap(const Graph& graph) {
   274 	throw UninitializedParameter();
   275       }
   276     };
   277 
   278     /// \brief \ref named-templ-param "Named parameter" for setting DistMap 
   279     /// type
   280     ///
   281     /// \ref named-templ-param "Named parameter" for setting DistMap type
   282     ///
   283     template <class T>
   284     struct DefDistMap 
   285       : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {
   286       typedef BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
   287     };
   288     
   289     template <class T>
   290     struct DefOperationTraitsTraits : public Traits {
   291       typedef T OperationTraits;
   292     };
   293     
   294     /// \brief \ref named-templ-param "Named parameter" for setting 
   295     /// OperationTraits type
   296     ///
   297     /// \ref named-templ-param "Named parameter" for setting OperationTraits
   298     /// type
   299     template <class T>
   300     struct DefOperationTraits
   301       : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
   302       typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
   303       Create;
   304     };
   305     
   306     ///@}
   307 
   308   protected:
   309     
   310     BelmannFord() {}
   311 
   312   public:      
   313     
   314     /// \brief Constructor.
   315     ///
   316     /// \param _graph the graph the algorithm will run on.
   317     /// \param _length the length map used by the algorithm.
   318     BelmannFord(const Graph& _graph, const LengthMap& _length) :
   319       graph(&_graph), length(&_length),
   320       _pred(0), local_pred(false),
   321       _dist(0), local_dist(false) {}
   322     
   323     ///Destructor.
   324     ~BelmannFord() {
   325       if(local_pred) delete _pred;
   326       if(local_dist) delete _dist;
   327     }
   328 
   329     /// \brief Sets the length map.
   330     ///
   331     /// Sets the length map.
   332     /// \return \c (*this)
   333     BelmannFord &lengthMap(const LengthMap &m) {
   334       length = &m;
   335       return *this;
   336     }
   337 
   338     /// \brief Sets the map storing the predecessor edges.
   339     ///
   340     /// Sets the map storing the predecessor edges.
   341     /// If you don't use this function before calling \ref run(),
   342     /// it will allocate one. The destuctor deallocates this
   343     /// automatically allocated map, of course.
   344     /// \return \c (*this)
   345     BelmannFord &predMap(PredMap &m) {
   346       if(local_pred) {
   347 	delete _pred;
   348 	local_pred=false;
   349       }
   350       _pred = &m;
   351       return *this;
   352     }
   353 
   354     /// \brief Sets the map storing the distances calculated by the algorithm.
   355     ///
   356     /// Sets the map storing the distances calculated by the algorithm.
   357     /// If you don't use this function before calling \ref run(),
   358     /// it will allocate one. The destuctor deallocates this
   359     /// automatically allocated map, of course.
   360     /// \return \c (*this)
   361     BelmannFord &distMap(DistMap &m) {
   362       if(local_dist) {
   363 	delete _dist;
   364 	local_dist=false;
   365       }
   366       _dist = &m;
   367       return *this;
   368     }
   369 
   370     /// \name Execution control
   371     /// The simplest way to execute the algorithm is to use
   372     /// one of the member functions called \c run(...).
   373     /// \n
   374     /// If you need more control on the execution,
   375     /// first you must call \ref init(), then you can add several source nodes
   376     /// with \ref addSource().
   377     /// Finally \ref start() will perform the actual path
   378     /// computation.
   379 
   380     ///@{
   381 
   382     /// \brief Initializes the internal data structures.
   383     /// 
   384     /// Initializes the internal data structures.
   385     void init(const Value value = OperationTraits::infinity()) {
   386       create_maps();
   387       for (NodeIt it(*graph); it != INVALID; ++it) {
   388 	_pred->set(it, INVALID);
   389 	_dist->set(it, value);
   390       }
   391     }
   392     
   393     /// \brief Adds a new source node.
   394     ///
   395     /// The optional second parameter is the initial distance of the node.
   396     /// It just sets the distance of the node to the given value.
   397     void addSource(Node source, Value dst = OperationTraits::zero()) {
   398       _dist->set(source, dst);
   399     }
   400 
   401     /// \brief Executes the algorithm.
   402     ///
   403     /// \pre init() must be called and at least one node should be added
   404     /// with addSource() before using this function.
   405     ///
   406     /// This method runs the %BelmannFord algorithm from the root node(s)
   407     /// in order to compute the shortest path to each node. The algorithm 
   408     /// computes 
   409     /// - The shortest path tree.
   410     /// - The distance of each node from the root(s).
   411     void start() {
   412       int num = countNodes(*graph) - 1;
   413       for (int i = 0; i < num; ++i) {
   414 	bool done = true;
   415 	for (EdgeIt it(*graph); it != INVALID; ++it) {
   416 	  Node source = graph->source(it);
   417 	  Node target = graph->target(it);
   418 	  Value relaxed = 
   419 	    OperationTraits::plus((*_dist)[source], (*length)[it]);
   420 	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
   421 	    _pred->set(target, it);
   422 	    _dist->set(target, relaxed);
   423 	    done = false; 
   424 	  }
   425 	}
   426 	if (done) return;
   427       }
   428     }
   429 
   430     /// \brief Executes the algorithm and checks the negative cycles.
   431     ///
   432     /// \pre init() must be called and at least one node should be added
   433     /// with addSource() before using this function. If there is
   434     /// a negative cycles in the graph it gives back false.
   435     ///
   436     /// This method runs the %BelmannFord algorithm from the root node(s)
   437     /// in order to compute the shortest path to each node. The algorithm 
   438     /// computes 
   439     /// - The shortest path tree.
   440     /// - The distance of each node from the root(s).
   441     bool checkedStart() {
   442       int num = countNodes(*graph);
   443       for (int i = 0; i < num; ++i) {
   444 	bool done = true;
   445 	for (EdgeIt it(*graph); it != INVALID; ++it) {
   446 	  Node source = graph->source(it);
   447 	  Node target = graph->target(it);
   448 	  Value relaxed = 
   449 	    OperationTraits::plus((*_dist)[source], (*length)[it]);
   450 	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
   451 	    _pred->set(target, it);
   452 	    _dist->set(target, relaxed);
   453 	    done = false; 
   454 	  }
   455 	}
   456 	if (done) return true;
   457       }
   458       return false;
   459     }
   460     
   461     /// \brief Runs %BelmannFord algorithm from node \c s.
   462     ///    
   463     /// This method runs the %BelmannFord algorithm from a root node \c s
   464     /// in order to compute the shortest path to each node. The algorithm 
   465     /// computes
   466     /// - The shortest path tree.
   467     /// - The distance of each node from the root.
   468     ///
   469     /// \note d.run(s) is just a shortcut of the following code.
   470     /// \code
   471     ///  d.init();
   472     ///  d.addSource(s);
   473     ///  d.start();
   474     /// \endcode
   475     void run(Node s) {
   476       init();
   477       addSource(s);
   478       start();
   479     }
   480     
   481     ///@}
   482 
   483     /// \name Query Functions
   484     /// The result of the %BelmannFord algorithm can be obtained using these
   485     /// functions.\n
   486     /// Before the use of these functions,
   487     /// either run() or start() must be called.
   488     
   489     ///@{
   490 
   491     /// \brief Copies the shortest path to \c t into \c p
   492     ///    
   493     /// This function copies the shortest path to \c t into \c p.
   494     /// If it \c t is a source itself or unreachable, then it does not
   495     /// alter \c p.
   496     ///
   497     /// \return Returns \c true if a path to \c t was actually copied to \c p,
   498     /// \c false otherwise.
   499     /// \sa DirPath
   500     template <typename Path>
   501     bool getPath(Path &p, Node t) {
   502       if(reached(t)) {
   503 	p.clear();
   504 	typename Path::Builder b(p);
   505 	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
   506 	  b.pushFront(predEdge(t));
   507 	b.commit();
   508 	return true;
   509       }
   510       return false;
   511     }
   512 	  
   513     /// \brief The distance of a node from the root.
   514     ///
   515     /// Returns the distance of a node from the root.
   516     /// \pre \ref run() must be called before using this function.
   517     /// \warning If node \c v in unreachable from the root the return value
   518     /// of this funcion is undefined.
   519     Value dist(Node v) const { return (*_dist)[v]; }
   520 
   521     /// \brief Returns the 'previous edge' of the shortest path tree.
   522     ///
   523     /// For a node \c v it returns the 'previous edge' of the shortest path 
   524     /// tree, i.e. it returns the last edge of a shortest path from the root 
   525     /// to \c v. It is \ref INVALID if \c v is unreachable from the root or 
   526     /// if \c v=s. The shortest path tree used here is equal to the shortest 
   527     /// path tree used in \ref predNode(). 
   528     /// \pre \ref run() must be called before using
   529     /// this function.
   530     Edge predEdge(Node v) const { return (*_pred)[v]; }
   531 
   532     /// \brief Returns the 'previous node' of the shortest path tree.
   533     ///
   534     /// For a node \c v it returns the 'previous node' of the shortest path 
   535     /// tree, i.e. it returns the last but one node from a shortest path from 
   536     /// the root to \c /v. It is INVALID if \c v is unreachable from the root 
   537     /// or if \c v=s. The shortest path tree used here is equal to the 
   538     /// shortest path tree used in \ref predEdge().  \pre \ref run() must be 
   539     /// called before using this function.
   540     Node predNode(Node v) const { 
   541       return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]); 
   542     }
   543     
   544     /// \brief Returns a reference to the NodeMap of distances.
   545     ///
   546     /// Returns a reference to the NodeMap of distances. \pre \ref run() must
   547     /// be called before using this function.
   548     const DistMap &distMap() const { return *_dist;}
   549  
   550     /// \brief Returns a reference to the shortest path tree map.
   551     ///
   552     /// Returns a reference to the NodeMap of the edges of the
   553     /// shortest path tree.
   554     /// \pre \ref run() must be called before using this function.
   555     const PredMap &predMap() const { return *_pred; }
   556  
   557     /// \brief Checks if a node is reachable from the root.
   558     ///
   559     /// Returns \c true if \c v is reachable from the root.
   560     /// \pre \ref run() must be called before using this function.
   561     ///
   562     bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
   563     
   564     ///@}
   565   };
   566  
   567   /// \brief Default traits class of BelmannFord function.
   568   ///
   569   /// Default traits class of BelmannFord function.
   570   /// \param _Graph Graph type.
   571   /// \param _LengthMap Type of length map.
   572   template <typename _Graph, typename _LengthMap>
   573   struct BelmannFordWizardDefaultTraits {
   574     /// \brief The graph type the algorithm runs on. 
   575     typedef _Graph Graph;
   576 
   577     /// \brief The type of the map that stores the edge lengths.
   578     ///
   579     /// The type of the map that stores the edge lengths.
   580     /// It must meet the \ref concept::ReadMap "ReadMap" concept.
   581     typedef _LengthMap LengthMap;
   582 
   583     /// \brief The value type of the length map.
   584     typedef typename _LengthMap::Value Value;
   585 
   586     /// \brief Operation traits for belmann-ford algorithm.
   587     ///
   588     /// It defines the infinity type on the given Value type
   589     /// and the used operation.
   590     /// \see BelmannFordDefaultOperationTraits
   591     typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
   592 
   593     /// \brief The type of the map that stores the last
   594     /// edges of the shortest paths.
   595     /// 
   596     /// The type of the map that stores the last
   597     /// edges of the shortest paths.
   598     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   599     typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
   600 
   601     /// \brief Instantiates a PredMap.
   602     /// 
   603     /// This function instantiates a \ref PredMap. 
   604     static PredMap *createPredMap(const _Graph &) {
   605       return new PredMap();
   606     }
   607     /// \brief The type of the map that stores the dists of the nodes.
   608     ///
   609     /// The type of the map that stores the dists of the nodes.
   610     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   611     typedef NullMap<typename Graph::Node, Value> DistMap;
   612     /// \brief Instantiates a DistMap.
   613     ///
   614     /// This function instantiates a \ref DistMap. 
   615     static DistMap *createDistMap(const _Graph &) {
   616       return new DistMap();
   617     }
   618   };
   619   
   620   /// \brief Default traits used by \ref BelmannFordWizard
   621   ///
   622   /// To make it easier to use BelmannFord algorithm
   623   /// we have created a wizard class.
   624   /// This \ref BelmannFordWizard class needs default traits,
   625   /// as well as the \ref BelmannFord class.
   626   /// The \ref BelmannFordWizardBase is a class to be the default traits of the
   627   /// \ref BelmannFordWizard class.
   628   /// \todo More named parameters are required...
   629   template<class _Graph,class _LengthMap>
   630   class BelmannFordWizardBase 
   631     : public BelmannFordWizardDefaultTraits<_Graph,_LengthMap> {
   632 
   633     typedef BelmannFordWizardDefaultTraits<_Graph,_LengthMap> Base;
   634   protected:
   635     /// Type of the nodes in the graph.
   636     typedef typename Base::Graph::Node Node;
   637 
   638     /// Pointer to the underlying graph.
   639     void *_graph;
   640     /// Pointer to the length map
   641     void *_length;
   642     ///Pointer to the map of predecessors edges.
   643     void *_pred;
   644     ///Pointer to the map of distances.
   645     void *_dist;
   646     ///Pointer to the source node.
   647     Node _source;
   648 
   649     public:
   650     /// Constructor.
   651     
   652     /// This constructor does not require parameters, therefore it initiates
   653     /// all of the attributes to default values (0, INVALID).
   654     BelmannFordWizardBase() : _graph(0), _length(0), _pred(0),
   655 			   _dist(0), _source(INVALID) {}
   656 
   657     /// Constructor.
   658     
   659     /// This constructor requires some parameters,
   660     /// listed in the parameters list.
   661     /// Others are initiated to 0.
   662     /// \param graph is the initial value of  \ref _graph
   663     /// \param length is the initial value of  \ref _length
   664     /// \param source is the initial value of  \ref _source
   665     BelmannFordWizardBase(const _Graph& graph, 
   666 			  const _LengthMap& length, 
   667 			  Node source = INVALID) :
   668       _graph((void *)&graph), _length((void *)&length), _pred(0),
   669       _dist(0), _source(source) {}
   670 
   671   };
   672   
   673   /// A class to make the usage of BelmannFord algorithm easier
   674 
   675   /// This class is created to make it easier to use BelmannFord algorithm.
   676   /// It uses the functions and features of the plain \ref BelmannFord,
   677   /// but it is much simpler to use it.
   678   ///
   679   /// Simplicity means that the way to change the types defined
   680   /// in the traits class is based on functions that returns the new class
   681   /// and not on templatable built-in classes.
   682   /// When using the plain \ref BelmannFord
   683   /// the new class with the modified type comes from
   684   /// the original class by using the ::
   685   /// operator. In the case of \ref BelmannFordWizard only
   686   /// a function have to be called and it will
   687   /// return the needed class.
   688   ///
   689   /// It does not have own \ref run method. When its \ref run method is called
   690   /// it initiates a plain \ref BelmannFord class, and calls the \ref 
   691   /// BelmannFord::run method of it.
   692   template<class _Traits>
   693   class BelmannFordWizard : public _Traits {
   694     typedef _Traits Base;
   695 
   696     ///The type of the underlying graph.
   697     typedef typename _Traits::Graph Graph;
   698 
   699     typedef typename Graph::Node Node;
   700     typedef typename Graph::NodeIt NodeIt;
   701     typedef typename Graph::Edge Edge;
   702     typedef typename Graph::OutEdgeIt EdgeIt;
   703     
   704     ///The type of the map that stores the edge lengths.
   705     typedef typename _Traits::LengthMap LengthMap;
   706 
   707     ///The type of the length of the edges.
   708     typedef typename LengthMap::Value Value;
   709 
   710     ///\brief The type of the map that stores the last
   711     ///edges of the shortest paths.
   712     typedef typename _Traits::PredMap PredMap;
   713 
   714     ///The type of the map that stores the dists of the nodes.
   715     typedef typename _Traits::DistMap DistMap;
   716 
   717   public:
   718     /// Constructor.
   719     BelmannFordWizard() : _Traits() {}
   720 
   721     /// \brief Constructor that requires parameters.
   722     ///
   723     /// Constructor that requires parameters.
   724     /// These parameters will be the default values for the traits class.
   725     BelmannFordWizard(const Graph& graph, const LengthMap& length, 
   726 		      Node source = INVALID) 
   727       : _Traits(graph, length, source) {}
   728 
   729     /// \brief Copy constructor
   730     BelmannFordWizard(const _Traits &b) : _Traits(b) {}
   731 
   732     ~BelmannFordWizard() {}
   733 
   734     /// \brief Runs BelmannFord algorithm from a given node.
   735     ///    
   736     /// Runs BelmannFord algorithm from a given node.
   737     /// The node can be given by the \ref source function.
   738     void run() {
   739       if(Base::_source == INVALID) throw UninitializedParameter();
   740       BelmannFord<Graph,LengthMap,_Traits> 
   741 	bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
   742       if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
   743       if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
   744       bf.run(Base::_source);
   745     }
   746 
   747     /// \brief Runs BelmannFord algorithm from the given node.
   748     ///
   749     /// Runs BelmannFord algorithm from the given node.
   750     /// \param s is the given source.
   751     void run(Node source) {
   752       Base::_source = source;
   753       run();
   754     }
   755 
   756     template<class T>
   757     struct DefPredMapBase : public Base {
   758       typedef T PredMap;
   759       static PredMap *createPredMap(const Graph &) { return 0; };
   760       DefPredMapBase(const _Traits &b) : _Traits(b) {}
   761     };
   762     
   763     ///\brief \ref named-templ-param "Named parameter"
   764     ///function for setting PredMap type
   765     ///
   766     /// \ref named-templ-param "Named parameter"
   767     ///function for setting PredMap type
   768     ///
   769     template<class T>
   770     BelmannFordWizard<DefPredMapBase<T> > predMap(const T &t) 
   771     {
   772       Base::_pred=(void *)&t;
   773       return BelmannFordWizard<DefPredMapBase<T> >(*this);
   774     }
   775     
   776     template<class T>
   777     struct DefDistMapBase : public Base {
   778       typedef T DistMap;
   779       static DistMap *createDistMap(const Graph &) { return 0; };
   780       DefDistMapBase(const _Traits &b) : _Traits(b) {}
   781     };
   782     
   783     ///\brief \ref named-templ-param "Named parameter"
   784     ///function for setting DistMap type
   785     ///
   786     /// \ref named-templ-param "Named parameter"
   787     ///function for setting DistMap type
   788     ///
   789     template<class T>
   790     BelmannFordWizard<DefDistMapBase<T> > distMap(const T &t) {
   791       Base::_dist=(void *)&t;
   792       return BelmannFordWizard<DefDistMapBase<T> >(*this);
   793     }
   794 
   795     template<class T>
   796     struct DefOperationTraitsBase : public Base {
   797       typedef T OperationTraits;
   798       DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
   799     };
   800     
   801     ///\brief \ref named-templ-param "Named parameter"
   802     ///function for setting OperationTraits type
   803     ///
   804     /// \ref named-templ-param "Named parameter"
   805     ///function for setting OperationTraits type
   806     ///
   807     template<class T>
   808     BelmannFordWizard<DefOperationTraitsBase<T> > distMap() {
   809       return BelmannFordWizard<DefDistMapBase<T> >(*this);
   810     }
   811     
   812     /// \brief Sets the source node, from which the BelmannFord algorithm runs.
   813     ///
   814     /// Sets the source node, from which the BelmannFord algorithm runs.
   815     /// \param s is the source node.
   816     BelmannFordWizard<_Traits>& source(Node source) {
   817       Base::_source = source;
   818       return *this;
   819     }
   820     
   821   };
   822   
   823   /// \brief Function type interface for BelmannFord algorithm.
   824   ///
   825   /// \ingroup flowalgs
   826   /// Function type interface for BelmannFord algorithm.
   827   ///
   828   /// This function also has several \ref named-templ-func-param 
   829   /// "named parameters", they are declared as the members of class 
   830   /// \ref BelmannFordWizard.
   831   /// The following
   832   /// example shows how to use these parameters.
   833   /// \code
   834   /// belmannford(g,length,source).predMap(preds).run();
   835   /// \endcode
   836   /// \warning Don't forget to put the \ref BelmannFordWizard::run() "run()"
   837   /// to the end of the parameter list.
   838   /// \sa BelmannFordWizard
   839   /// \sa BelmannFord
   840   template<class _Graph, class _LengthMap>
   841   BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
   842   belmannFord(const _Graph& graph,
   843 	      const _LengthMap& length, 
   844 	      typename _Graph::Node source = INVALID) {
   845     return BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
   846       (graph, length, source);
   847   }
   848 
   849 } //END OF NAMESPACE LEMON
   850 
   851 #endif
   852