RhodeCode

 *

 */

#ifndef LEMON_BFS_H

#define LEMON_BFS_H

///\ingroup search

///\file

///\brief Bfs algorithm.

#include <lemon/list_graph.h>

#include <lemon/graph_utils.h>

#include <lemon/bits/path_dump.h>

#include <lemon/bits/invalid.h>

#include <lemon/error.h>

#include <lemon/maps.h>

namespace lemon {

  ///Default traits class of Bfs class.

  ///Default traits class of Bfs class.

  template<class GR>

  struct BfsDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

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

    ///arcs of the shortest paths.

    /// 

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

    ///arcs of the shortest paths.

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

    ///

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

    ///Instantiates a PredMap.

    ///This function instantiates a \ref PredMap. 

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

    ///\todo The digraph alone may be insufficient to initialize

    static PredMap *createPredMap(const GR &G) 

    {

      return new PredMap(G);

    }

    ///The type of the map that indicates which nodes are processed.

    {

      return new ReachedMap(G);

    }

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

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

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

    ///

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap. 

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

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

  ///%BFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %BFS algorithm.

  ///

  ///\ref ListDigraph. The value of GR is not used directly by Bfs, it

  ///is only passed to \ref BfsDefaultTraits.

  ///The default traits class is

  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".

  ///See \ref BfsDefaultTraits for the documentation of

  ///a Bfs traits class.

#ifdef DOXYGEN

  template <typename GR,

	    typename TR>

#else

  template <typename GR=ListDigraph,

	    typename TR=BfsDefaultTraits<GR> >

#endif

  class Bfs {

  public:

    /**

     * \brief \ref Exception for uninitialized parameters.

     *

     * This error represents problems in the initialization

     * of the parameters of the algorithms.

     */

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw() {

	return "lemon::Bfs::UninitializedParameter";

      }

    };

    typedef TR Traits;

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

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

    ///shortest path tree.

    ///\pre Either \ref run() or \ref init()

    ///must be called before using this function.

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

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

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

    ///\warning The source nodes are indicated as unreached.

    ///\pre Either \ref run() or \ref start()

    ///must be called before using this function.

    ///

    bool reached(Node v) { return (*_reached)[v]; }

    ///@}

  };

  ///Default traits class of Bfs function.

  ///Default traits class of Bfs function.

  template<class GR>

  struct BfsWizardDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

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

    ///arcs of the shortest paths.

    /// 

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

    ///arcs of the shortest paths.

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

    ///

    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;

    ///Instantiates a PredMap.

    ///This function instantiates a \ref PredMap. 

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

    ///\todo The digraph alone may be insufficient to initialize

#ifdef DOXYGEN

    static PredMap *createPredMap(const GR &g) 

#else

    static PredMap *createPredMap(const GR &) 

#endif

    {

    void reach(const Node&) {}

    void examine(const Arc&) {}

    void start(const Node&) {}

    void process(const Node&) {}

    template <typename _Visitor>

    struct Constraints {

      void constraints() {

	Arc arc;

	Node node;

	visitor.discover(arc);

	visitor.reach(node);

	visitor.examine(arc);

	visitor.start(node);

        visitor.process(node);

      }

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of BfsVisit class.

  ///

  /// Default traits class of BfsVisit class.

  template<class _Digraph>

  struct BfsVisitDefaultTraits {

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

    typedef _Digraph Digraph;

    /// \brief The type of the map that indicates which nodes are reached.

    /// 

    /// The type of the map that indicates which nodes are reached.

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

    /// \todo named parameter to set this type, function to read and write.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap. 

    /// \param digraph is the digraph, to which

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///  

  /// \brief %BFS Visit algorithm class.

  ///  

  /// This class provides an efficient implementation of the %BFS algorithm

  /// with visitor interface.

  ///

  /// The %BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// on every bfs event the \c Visitor class member functions. 

  ///

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

  /// is only passed to \ref BfsDefaultTraits.

  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which

  /// does not observe the Bfs events. If you want to observe the bfs

  /// events you should implement your own Visitor class.

  /// algorithm. The default traits class is

  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a Bfs visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

	    typename _Visitor = BfsVisitor<_Digraph>,

	    typename _Traits = BfsDefaultTraits<_Digraph> >

#endif

  class BfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    ///

    /// This error represents problems in the initialization

    /// of the parameters of the algorithms.

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw() 

      {

	return "lemon::BfsVisit::UninitializedParameter";

      }

    };

    typedef _Traits Traits;

#ifndef LEMON_BIN_HEAP_H

#define LEMON_BIN_HEAP_H

///\ingroup auxdat

///\file

///\brief Binary Heap implementation.

#include <vector>

#include <utility>

#include <functional>

namespace lemon {

  ///\ingroup auxdat

  ///

  ///\brief A Binary Heap implementation.

  ///

  ///This class implements the \e binary \e heap data structure. A \e heap

  ///is a data structure for storing items with specified values called \e

  ///priorities in such a way that finding the item with minimum priority is

  ///efficient. \c Compare specifies the ordering of the priorities. In a heap

  ///one can change the priority of an item, add or erase an item, etc.

  ///

  ///to handle the cross references.

  ///default is \c std::less<_Prio>.

  ///

  ///\sa FibHeap

  ///\sa Dijkstra

  template <typename _Prio, typename _ItemIntMap,

	    typename _Compare = std::less<_Prio> >

  class BinHeap {

  public:

    ///\e

    typedef _ItemIntMap ItemIntMap;

    ///\e

    typedef _Prio Prio;

    ///\e

    typedef typename ItemIntMap::Key Item;

    ///\e

    typedef std::pair<Item,Prio> Pair;

    ///\e

    typedef _Compare Compare;

    /// \brief Type to represent the items states.

    ///

    /// Each Item element have a state associated to it. It may be "in heap",

    /// "pre heap" or "post heap". The latter two are indifferent from the

  /// alteration handlers should not call any function which signals

  /// an other alteration in the same notifier and should not

  /// detach any observer from the notifier.

  ///

  /// Alteration observers try to be exception safe. If an \e add() or

  /// a \e clear() function throws an exception then the remaining

  /// observeres will not be notified and the fulfilled additions will

  /// be rolled back by calling the \e erase() or \e clear()

  /// functions. Thence the \e erase() and \e clear() should not throw

  /// exception. Actullay, it can be throw only 

  /// \ref AlterationObserver::ImmediateDetach ImmediateDetach

  /// exception which detach the observer from the notifier.

  ///

  /// There are some place when the alteration observing is not completly

  /// reliable. If we want to carry out the node degree in the graph

  /// as in the \ref InDegMap and we use the reverseEdge that cause 

  /// unreliable functionality. Because the alteration observing signals

  /// only erasing and adding but not the reversing it will stores bad

  /// degrees. The sub graph adaptors cannot signal the alterations because

  /// just a setting in the filter map can modify the graph and this cannot

  /// be watched in any way.

  ///

  /// \param _Container The container which is observed.

  /// \param _Item The item type which is obserbved.

  template <typename _Container, typename _Item>

  class AlterationNotifier {

  public:

    typedef True Notifier;

    typedef _Container Container;

    typedef _Item Item;

    /// \brief Exception which can be called from \e clear() and 

    /// \e erase().

    ///

    /// From the \e clear() and \e erase() function only this

    /// exception is allowed to throw. The exception immediatly

    /// detaches the current observer from the notifier. Because the

    /// \e clear() and \e erase() should not throw other exceptions

    /// it can be used to invalidate the observer.

    struct ImmediateDetach {};

    /// \brief ObserverBase is the base class for the observers.

    ///

    /// ObserverBase is the abstract base class for the observers.

    /// It will be notified about an item was inserted into or

    /// erased from the graph.

    ///

    /// The observer interface contains some pure virtual functions

    /// to override. The add() and erase() functions are

    /// to notify the oberver when one item is added or

    /// erased.

    ///

    /// The build() and clear() members are to notify the observer

    /// about the container is built from an empty container or

    /// is cleared to an empty container. 

    class ObserverBase {

    protected:

      typedef AlterationNotifier Notifier;

      friend class AlterationNotifier;

      /// \brief Default constructor.

      ///

      /// Default constructor for ObserverBase.

      /// 

      ObserverBase() : _notifier(0) {}

      /// \brief Constructor which attach the observer into notifier.

      ///

      /// Constructor which attach the observer into notifier.

      ObserverBase(AlterationNotifier& nf) {

        attach(nf);

      }

      /// \brief Constructor which attach the obserever to the same notifier.

      ///

      /// Constructor which attach the obserever to the same notifier as

      /// the other observer is attached to. 

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

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

#ifndef LEMON_BEZIER_H

#define LEMON_BEZIER_H

///\ingroup misc

///\file

///\brief Classes to compute with Bezier curves.

///

///Up to now this file is used internally by \ref graph_to_eps.h

#include<lemon/dim2.h>

namespace lemon {

  namespace dim2 {

class BezierBase {

public:

  typedef Point<double> Point;

protected:

  static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;}

};

class Bezier1 : public BezierBase

{

public:

  Point p1,p2;

  Bezier1() {}

  Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}

  Point operator()(double t) const

  {

    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);

#include <algorithm>

#include <lemon/bits/traits.h>

#include <lemon/bits/utility.h>

#include <lemon/bits/alteration_notifier.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

///\ingroup graphbits

///

///\file

///\brief Vector based graph maps.

namespace lemon {

  /// \ingroup graphbits

  ///

  /// \brief Graph map based on the std::vector storage.

  ///

  /// The VectorMap template class is graph map structure what

  /// automatically updates the map when a key is added to or erased from

  /// the map. This map type uses the std::vector to store the values.

  ///

  template <typename _Graph, typename _Item, typename _Value>

  class VectorMap 

    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

  private:

    /// The container type of the map.

    typedef std::vector<_Value> Container;	

  public:

    /// The graph type of the map. 

    typedef _Graph Graph;

    /// The item type of the map.

    typedef _Item Item;

    /// The reference map tag.

    typedef True ReferenceMapTag;

    /// The key type of the map.

    typedef _Item Key;

    /// The value type of the map.

    typedef _Value Value;

    /// The notifier type.

    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

#ifndef LEMON_COLOR_H

#define LEMON_COLOR_H

#include<vector>

#include<lemon/math.h>

#include<lemon/maps.h>

///\ingroup misc

///\file

///\brief Tools to manage RGB colors.

namespace lemon {

  /// \addtogroup misc

  /// @{

  ///Data structure representing RGB colors.

  ///Data structure representing RGB colors.

  class Color

  {

    double _r,_g,_b;

  public:

    ///Default constructor

    Color() {}

    ///Constructor

    Color(double r,double g,double b) :_r(r),_g(g),_b(b) {};

    ///Set the red component

    double & red() {return _r;}

    ///Return the red component

    const double & red() const {return _r;}

    ///Set the green component

    double & green() {return _g;}

///\ingroup concept

///\file

///\brief Classes for representing paths in digraphs.

///

///\todo Iterators have obsolete style

#ifndef LEMON_CONCEPT_PATH_H

#define LEMON_CONCEPT_PATH_H

#include <lemon/bits/invalid.h>

#include <lemon/bits/utility.h>

#include <lemon/concept_check.h>

namespace lemon {

  namespace concepts {

    /// \addtogroup concept

    /// @{

    /// \brief A skeleton structure for representing directed paths in

    /// a digraph.

    ///

    /// A skeleton structure for representing directed paths in a

    /// digraph.  

    ///

    /// In a sense, the path can be treated as a list of arcs. The

    /// lemon path type stores just this list. As a consequence it

    /// cannot enumerate the nodes in the path and the zero length

    /// paths cannot store the source.

    ///

    template <typename _Digraph>

    class Path {

    public:

      /// Type of the underlying digraph.

      typedef _Digraph Digraph;

      /// Arc type of the underlying digraph.

      typedef typename Digraph::Arc Arc;

      class ArcIt;

      /// \brief Default constructor

      Path() {}

      /// \brief Template constructor

      template <typename CPath>

      Path(const CPath& cpath) {}

        }

        _Path& p;

      };

    }

    /// \brief A skeleton structure for path dumpers.

    ///

    /// A skeleton structure for path dumpers. The path dumpers are

    /// the generalization of the paths. The path dumpers can

    /// enumerate the arcs of the path wheter in forward or in

    /// backward order.  In most time these classes are not used

    /// directly rather it used to assign a dumped class to a real

    /// path type.

    ///

    /// The main purpose of this concept is that the shortest path

    /// algorithms can enumerate easily the arcs in reverse order.

    /// If we would like to give back a real path from these

    /// algorithms then we should create a temporarly path object. In

    /// Lemon such algorithms gives back a path dumper what can

    /// assigned to a real path and the dumpers can be implemented as

    /// an adaptor class to the predecessor map.

    ///

    /// The paths can be constructed from any path type by a

    /// template constructor or a template assignment operator.

    /// 

    template <typename _Digraph>

    class PathDumper {

    public:

      /// Type of the underlying digraph.

      typedef _Digraph Digraph;

      /// Arc type of the underlying digraph.

      typedef typename Digraph::Arc Arc;

      /// Length of the path ie. the number of arcs in the path.

      int length() const { return 0;}

      /// Returns whether the path is empty.

      bool empty() const { return true;}

      /// \brief Forward or reverse dumping

      ///

      /// If the RevPathTag is defined and true then reverse dumping

      /// is provided in the path dumper. In this case instead of the

      /// ArcIt the RevArcIt iterator should be implemented in the

 */

#ifndef LEMON_DFS_H

#define LEMON_DFS_H

///\ingroup search

///\file

///\brief Dfs algorithm.

#include <lemon/list_graph.h>

#include <lemon/graph_utils.h>

#include <lemon/bits/path_dump.h>

#include <lemon/bits/invalid.h>

#include <lemon/error.h>

#include <lemon/maps.h>

#include <lemon/concept_check.h>

namespace lemon {

  ///Default traits class of Dfs class.

  ///Default traits class of Dfs class.

  template<class GR>

  struct DfsDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

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

    ///arcs of the %DFS paths.

    /// 

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

    ///arcs of the %DFS paths.

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

    ///

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

    ///Instantiates a PredMap.

    ///This function instantiates a \ref PredMap. 

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

    ///\todo The digraph alone may be insufficient to initialize

    static PredMap *createPredMap(const GR &G) 

    {

      return new PredMap(G);

    }

    ///The type of the map that indicates which nodes are processed.

    {

      return new ReachedMap(G);

    }

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

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

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

    ///

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap. 

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

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

  ///%DFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %DFS algorithm.

  ///

  ///\ref ListDigraph. The value of GR is not used directly by Dfs, it

  ///is only passed to \ref DfsDefaultTraits.

  ///The default traits class is

  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".

  ///See \ref DfsDefaultTraits for the documentation of

  ///a Dfs traits class.

#ifdef DOXYGEN

  template <typename GR,

	    typename TR>

#else

  template <typename GR=ListDigraph,

	    typename TR=DfsDefaultTraits<GR> >

#endif

  class Dfs {

  public:

    /**

     * \brief \ref Exception for uninitialized parameters.

     *

     * This error represents problems in the initialization

     * of the parameters of the algorithms.

     */

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw() {

	return "lemon::Dfs::UninitializedParameter";

      }

    };

    typedef TR Traits;

    ///The type of the underlying digraph.

    ///Returns a reference to the %DFS arc-tree map.

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

    ///%DFS tree.

    ///\pre Either \ref run() or \ref init()

    ///must be called before using this function.

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

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

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

    ///\warning The source nodes are inditated as unreachable.

    ///\pre Either \ref run() or \ref start()

    ///must be called before using this function.

    ///

    bool reached(Node v) { return (*_reached)[v]; }

    ///@}

  };

  ///Default traits class of Dfs function.

  ///Default traits class of Dfs function.

  template<class GR>

  struct DfsWizardDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

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

    ///arcs of the %DFS paths.

    /// 

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

    ///arcs of the %DFS paths.

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

    ///

    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;

    ///Instantiates a PredMap.

    ///This function instantiates a \ref PredMap. 

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

    ///\todo The digraph alone may be insufficient to initialize

#ifdef DOXYGEN

    static PredMap *createPredMap(const GR &g) 

#else

    static PredMap *createPredMap(const GR &) 

#endif

    {

    void start(const Node&) {}

    void stop(const Node&) {}

    template <typename _Visitor>

    struct Constraints {

      void constraints() {

	Arc arc;

	Node node;

	visitor.discover(arc);

	visitor.reach(node);

	visitor.backtrack(arc);

	visitor.leave(node);

	visitor.examine(arc);

	visitor.start(node);

	visitor.stop(arc);

      }

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of DfsVisit class.

  ///

  /// Default traits class of DfsVisit class.

  template<class _Digraph>

  struct DfsVisitDefaultTraits {

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

    typedef _Digraph Digraph;

    /// \brief The type of the map that indicates which nodes are reached.

    /// 

    /// The type of the map that indicates which nodes are reached.

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

    /// \todo named parameter to set this type, function to read and write.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap. 

    /// \param digraph is the digraph, to which

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// %DFS Visit algorithm class.

  /// \ingroup search

  /// This class provides an efficient implementation of the %DFS algorithm

  /// with visitor interface.

  ///

  /// The %DfsVisit class provides an alternative interface to the Dfs

  /// class. It works with callback mechanism, the DfsVisit object calls

  /// on every dfs event the \c Visitor class member functions. 

  ///

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

  /// is only passed to \ref DfsDefaultTraits.

  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which

  /// does not observe the Dfs events. If you want to observe the dfs

  /// events you should implement your own Visitor class.

  /// algorithm. The default traits class is

  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".

  /// See \ref DfsVisitDefaultTraits for the documentation of

  /// a Dfs visit traits class.

  ///

  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

	    typename _Visitor = DfsVisitor<_Digraph>,

	    typename _Traits = DfsDefaultTraits<_Digraph> >

#endif

  class DfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    ///

    /// This error represents problems in the initialization

    /// of the parameters of the algorithms.

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw() 

      {

  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.

  ///  

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

  /// used in the Dijkstra algorithm for widest path computation.

  template <typename Value>

  struct DijkstraWidestPathOperationTraits {

    /// \brief Gives back the maximum value of the type.

    static Value zero() {

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

    }

    /// \brief Gives back the minimum of the given two elements.

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

      return std::min(left, right);

    }

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

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

      return left < right;

    }

  };

  ///Default traits class of Dijkstra class.

  ///Default traits class of Dijkstra class.

  template<class GR, class LM>

  struct DijkstraDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

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

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

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

    typedef LM LengthMap;

    //The type of the length of the arcs.

    typedef typename LM::Value Value;

    /// Operation traits for Dijkstra algorithm.

    /// It defines the used operation by the algorithm.

    /// \see DijkstraDefaultOperationTraits

    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;

    /// The cross reference type used by heap.

    /// The cross reference type used by heap.

    /// Usually it is \c Digraph::NodeMap<int>.

    typedef typename Digraph::template NodeMap<int> HeapCrossRef;

    ///Instantiates a HeapCrossRef.

    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap. 

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

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

  ///%Dijkstra algorithm class.

  /// \ingroup shortest_path

  ///This class provides an efficient implementation of %Dijkstra algorithm.

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

  ///\ref concepts::ReadMap "ReadMap",

  ///so it is easy to change it to any kind of length.

  ///

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

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

  ///

  ///It is also possible to change the underlying priority heap.

  ///

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

  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.

  ///arcs. It is read once for each arc, so the map may involve in

  ///relatively time consuming process to compute the arc length if

  ///it is necessary. The default map type is \ref

  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value

  ///of LM is not used directly by Dijkstra, it is only passed to \ref

  ///various data types used by the algorithm.  The default traits

  ///class is \ref DijkstraDefaultTraits

  ///"DijkstraDefaultTraits<GR,LM>".  See \ref

  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits

  ///class.

#ifdef DOXYGEN

  template <typename GR, typename LM, typename TR>

#else

  template <typename GR=ListDigraph,

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

	    typename TR=DijkstraDefaultTraits<GR,LM> >

#endif

  class Dijkstra {

  public:

    /**

     * \brief \ref Exception for uninitialized parameters.

     *

     * This error represents problems in the initialization

     * of the parameters of the algorithms.

     */

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw() {

	return "lemon::Dijkstra::UninitializedParameter";

      }

    };

    typedef TR Traits;

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

    ///\warning The source nodes are inditated as unreached.

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

    ///

    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }

    ///Checks if a node is processed.

    ///Returns \c true if \c v is processed, i.e. the shortest

    ///path to \c v has already found.

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

    ///

    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }

    ///@}

  };