#ifndef LEMON_BELMANN_FORD_H

 #ifndef LEMON_BELLMAN_FORD_H

 #define LEMON_BELMANN_FORD_H

 #define LEMON_BELLMAN_FORD_H

   /// It defines all computational operations and constants which are

   /// This operation traits class defines all computational operations

   /// used in the Bellman-Ford algorithm. The default implementation

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

   /// is based on the numeric_limits class. If the numeric type does not

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

   /// have infinity value then the maximum value is used as extremal

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

   /// infinity value.

   /// value is used as extremal infinity value.

     typename Value, 

     typename V, 

     bool has_infinity = std::numeric_limits<Value>::has_infinity>

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

     /// \brief Gives back true only if the first value less than the second.

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

     /// the second.

   template <typename Value>

   template <typename V>

   struct BellmanFordDefaultOperationTraits<Value, false> {

   struct BellmanFordDefaultOperationTraits<V, false> {

     typedef V Value;

   /// \param _Digraph Digraph type.

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

   /// \param _LegthMap Type of length map.

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

   template<class _Digraph, class _LengthMap>

   template<typename GR, typename LEN>

     /// The digraph type the algorithm runs on. 

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

     typedef _Digraph Digraph;

     typedef GR Digraph;

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

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

     typedef _LengthMap LengthMap;

     typedef LEN LengthMap;

     // The type of the length of the arcs.

     /// The type of the arc lengths.

     typedef typename _LengthMap::Value Value;

     typedef typename LEN::Value Value;

     /// It defines the infinity type on the given Value type

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

     /// and the used operation.

     /// given \c Value type.

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

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

     ///

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

     typedef typename Digraph::template NodeMap<typename _Digraph::Arc> PredMap;

     /// \brief Instantiates a \c PredMap.

     /// \brief Instantiates a PredMap.

     /// \param digraph is the digraph, to which we would like to define the PredMap.

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

     static PredMap *createPredMap(const _Digraph& digraph) {

     /// \ref PredMap.

       return new PredMap(digraph);

     static PredMap *createPredMap(const GR& g) {

     }

       return new PredMap(g);

     }

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

     ///

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

     /// The type of the map that stores the dists of the nodes.

     ///

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

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

     ///

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

     typedef typename Digraph::template NodeMap<typename _LengthMap::Value> 

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

     DistMap;

     /// \brief Instantiates a \c DistMap.

     /// \brief Instantiates a DistMap.

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

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

     /// \ref DistMap

     /// \ref DistMap.

     static DistMap *createDistMap(const _Digraph& digraph) {

     static DistMap *createDistMap(const GR& g) {

       return new DistMap(digraph);

       return new DistMap(g);

   /// This class provides an efficient implementation of \c Bellman-Ford 

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

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

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

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

   ///

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

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

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

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

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

   ///

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

   /// kind of length.

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

   ///

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

   /// The Bellman-Ford algorithm solves the shortest path from one node

   ///

   /// problem when the arcs can have negative length but the digraph should

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

   /// not contain cycles with negative sum of length. If we can assume

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

   /// that all arc is non-negative in the digraph then the dijkstra algorithm

   /// it can be used easier.

   /// should be used rather.

   ///

   ///

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

   /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.

   /// The default type is \ref ListDigraph.

   ///

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

   /// The type of the length is determined by the

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

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

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

   ///

   /// \param _Digraph The digraph type the algorithm runs on. The default value

   /// is \ref ListDigraph. The value of _Digraph is not used directly by

   /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.

   /// \param _LengthMap This read-only ArcMap determines the lengths of the

   /// arcs. The default map type is \ref concepts::Digraph::ArcMap 

   /// "Digraph::ArcMap<int>".  The value of _LengthMap is not used directly 

   /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.  

   /// \param _Traits Traits class to set various data types used by the 

   /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits

   /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>".  See \ref

   /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits

   /// class.

   template <typename _Digraph, typename _LengthMap, typename _Traits>

   template <typename GR, typename LEN, typename TR>

   template <typename _Digraph,

   template <typename GR=ListDigraph,

 	    typename _LengthMap=typename _Digraph::template ArcMap<int>,

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

 	    typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> >

             typename TR=BellmanFordDefaultTraits<GR,LEN> >

     typedef typename _Traits::Digraph Digraph;

     typedef typename TR::Digraph Digraph;

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

     typedef typename TR::LengthMap::Value Value;

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

     typedef typename TR::LengthMap LengthMap;

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

     /// arcs of the shortest paths.

     typedef typename TR::PredMap PredMap;

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

     typedef typename TR::DistMap DistMap;

     /// The type of the paths.

     typedef PredMapPath<Digraph, PredMap> Path;

     ///\brief The \ref BellmanFordDefaultOperationTraits

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

     typedef typename TR::OperationTraits OperationTraits;

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

     typedef TR Traits;

   private:

     /// \brief The type of the length of the arcs.

     // Pointer to the underlying digraph.

     typedef typename _Traits::LengthMap::Value Value;

     const Digraph *_gr;

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

     // Pointer to the length map

     typedef typename _Traits::LengthMap LengthMap;

     const LengthMap *_length;

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

     // Pointer to the map of predecessors arcs.

     /// arcs of the shortest paths.

     typedef typename _Traits::PredMap PredMap;

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

     typedef typename _Traits::DistMap DistMap;

     /// \brief The operation traits.

     typedef typename _Traits::OperationTraits OperationTraits;

   private:

     /// Pointer to the underlying digraph.

     const Digraph *digraph;

     /// Pointer to the length map

     const LengthMap *length;

     ///Pointer to the map of predecessors arcs.

     ///Indicates if \ref _pred is locally allocated (\c true) or not.

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

     bool local_pred;

     bool _local_pred;

     ///Pointer to the map of distances.

     // Pointer to the map of distances.

     ///Indicates if \ref _dist is locally allocated (\c true) or not.

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

     bool local_dist;

     bool _local_dist;

     /// Creates the maps if necessary.

     // Creates the maps if necessary.

 	local_pred = true;

 	_local_pred = true;

 	_pred = Traits::createPredMap(*digraph);

 	_pred = Traits::createPredMap(*_gr);

 	local_dist = true;

 	_local_dist = true;

 	_dist = Traits::createDistMap(*digraph);

 	_dist = Traits::createDistMap(*_gr);

       }

       }

       _mask = new MaskMap(*digraph, false);

       _mask = new MaskMap(*_gr, false);

     /// \name Named template parameters

     /// \name Named Template Parameters

     struct DefPredMapTraits : public Traits {

     struct SetPredMapTraits : public Traits {

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

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

     /// type

     /// \c PredMap type.

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

     ///

     ///

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

     /// \c PredMap type.

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

       : public BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > {

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

       typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > Create;

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

     struct DefDistMapTraits : public Traits {

     struct SetDistMapTraits : public Traits {

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

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

     /// type

     /// \c DistMap type.

     ///

     ///

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

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

     ///

     /// \c DistMap type.

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

       : public BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > {

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

       typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > Create;

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

     struct DefOperationTraitsTraits : public Traits {

     struct SetOperationTraitsTraits : public Traits {

     /// OperationTraits type

     /// \c OperationTraits type.

     ///

     ///

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

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

     /// type

     /// \c OperationTraits type.

     /// For more information see \ref BellmanFordDefaultOperationTraits.

       : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> > {

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

       typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> >

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

     /// \param _graph the digraph the algorithm will run on.

     /// Constructor.

     /// \param _length the length map used by the algorithm.

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

     BellmanFord(const Digraph& _graph, const LengthMap& _length) :

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

       digraph(&_graph), length(&_length),

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

       _pred(0), local_pred(false),

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

       _dist(0), local_dist(false), _mask(0) {}

       _pred(0), _local_pred(false),

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

       if(local_pred) delete _pred;

       if(_local_pred) delete _pred;

       if(local_dist) delete _dist;

       if(_local_dist) delete _dist;

     /// \return \c (*this)

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

     BellmanFord &lengthMap(const LengthMap &m) {

     BellmanFord &lengthMap(const LengthMap &map) {

       length = &m;

       _length = ↦

     /// \brief Sets the map storing the predecessor arcs.

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

     ///

     ///

     /// Sets the map storing the predecessor arcs.

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

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

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

     /// it will allocate one. The destuctor deallocates this

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

     /// automatically allocated map, of course.

     /// The destructor deallocates this automatically allocated map,

     /// \return \c (*this)

     /// of course.

     BellmanFord &predMap(PredMap &m) {

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

       if(local_pred) {

     BellmanFord &predMap(PredMap &map) {

       if(_local_pred) {

 	local_pred=false;

 	_local_pred=false;

       }

       }

       _pred = &m;

       _pred = ↦

     /// \brief Sets the map storing the distances calculated by the algorithm.

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

     ///

     ///

     /// Sets the map storing the distances calculated by the algorithm.

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

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

     /// by the algorithm.

     /// it will allocate one. The destuctor deallocates this

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

     /// automatically allocated map, of course.

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

     /// \return \c (*this)

     /// The destructor deallocates this automatically allocated map,

     BellmanFord &distMap(DistMap &m) {

     /// of course.

       if(local_dist) {

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

     BellmanFord &distMap(DistMap &map) {

       if(_local_dist) {

 	local_dist=false;

 	_local_dist=false;

       }

       }

       _dist = &m;

       _dist = ↦

     /// \name Execution control

     /// \name Execution Control

     /// The simplest way to execute the algorithm is to use

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

     /// one of the member functions called \c run(...).

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

     /// \n

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

     /// If you need more control on the execution,

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

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

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

     /// with \ref addSource().

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

     /// Finally \ref start() will perform the actual path

     /// \ref limitedStart().

     /// computation.

     /// Initializes the internal data structures.

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

     /// is the initial distance of each node.

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

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

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

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

     /// Adds a new source node. The optional second parameter is the 

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

     /// initial distance of the node. It just sets the distance of the 

     /// is the initial distance of the node.

     /// node to the given value.

     /// exactly for all at most \f$ k \f$ length path lengths then it will

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

     /// calculate the distances exactly for all at most \f$ k + 1 \f$

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

     /// length path lengths. With \f$ k \f$ iteration this function

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

     /// calculates the at most \f$ k \f$ length path lengths.

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

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

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

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

     /// need the shortest path and not just the distance you should store

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

     /// after each iteration the \ref predMap() map and manually build

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

     /// the path.

     /// and build the path manually.

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

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

 	  Node target = digraph->target(it);

 	  Node target = _gr->target(it);

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

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

     /// If the algorithm calculated the distances in the

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

     /// previous round at least for all at most k length paths then it will

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

     /// calculate the distances at least for all at most k + 1 length paths.

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

     /// This function does not make it possible to calculate strictly the

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

     /// at most k length minimal paths, this is why it is

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

     /// called just weak round.

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

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

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

     ///

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

     /// paths.

     ///

     /// \see ActiveIt

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

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

 	  Node target = digraph->target(it);

 	  Node target = _gr->target(it);

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

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

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

     /// Executes the algorithm.

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

     ///

     ///

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

     /// This method runs the %BellmanFord algorithm from the root node(s)

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

     /// in order to compute the shortest path to each node. The algorithm 

     ///

     /// computes 

     /// The algorithm computes

     /// - The shortest path tree.

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

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

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

     ///

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

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

       int num = countNodes(*digraph) - 1;

       int num = countNodes(*_gr) - 1;

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

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

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

     ///

     ///

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

     /// This method runs the %BellmanFord algorithm from the root node(s)

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

     /// in order to compute the shortest path to each node. The algorithm 

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

     /// computes 

     ///

     /// - The shortest path tree.

     /// The algorithm computes 

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

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

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

       int num = countNodes(*digraph);

       int num = countNodes(*_gr);

     /// \brief Executes the algorithm with path length limit.

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

     ///

     ///

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

     /// Executes the algorithm with arc number limit.

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

     ///

     ///

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

     /// This method runs the %BellmanFord algorithm from the root

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

     /// node(s) in order to compute the shortest path lengths with at

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

     /// most \c num arc.

     ///

     /// The algorithm computes

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

     /// - the predecessor arc for each node.

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

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

     /// need the shortest path and not just the distance you should store

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

     /// after each iteration the \ref predMap() map and manually build

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

     /// the path.

     /// and build the path manually.

     ///

     ///

     /// The algorithm computes

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

     /// - The predecessor arc from each node.

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

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

     /// \brief Runs %BellmanFord algorithm from node \c s.

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

     /// This method runs the %BellmanFord algorithm from a root node \c s

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

     /// in order to compute the shortest path to each node. The algorithm 

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

     /// computes

     ///

     /// - The shortest path tree.

     /// The algorithm computes

     /// - The distance of each node from the root.

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

     ///

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

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

     ///

     ///\code

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

     ///  d.init();

     /// \code

     ///  d.addSource(s);

     ///   bf.init();

     ///  d.start();

     ///   bf.addSource(s);

     ///\endcode

     ///   bf.start();

     /// \endcode

     /// \brief Runs %BellmanFord algorithm with limited path length 

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

     /// from node \c s.

     /// number limit.

     /// This method runs the %BellmanFord algorithm from a root node \c s

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

     /// in order to compute the shortest path with at most \c len arcs 

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

     /// to each node. The algorithm computes

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

     /// - The shortest path tree.

     ///

     /// - The distance of each node from the root.

     /// The algorithm computes

     ///

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

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

     /// - the predecessor arc for each node.

     ///\code

     ///

     ///  d.init();

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

     ///  d.addSource(s);

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

     ///  d.limitedStart(num);

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

     ///\endcode

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

     /// and build the path manually.

     ///

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

     /// \code

     ///   bf.init();

     ///   bf.addSource(s);

     ///   bf.limitedStart(num);

     /// \endcode

     /// \name Query Functions

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

     /// The result of the %BellmanFord algorithm can be obtained using these

     ///

     /// functions.\n

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

     /// Before the use of these functions,

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

     /// either run() or start() must be called.

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

     /// find augmenting arcs outgoing from them.

     ///@{

     /// \brief Lemon iterator for get the active nodes.

     ///

     /// Lemon iterator for get the active nodes. This class provides a

     /// common style lemon iterator which gives back a subset of the

     /// nodes. The iterated nodes are active in the algorithm after

     /// the last phase so these should be checked in the next phase to

     /// find augmenting arcs from these.

       /// Constructor for get the nodeset of the variable. 

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

       /// instance. 

       /// \brief Conversion to node.

       /// \brief Conversion to \c Node.

       /// Conversion to node.

       /// Conversion to \c Node.

     typedef PredMapPath<Digraph, PredMap> Path;

     /// \name Query Functions

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

     /// \brief Gives back the shortest path.

     /// functions.\n

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

     ///@{

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

     /// Gives back the shortest path.

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

     /// \pre The \c t should be reachable from the source.

     ///

     Path path(Node t) 

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

     ///

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

     /// using this function.

     Path path(Node t) const

       return Path(*digraph, *_pred, t);

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

     }

     }

     // TODO : implement negative cycle

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

 //     ///    

 //     /// This function gives back a negative cycle.

 //     /// If the algorithm have not found yet negative cycle it will give back

 //     /// an empty path.

 //     Path negativeCycle() {

 //       typename Digraph::template NodeMap<int> state(*digraph, 0);

 //       for (ActiveIt it(*this); it != INVALID; ++it) {

 //         if (state[it] == 0) {

 //           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {

 //             if (state[t] == 0) {

 //               state[t] = 1;

 //             } else if (state[t] == 2) {

 //               break;

 //             } else {

 //               p.clear();

 //               typename Path::Builder b(p);

 //               b.setStartNode(t);

 //               b.pushFront(predArc(t));

 //               for(Node s = predNode(t); s != t; s = predNode(s)) {

 //                 b.pushFront(predArc(s));

 //               }

 //               b.commit();

 //               return true;

 //             }

 //           }

 //           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {

 //             if (state[t] == 1) {

 //               state[t] = 2;

 //             } else {

 //               break;

 //             }

 //           }

 //         }

 //       }

 //       return false;

 //     }

     /// \brief The distance of a node from the root.

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

     ///

     ///

     /// Returns the distance of a node from the root.

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

     /// \pre \ref run() must be called before using this function.

     ///

     /// \warning If node \c v in unreachable from the root the return value

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

     /// of this funcion is undefined.

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

     ///

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

     /// using this function.

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

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

     ///

     /// the given node.

     /// For a node \c v it returns the 'previous arc' of the shortest path 

     ///

     /// tree, i.e. it returns the last arc of a shortest path from the root 

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

     /// to \c v. It is \ref INVALID if \c v is unreachable from the root or 

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

     /// if \c v=s. The shortest path tree used here is equal to the shortest 

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

     /// path tree used in \ref predNode(). 

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

     /// \pre \ref run() must be called before using

     ///

     /// this function.

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

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

     ///

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

     /// using this function.

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

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

     ///

     /// the given node.

     /// For a node \c v it returns the 'previous node' of the shortest path 

     ///

     /// tree, i.e. it returns the last but one node from a shortest path from 

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

     /// the root to \c /v. It is INVALID if \c v is unreachable from the root 

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

     /// or if \c v=s. The shortest path tree used here is equal to the 

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

     /// shortest path tree used in \ref predArc().  \pre \ref run() must be 

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

     /// called before using this function.

     ///

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

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

     ///

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

     /// using this function.

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

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

     }

     }

     /// \brief Returns a reference to the NodeMap of distances.

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

     ///

     /// distances of the nodes.

     /// Returns a reference to the NodeMap of distances. \pre \ref run() must

     ///

     /// be called before using this function.

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

     /// of the nodes calculated by the algorithm.

     ///

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

     /// using this function.

     /// \brief Returns a reference to the shortest path tree map.

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

     ///

     /// predecessor arcs.

     /// Returns a reference to the NodeMap of the arcs of the

     ///

     /// shortest path tree.

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

     /// \pre \ref run() must be called before using this function.

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

     ///

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

     /// using this function.

     /// \brief Checks if a node is reachable from the root.

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

     ///

     ///

     /// Returns \c true if \c v is reachable from the root.

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

     /// \pre \ref run() must be called before using this function.

     ///

     ///

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

     bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }

     /// using this function.

     bool reached(Node v) const {

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

     }

     // TODO: implement negative cycle

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

 //    ///    

 //    /// This function gives back a negative cycle.

 //    /// If the algorithm have not found yet negative cycle it will give back

 //    /// an empty path.

 //    Path negativeCycle() {

 //      typename Digraph::template NodeMap<int> state(*digraph, 0);

 //      for (ActiveIt it(*this); it != INVALID; ++it) {

 //        if (state[it] == 0) {

 //          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {

 //            if (state[t] == 0) {

 //              state[t] = 1;

 //            } else if (state[t] == 2) {

 //              break;

 //            } else {

 //              p.clear();

 //              typename Path::Builder b(p);

 //              b.setStartNode(t);

 //              b.pushFront(predArc(t));

 //              for(Node s = predNode(t); s != t; s = predNode(s)) {

 //                b.pushFront(predArc(s));

 //              }

 //              b.commit();

 //              return true;

 //            }

 //          }

 //          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {

 //            if (state[t] == 1) {

 //              state[t] = 2;

 //            } else {

 //              break;

 //            }

 //          }

 //        }

 //      }

 //      return false;

 //    }

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

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

   ///

   ///

   /// Default traits class of BellmanFord function.

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

   /// \param _Digraph Digraph type.

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

   /// \param _LengthMap Type of length map.

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

   template <typename _Digraph, typename _LengthMap>

   template <typename GR, typename LEN>

     /// \brief The digraph type the algorithm runs on. 

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

     typedef _Digraph Digraph;

     typedef GR Digraph;

     typedef _LengthMap LengthMap;

     typedef LEN LengthMap;

     /// \brief The value type of the length map.

     /// The type of the arc lengths.

     typedef typename _LengthMap::Value Value;

     typedef typename LEN::Value Value;

     /// It defines the infinity type on the given Value type

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

     /// and the used operation.

     /// given \c Value type.

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

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

     /// arcs of the shortest paths.

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

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

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

     typedef NullMap <typename _Digraph::Node,typename _Digraph::Arc> PredMap;

     /// \brief Instantiates a \c PredMap.

     /// \brief Instantiates a PredMap.

     /// This function instantiates a \ref PredMap. 

     /// This function instantiates a \ref PredMap.

     static PredMap *createPredMap(const _Digraph &) {

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

       return new PredMap();

     /// \ref PredMap.

     }

     static PredMap *createPredMap(const GR &g) {

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

       return new PredMap(g);

     ///

     }

     /// The type of the map that stores the dists of the nodes.

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

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

     typedef NullMap<typename Digraph::Node, Value> DistMap;

     ///

     /// \brief Instantiates a DistMap.

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

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

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

     /// \brief Instantiates a \c DistMap.

     static DistMap *createDistMap(const _Digraph &) {

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

       return new DistMap();

     /// \ref DistMap.

     }

     static DistMap *createDistMap(const GR &g) {

       return new DistMap(g);

     }

     ///The type of the shortest paths.

     ///The type of the shortest paths.

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

     typedef lemon::Path<Digraph> Path;

   /// \brief Default traits used by \ref BellmanFordWizard

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

   ///

   ///

   /// To make it easier to use BellmanFord algorithm

   /// Default traits class used by BellmanFordWizard.

   /// we have created a wizard class.

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

   /// This \ref BellmanFordWizard class needs default traits,

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

   /// as well as the \ref BellmanFord class.

   template <typename GR, typename LEN>

   /// The \ref BellmanFordWizardBase is a class to be the default traits of the

   /// \ref BellmanFordWizard class.

   /// \todo More named parameters are required...

   template<class _Digraph,class _LengthMap>

     : public BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> {

     : public BellmanFordWizardDefaultTraits<GR, LEN> {

     typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base;

     typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;

     /// Type of the nodes in the digraph.

     // Type of the nodes in the digraph.

     /// Pointer to the underlying digraph.

     // Pointer to the underlying digraph.

     /// Pointer to the length map

     // Pointer to the length map

     ///Pointer to the map of predecessors arcs.

     // Pointer to the map of predecessors arcs.

     ///Pointer to the map of distances.

     // Pointer to the map of distances.

     ///Pointer to the source node.

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

     Node _source;

     void *_path;

     //Pointer to the distance of the target node.

     void *_di;

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

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

     /// all of the attributes to default values (0, INVALID).

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

     BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),

     BellmanFordWizardBase() :

 			   _dist(0), _source(INVALID) {}

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

     /// This constructor requires some parameters,

     /// This constructor requires two parameters,

     /// listed in the parameters list.

     /// others are initiated to \c 0.

     /// Others are initiated to 0.

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

     /// \param digraph is the initial value of  \ref _graph

     /// \param len The length map.

     /// \param length is the initial value of  \ref _length

     BellmanFordWizardBase(const GR& gr, 

     /// \param source is the initial value of  \ref _source

 			  const LEN& len) :

     BellmanFordWizardBase(const _Digraph& digraph, 

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

 			  const _LengthMap& length, 

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

 			  Node source = INVALID) :

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

       _graph(reinterpret_cast<void*>(const_cast<_Digraph*>(&digraph))), 

       _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))), 

       _pred(0), _dist(0), _source(source) {}

   /// A class to make the usage of BellmanFord algorithm easier

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

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

   /// This class is created to make it easier to use BellmanFord algorithm.

   ///

   /// It uses the functions and features of the plain \ref BellmanFord,

   /// This auxiliary class is created to implement the

   /// but it is much simpler to use it.

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

   ///

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

   /// Simplicity means that the way to change the types defined

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

   /// in the traits class is based on functions that returns the new class

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

   /// and not on templatable built-in classes.

   ///

   /// When using the plain \ref BellmanFord

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

   /// the new class with the modified type comes from

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

   /// the original class by using the ::

   template<class TR>

   /// operator. In the case of \ref BellmanFordWizard only

   class BellmanFordWizard : public TR {

   /// a function have to be called and it will

     typedef TR Base;

   /// return the needed class.

   ///

     typedef typename TR::Digraph Digraph;

   /// It does not have own \ref run method. When its \ref run method is called

   /// it initiates a plain \ref BellmanFord class, and calls the \ref 

   /// BellmanFord::run method of it.

   template<class _Traits>

   class BellmanFordWizard : public _Traits {

     typedef _Traits Base;

     ///The type of the underlying digraph.

     typedef typename _Traits::Digraph Digraph;

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

     typedef typename TR::LengthMap LengthMap;

     typedef typename _Traits::LengthMap LengthMap;

     ///The type of the length of the arcs.

     typedef typename TR::PredMap PredMap;

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

     typedef typename TR::DistMap DistMap;

     ///arcs of the shortest paths.

     typedef typename TR::Path Path;

     typedef typename _Traits::PredMap PredMap;

     ///The type of the map that stores the dists of the nodes.

     typedef typename _Traits::DistMap DistMap;

     BellmanFordWizard() : _Traits() {}

     BellmanFordWizard() : TR() {}

     BellmanFordWizard(const Digraph& digraph, const LengthMap& length, 

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

 		      Node src = INVALID) 

     /// \param len The length map.

       : _Traits(digraph, length, src) {}

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

       : TR(gr, len) {}

     BellmanFordWizard(const _Traits &b) : _Traits(b) {}

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

     /// \brief Runs BellmanFord algorithm from a given node.

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

     /// Runs BellmanFord algorithm from a given node.

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

     /// The node can be given by the \ref source function.

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

     void run() {

     void run(Node s) {

       LEMON_ASSERT(Base::_source != INVALID, "Source node is not given");

       BellmanFord<Digraph,LengthMap,TR> 

       BellmanFord<Digraph,LengthMap,_Traits> 

       bf.run(Base::_source);

       bf.run(s);

     }

     }

     /// \brief Runs BellmanFord algorithm from the given node.

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

     ///

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

     /// Runs BellmanFord algorithm from the given node.

     ///

     /// \param src is the given source.

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

     void run(Node src) {

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

       Base::_source = src;

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

       run();

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

     /// for a single target node easier.

     ///

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

     bool run(Node s, Node t) {

       BellmanFord<Digraph,LengthMap,TR>

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

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

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

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

       bf.run(s);

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

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

       return bf.reached(t);

     struct DefPredMapBase : public Base {

     struct SetPredMapBase : public Base {

       DefPredMapBase(const _Traits &b) : _Traits(b) {}

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

     ///\brief \ref named-templ-param "Named parameter"

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

     ///function for setting PredMap type

     /// the predecessor map.

     ///

     ///

     /// \ref named-templ-param "Named parameter"

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

     ///function for setting PredMap type

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

     ///

     BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 

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

     {

       return BellmanFordWizard<DefPredMapBase<T> >(*this);

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

     struct DefDistMapBase : public Base {

     struct SetDistMapBase : public Base {

       DefDistMapBase(const _Traits &b) : _Traits(b) {}

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

     ///\brief \ref named-templ-param "Named parameter"

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

     ///function for setting DistMap type

     /// the distance map.

     ///

     ///

     /// \ref named-templ-param "Named parameter"

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

     ///function for setting DistMap type

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

     ///

     /// by the algorithm.

     BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {

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

       return BellmanFordWizard<DefDistMapBase<T> >(*this);

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

     struct DefOperationTraitsBase : public Base {

     struct SetPathBase : public Base {

       typedef T OperationTraits;

       typedef T Path;

       DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}

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

     ///\brief \ref named-templ-param "Named parameter"

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

     ///function for setting OperationTraits type

     /// the shortest path to the target node.

     ///

     ///

     /// \ref named-templ-param "Named parameter"

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

     ///function for setting OperationTraits type

     /// the shortest path to the target node.

     ///

     BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {

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

       return BellmanFordWizard<DefDistMapBase<T> >(*this);

     {

     }

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

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

     /// \brief Sets the source node, from which the BellmanFord algorithm runs.

     }

     ///

     /// Sets the source node, from which the BellmanFord algorithm runs.

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

     /// \param src is the source node.

     /// the distance of the target node.

     BellmanFordWizard<_Traits>& source(Node src) {

     ///

       Base::_source = src;

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

     /// the distance of the target node.

     BellmanFordWizard dist(const Value &d)

     {

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

   /// \brief Function type interface for BellmanFord algorithm.

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

   /// algorithm.

   /// Function type interface for BellmanFord algorithm.