Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 1910)
+++ lemon/Makefile.am	(revision 1912)
@@ -31,8 +31,10 @@
 	dijkstra.h \
 	dimacs.h \
+	dag_shortest_path.h \
 	edge_set.h \
 	error.h \
 	fib_heap.h \
 	floyd_warshall.h \
+	fredman_tarjan.h \
 	full_graph.h \
 	grid_graph.h \
@@ -60,4 +62,5 @@
 	preflow.h \
 	path.h \
+	prim.h \
 	radix_heap.h \
 	radix_sort.h \
Index: lemon/dag_shortest_path.h
===================================================================
--- lemon/dag_shortest_path.h	(revision 1912)
+++ lemon/dag_shortest_path.h	(revision 1912)
@@ -0,0 +1,1082 @@
+/* -*- C++ -*-
+ * lemon/dag_shortest_path.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 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_DAG_SHORTEST_PATH_H
+#define LEMON_DAG_SHORTEST_PATH_H
+
+///\ingroup flowalgs
+/// \file
+/// \brief DagShortestPath algorithm.
+///
+
+#include <lemon/list_graph.h>
+#include <lemon/invalid.h>
+#include <lemon/error.h>
+#include <lemon/maps.h>
+#include <lemon/topology.h>
+
+#include <limits>
+
+namespace lemon {
+
+  /// \brief Default OperationTraits for the DagShortestPath algorithm class.
+  ///  
+  /// It defines all computational operations and constants which are
+  /// used in the dag shortest path algorithm. The default implementation
+  /// is based on the numeric_limits class. If the numeric type does not
+  /// have infinity value then the maximum value is used as extremal
+  /// infinity value.
+  template <
+    typename Value, 
+    bool has_infinity = std::numeric_limits<Value>::has_infinity>
+  struct DagShortestPathDefaultOperationTraits {
+    /// \brief Gives back the zero value of the type.
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    /// \brief Gives back the positive infinity value of the type.
+    static Value infinity() {
+      return std::numeric_limits<Value>::infinity();
+    }
+    /// \brief Gives back the sum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return 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;
+    }
+  };
+
+  template <typename Value>
+  struct DagShortestPathDefaultOperationTraits<Value, false> {
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    static Value infinity() {
+      return std::numeric_limits<Value>::max();
+    }
+    static Value plus(const Value& left, const Value& right) {
+      if (left == infinity() || right == infinity()) return infinity();
+      return left + right;
+    }
+    static bool less(const Value& left, const Value& right) {
+      return left < right;
+    }
+  };
+  
+  /// \brief Default traits class of DagShortestPath class.
+  ///
+  /// Default traits class of DagShortestPath class.
+  /// \param _Graph Graph type.
+  /// \param _LegthMap Type of length map.
+  template<class _Graph, class _LengthMap>
+  struct DagShortestPathDefaultTraits {
+    /// The graph type the algorithm runs on. 
+    typedef _Graph Graph;
+
+    /// \brief The type of the map that stores the edge lengths.
+    ///
+    /// The type of the map that stores the edge lengths.
+    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
+    typedef _LengthMap LengthMap;
+
+    // The type of the length of the edges.
+    typedef typename _LengthMap::Value Value;
+
+    /// \brief Operation traits for dag shortest path algorithm.
+    ///
+    /// It defines the infinity type on the given Value type
+    /// and the used operation.
+    /// \see DagShortestPathDefaultOperationTraits
+    typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
+ 
+    /// \brief The type of the map that stores the last edges of the 
+    /// shortest paths.
+    /// 
+    /// The type of the map that stores the last
+    /// edges of the shortest paths.
+    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
+
+    /// \brief Instantiates a PredMap.
+    /// 
+    /// This function instantiates a \ref PredMap. 
+    /// \param G is the graph, to which we would like to define the PredMap.
+    /// \todo The graph alone may be insufficient for the initialization
+    static PredMap *createPredMap(const _Graph& graph) {
+      return new PredMap(graph);
+    }
+
+    /// \brief 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 concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<typename _LengthMap::Value> 
+    DistMap;
+
+    /// \brief Instantiates a DistMap.
+    ///
+    /// This function instantiates a \ref DistMap. 
+    /// \param G is the graph, to which we would like to define the 
+    /// \ref DistMap
+    static DistMap *createDistMap(const _Graph& graph) {
+      return new DistMap(graph);
+    }
+
+  };
+  
+  /// \brief Inverse OperationTraits for the DagShortestPath algorithm class.
+  /// 
+  /// It defines all computational operations and constants which are
+  /// used in the dag shortest path algorithm. It is the inverse of
+  /// \ref DagShortestPathDefaultOperationTraits, so it can be used to
+  /// calculate the longest path. The default implementation
+  /// is based on the numeric_limits class. If the numeric type does not
+  /// have infinity value then the minimum value is used as extremal
+  /// infinity value.
+  template <
+    typename Value, 
+    bool has_infinity = std::numeric_limits<Value>::has_infinity>
+  struct DagLongestPathOperationTraits {
+    /// \brief Gives back the zero value of the type.
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    /// \brief Gives back the negative infinity value of the type.
+    static Value infinity() {
+      return -(std::numeric_limits<Value>::infinity());
+    }
+    /// \brief Gives back the sum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return 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;
+    }
+  };
+
+  template <typename Value>
+  struct DagLongestPathOperationTraits<Value, false> {
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    static Value infinity() {
+      return std::numeric_limits<Value>::min();
+    }
+    static Value plus(const Value& left, const Value& right) {
+      if (left == infinity() || right == infinity()) return infinity();
+      return left + right;
+    }
+    static bool less(const Value& left, const Value& right) {
+      return left > right;
+    }
+  };
+
+  /// \brief Inverse traits class of DagShortestPath class.
+  ///
+  /// Inverse traits class of DagShortestPath class.
+  /// \param _Graph Graph type.
+  /// \param _LegthMap Type of length map.
+  template<class _Graph, class _LengthMap>
+  struct DagLongestPathTraits {
+    /// The graph type the algorithm runs on. 
+    typedef _Graph Graph;
+
+    /// \brief The type of the map that stores the edge lengths.
+    ///
+    /// The type of the map that stores the edge lengths.
+    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
+    typedef _LengthMap LengthMap;
+
+    // The type of the length of the edges.
+    typedef typename _LengthMap::Value Value;
+
+    /// \brief Inverse operation traits for dag shortest path algorithm.
+    ///
+    /// It defines the infinity type on the given Value type
+    /// and the used operation.
+    /// \see DagLongestPathOperationTraits
+    typedef DagLongestPathOperationTraits<Value> OperationTraits;
+ 
+    /// \brief The type of the map that stores the last edges of the 
+    /// longest paths.
+    /// 
+    /// The type of the map that stores the last
+    /// edges of the longest paths.
+    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
+
+    /// \brief Instantiates a PredMap.
+    /// 
+    /// This function instantiates a \ref PredMap. 
+    /// \param G is the graph, to which we would like to define the PredMap.
+    /// \todo The graph alone may be insufficient for the initialization
+    static PredMap *createPredMap(const _Graph& graph) {
+      return new PredMap(graph);
+    }
+
+    /// \brief 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 concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<typename _LengthMap::Value> 
+    DistMap;
+
+    /// \brief Instantiates a DistMap.
+    ///
+    /// This function instantiates a \ref DistMap. 
+    /// \param G is the graph, to which we would like to define the 
+    /// \ref DistMap
+    static DistMap *createDistMap(const _Graph& graph) {
+      return new DistMap(graph);
+    }
+
+  };
+  
+
+  /// \brief %DagShortestPath algorithm class.
+  ///
+  /// \ingroup flowalgs
+  /// This class provides an efficient implementation of a Dag sortest path
+  /// searching algorithm. The edge lengths are passed to the algorithm
+  /// using a \ref concept::ReadMap "ReadMap", so it is easy to change it
+  /// to any kind of length.
+  ///
+  /// The complexity of the algorithm is O(n + e).
+  ///
+  /// The type of the length is determined by the
+  /// \ref concept::ReadMap::Value "Value" of the length map.
+  ///
+  /// \param _Graph The graph type the algorithm runs on. The default value
+  /// is \ref ListGraph. The value of _Graph is not used directly by
+  /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
+  /// \param _LengthMap This read-only EdgeMap determines the lengths of the
+  /// edges. The default map type is \ref concept::StaticGraph::EdgeMap 
+  /// "Graph::EdgeMap<int>".  The value of _LengthMap is not used directly 
+  /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.  
+  /// \param _Traits Traits class to set various data types used by the 
+  /// algorithm.  The default traits class is \ref DagShortestPathDefaultTraits
+  /// "DagShortestPathDefaultTraits<_Graph,_LengthMap>".  See \ref
+  /// DagShortestPathDefaultTraits for the documentation of a DagShortestPath traits
+  /// class.
+  ///
+  /// \author Balazs Attila Mihaly (based on Balazs Dezso's work)
+
+#ifdef DOXYGEN
+  template <typename _Graph, typename _LengthMap, typename _Traits>
+#else
+  template <typename _Graph=ListGraph,
+	    typename _LengthMap=typename _Graph::template EdgeMap<int>,
+	    typename _Traits=DagShortestPathDefaultTraits<_Graph,_LengthMap> >
+#endif
+  class DagShortestPath {
+  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* exceptionName() const {
+	return "lemon::DagShortestPath::UninitializedParameter";
+      }
+    };
+
+    typedef _Traits Traits;
+    ///The type of the underlying graph.
+    typedef typename _Traits::Graph Graph;
+
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+    /// \brief The type of the length of the edges.
+    typedef typename _Traits::LengthMap::Value Value;
+    /// \brief The type of the map that stores the edge lengths.
+    typedef typename _Traits::LengthMap LengthMap;
+    /// \brief The type of the map that stores the last
+    /// edges 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;
+    /// \brief The Node weight map.
+    typedef typename Graph::NodeMap<Value> WeightMap;
+  private:
+    /// Pointer to the underlying graph
+    const Graph *graph;
+    /// Pointer to the length map
+    const LengthMap *length;
+    ///Pointer to the map of predecessors edges
+    PredMap *_pred;
+    ///Indicates if \ref _pred is locally allocated (\c true) or not
+    bool local_pred;
+    ///Pointer to the map of distances
+    DistMap *_dist;
+    ///Indicates if \ref _dist is locally allocated (\c true) or not
+    bool local_dist;
+    ///Process step counter
+    unsigned int _process_step;
+
+    std::vector<Node> _node_order;
+
+    /// Creates the maps if necessary.
+    void create_maps() {
+      if(!_pred) {
+	local_pred = true;
+	_pred = Traits::createPredMap(*graph);
+      }
+      if(!_dist) {
+	local_dist = true;
+	_dist = Traits::createDistMap(*graph);
+      }
+    }
+    
+  public :
+ 
+    typedef DagShortestPath Create;
+
+    /// \name Named template parameters
+
+    ///@{
+
+    template <class T>
+    struct DefPredMapTraits : public Traits {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Graph&) {
+	throw UninitializedParameter();
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting PredMap 
+    /// type
+    /// \ref named-templ-param "Named parameter" for setting PredMap type
+    ///
+    template <class T>
+    struct DefPredMap {
+      typedef DagShortestPath< Graph, LengthMap, DefPredMapTraits<T> > Create;
+    };
+    
+    template <class T>
+    struct DefDistMapTraits : public Traits {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Graph& graph) {
+	throw UninitializedParameter();
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting DistMap 
+    /// type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting DistMap type
+    ///
+    template <class T>
+    struct DefDistMap 
+      : public DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > {
+      typedef DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > Create;
+    };
+    
+    template <class T>
+    struct DefOperationTraitsTraits : public Traits {
+      typedef T OperationTraits;
+    };
+    
+    /// \brief \ref named-templ-param "Named parameter" for setting 
+    /// OperationTraits type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting OperationTraits
+    /// type
+    template <class T>
+    struct DefOperationTraits
+      : public DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> > {
+      typedef DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> >
+      Create;
+    };
+    
+    ///@}
+
+  protected:
+    
+    DagShortestPath() {}
+
+  public:      
+    
+    /// \brief Constructor.
+    ///
+    /// \param _graph the graph the algorithm will run on.
+    /// \param _length the length map used by the algorithm.
+    DagShortestPath(const Graph& _graph, const LengthMap& _length) :
+      graph(&_graph), length(&_length),
+      _pred(0), local_pred(false),
+      _dist(0), local_dist(false){}
+
+    /// \brief Constructor with node weight map.
+    ///
+    /// \param _graph the graph the algorithm will run on.
+    /// \param _length the length map used by the algorithm.
+    /// The NodeMap _length will be used as the weight map.
+    /// Each edge will have the weight of its target node.
+    DagShortestPath(const Graph& _graph, const WeightMap& _length) :
+      graph(&_graph),
+      _pred(0), local_pred(false),
+      _dist(0), local_dist(false){
+      length=new LengthMap(_graph);
+      _dist=new DistMap(_graph);
+      for(EdgeIt eit(_graph);eit!=INVALID;++eit)
+	(const_cast<LengthMap*>(length))->set(eit,_length[_graph.target(eit)]);
+      }
+
+    ///Destructor.
+    ~DagShortestPath() {
+      if(local_pred) delete _pred;
+      if(local_dist) delete _dist;
+    }
+
+    /// \brief Sets the length map.
+    ///
+    /// Sets the length map.
+    /// \return \c (*this)
+    DagShortestPath &lengthMap(const LengthMap &m) {
+      length = &m;
+      return *this;
+    }
+
+    /// \brief Sets the map storing the predecessor edges.
+    ///
+    /// Sets the map storing the predecessor edges.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return \c (*this)
+    DagShortestPath &predMap(PredMap &m) {
+      if(local_pred) {
+	delete _pred;
+	local_pred=false;
+      }
+      _pred = &m;
+      return *this;
+    }
+
+    /// \brief Sets the map storing the distances calculated by the algorithm.
+    ///
+    /// Sets the map storing the distances calculated by the algorithm.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return \c (*this)
+    DagShortestPath &distMap(DistMap &m) {
+      if(local_dist) {
+	delete _dist;
+	local_dist=false;
+      }
+      _dist = &m;
+      return *this;
+    }
+
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...)
+    /// \n
+    /// If you need more control on the execution,
+    /// first you must call \ref init(...), then you can add several source
+    /// nodes with \ref addSource().
+    /// Finally \ref start() will perform the actual path computation.
+    /// Some functions have an alternative form (\ref checkedInit(...),
+    /// \ref checkedRun(...)) which also verifies if the graph given in the
+    /// constructor is a dag.
+
+    ///@{
+
+    /// \brief Initializes the internal data structures.
+    ///
+    /// Initializes the internal data structures.
+    void init(const Value value = OperationTraits::infinity()) {
+      typedef typename Graph::template NodeMap<int> NodeOrderMap;
+      _process_step=0;
+      NodeOrderMap node_order(*graph);
+      topologicalSort(*graph,node_order);
+      _node_order.resize(countNodes(*graph),INVALID);
+      create_maps();
+      for (NodeIt it(*graph); it != INVALID; ++it) {
+        _node_order[node_order[it]]=it;
+        _pred->set(it, INVALID);
+        _dist->set(it, value);
+      }
+    }
+
+    /// \brief Initializes the internal data structures
+    /// with a given topological sort (NodeMap).
+    ///
+    /// Initializes the internal data structures
+    /// with a given topological sort (NodeMap).
+    void init(const typename Graph::template NodeMap<int>& node_order,
+         const Value value = OperationTraits::infinity()) {
+      _process_step=0;
+      _node_order.resize(countNodes(*graph),INVALID);
+      create_maps();
+      for (NodeIt it(*graph); it != INVALID; ++it) {
+        _node_order[node_order[it]]=it;
+        _pred->set(it, INVALID);
+        _dist->set(it, value);
+      }
+    }
+
+    /// \brief Initializes the internal data structures
+    /// with a given topological sort (std::vector).
+    ///
+    /// Initializes the internal data structures
+    /// with a given topological sort (std::vector).
+    void init(const std::vector<Node>& node_order,
+        const Value value = OperationTraits::infinity()) {
+      _process_step=0;
+      _node_order=node_order;
+      create_maps();
+      for (NodeIt it(*graph); it != INVALID; ++it) {
+        _pred->set(it, INVALID);
+        _dist->set(it, value);
+      }
+    }
+
+    /// \brief Initializes the internal data structures. It also checks if the graph is dag.
+    ///
+    /// Initializes the internal data structures. It also checks if the graph is dag.
+    /// \return true if the graph (given in the constructor) is dag, false otherwise.
+    bool checkedInit(const Value value = OperationTraits::infinity()) {
+      typedef typename Graph::template NodeMap<int> NodeOrderMap;
+      NodeOrderMap node_order(*graph);
+      if(!checkedTopologicalSort(*graph,node_order))return false;
+      init(node_order,value);
+      return true;
+    }
+
+    /// \brief Initializes the internal data structures with a given
+    /// topological sort (NodeMap). It also checks if the graph is dag.
+    ///
+    /// Initializes the internal data structures with a given
+    /// topological sort (NodeMap). It also checks if the graph is dag.
+    /// \return true if the graph (given in the constructor) is dag, false otherwise.
+    bool checkedInit(const typename Graph::template NodeMap<int>& node_order, 
+                     const Value value = OperationTraits::infinity()) {
+      for(NodeIt it(*graph);it!=INVALID;++it){
+        for(OutEdgeIt oeit(*graph,it);oeit!=INVALID;++oeit){
+          if(node_order[graph->target(oeit)]<node_order[it])return false;
+        }
+      }
+      init(node_order,value);
+      return true;
+    }
+
+    /// \brief Initializes the internal data structures with a given
+    /// topological sort (std::vector). It also checks if the graph is dag.
+    ///
+    /// Initializes the internal data structures with a given
+    /// topological sort (std::vector). It also checks if the graph is dag.
+    /// \return true if the graph (given in the constructor) is dag, false otherwise.
+    bool checkedInit(const std::vector<Node>& node_order, 
+                     const Value value = OperationTraits::infinity()) {
+      typedef typename Graph::template NodeMap<bool> BoolNodeMap;
+      BoolNodeMap _processed(*graph,false);
+      for(unsigned int i=0;i<_node_order.size();++i){
+        _processed[node_order[i]]=true;
+        for(OutEdgeIt oeit(*graph,node_order[i]);oeit!=INVALID;++oeit){
+          if(_processed[graph->target(oeit)])return false;
+        }
+      }
+      init(node_order,value);
+      return true;
+    }
+
+    /// \brief Adds a new source node.
+    ///
+    /// The optional second parameter is the initial distance of the node.
+    /// It just sets the distance of the node to the given value.
+    void addSource(Node source, Value dst = OperationTraits::zero()) {
+      if((*_dist)[source] != dst){
+        _dist->set(source, dst);
+      }
+    }
+
+    /// \brief Executes one step from the dag shortest path algorithm.
+    ///
+    /// If the algoritm calculated the distances in the previous step 
+    /// strictly for all at most k length paths then it will calculate the 
+    /// distances strictly for all at most k + 1 length paths. With k
+    /// iteration this function calculates the at most k length paths.
+    ///\pre the queue is not empty
+    ///\return the currently processed node
+    Node processNextNode() {
+      if(reached(_node_order[_process_step])){
+        for (OutEdgeIt it(*graph, _node_order[_process_step]); it != INVALID; ++it) {
+	  Node target = graph->target(it);
+	  Value relaxed =
+	    OperationTraits::plus((*_dist)[_node_order[_process_step]], (*length)[it]);
+	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
+	    _pred->set(target, it);
+	    _dist->set(target, relaxed);
+	  }
+        }
+      }
+      ++_process_step;
+      return _node_order[_process_step-1];
+    }
+
+    ///\brief Returns \c false if there are nodes
+    ///to be processed in the queue
+    ///
+    ///Returns \c false if there are nodes
+    ///to be processed in the queue
+    bool emptyQueue() { return _node_order.size()-1==_process_step; }
+
+    ///\brief Returns the number of the nodes to be processed.
+    ///
+    ///Returns the number of the nodes to be processed in the queue.
+    int queueSize() { return _node_order.size()-1-_process_step; }
+
+    /// \brief Executes the algorithm.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    ///
+    /// This method runs the %DagShortestPath algorithm from the root node(s)
+    /// in order to compute the shortest path to each node. The algorithm 
+    /// computes 
+    /// - The shortest path tree.
+    /// - The distance of each node from the root(s).
+    void start() {
+      while(!emptyQueue()) {
+	processNextNode();
+      }
+    }
+
+    /// \brief Runs %DagShortestPath algorithm from node \c s.
+    ///    
+    /// This method runs the %DagShortestPath algorithm from a root node \c s
+    /// in order to compute the shortest path to each node. The algorithm 
+    /// computes
+    /// - The shortest path tree.
+    /// - The distance of each node from the root.
+    ///
+    /// \note d.run(s) is just a shortcut of the following code.
+    /// \code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start();
+    /// \endcode
+    void run(Node s) {
+      init();
+      addSource(s);
+      start();
+    }
+    
+    /// \brief Runs %DagShortestPath algorithm from node \c s.
+    /// It also checks if the graph is a dag.
+    ///    
+    /// This method runs the %DagShortestPath algorithm from a root node \c s
+    /// in order to compute the shortest path to each node. The algorithm 
+    /// computes
+    /// - The shortest path tree.
+    /// - The distance of each node from the root.
+    /// The algorithm checks if the graph given int the constructor is a dag.
+    bool checkedRun(Node s) {
+      if(!checkedInit())return false;
+      addSource(s);
+      start();
+      return true;
+    }
+    
+    ///@}
+
+    /// \name Query Functions
+    /// The result of the %DagShortestPath algorithm can be obtained using these
+    /// functions.\n
+    /// Before the use of these functions,
+    /// either run() or start() must be called.
+    
+    ///@{
+
+    /// \brief Copies the shortest path to \c t into \c p
+    ///    
+    /// This function copies the shortest path to \c t into \c p.
+    /// If it \c t is a source itself or unreachable, then it does not
+    /// alter \c p.
+    ///
+    /// \return Returns \c true if a path to \c t was actually copied to \c p,
+    /// \c false otherwise.
+    /// \sa DirPath
+    template <typename Path>
+    bool getPath(Path &p, Node t) {
+      if(reached(t)) {
+	p.clear();
+	typename Path::Builder b(p);
+	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
+	  b.pushFront(predEdge(t));
+	b.commit();
+	return true;
+      }
+      return false;
+    }
+	  
+    /// \brief The distance of a node from the root.
+    ///
+    /// Returns the distance of a node from the root.
+    /// \pre \ref run() must be called before using this function.
+    /// \warning If node \c v in unreachable from the root the return value
+    /// of this funcion is undefined.
+    Value dist(Node v) const { return (*_dist)[v]; }
+
+    /// \brief Returns the 'previous edge' of the shortest path tree.
+    ///
+    /// For a node \c v it returns the 'previous edge' of the shortest path 
+    /// tree, i.e. it returns the last edge of a shortest path from the root 
+    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or 
+    /// if \c v=s. The shortest path tree used here is equal to the shortest 
+    /// path tree used in \ref predNode(). 
+    /// \pre \ref run() must be called before using
+    /// this function.
+    Edge predEdge(Node v) const { return (*_pred)[v]; }
+
+    /// \brief Returns the 'previous node' of the shortest path tree.
+    ///
+    /// 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 
+    /// the root to \c /v. It is INVALID if \c v is unreachable from the root 
+    /// or if \c v=s. The shortest path tree used here is equal to the 
+    /// shortest path tree used in \ref predEdge().  \pre \ref run() must be 
+    /// called before using this function.
+    Node predNode(Node v) const { 
+      return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]); 
+    }
+    
+    /// \brief Returns a reference to the NodeMap of distances.
+    ///
+    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
+    /// be called before using this function.
+    const DistMap &distMap() const { return *_dist;}
+ 
+    /// \brief Returns a reference to the shortest path tree map.
+    ///
+    /// Returns a reference to the NodeMap of the edges of the
+    /// shortest path tree.
+    /// \pre \ref run() must be called before using this function.
+    const PredMap &predMap() const { return *_pred; }
+ 
+    /// \brief Checks if a node is reachable from the root.
+    ///
+    /// Returns \c true if \c v is reachable from the root.
+    /// \pre \ref run() must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
+    
+    ///@}
+  };
+ 
+  /// \brief Default traits class of DagShortestPath function.
+  ///
+  /// Default traits class of DagShortestPath function.
+  /// \param _Graph Graph type.
+  /// \param _LengthMap Type of length map.
+  template <typename _Graph, typename _LengthMap>
+  struct DagShortestPathWizardDefaultTraits {
+    /// \brief The graph type the algorithm runs on. 
+    typedef _Graph Graph;
+
+    /// \brief The type of the map that stores the edge lengths.
+    ///
+    /// The type of the map that stores the edge lengths.
+    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
+    typedef _LengthMap LengthMap;
+
+    /// \brief The value type of the length map.
+    typedef typename _LengthMap::Value Value;
+
+    /// \brief Operation traits for dag shortest path algorithm.
+    ///
+    /// It defines the infinity type on the given Value type
+    /// and the used operation.
+    /// \see DagShortestPathDefaultOperationTraits
+    typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
+
+    /// \brief The type of the map that stores the last
+    /// edges of the shortest paths.
+    /// 
+    /// The type of the map that stores the last
+    /// edges of the shortest paths.
+    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
+    typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
+
+    /// \brief Instantiates a PredMap.
+    /// 
+    /// This function instantiates a \ref PredMap. 
+    static PredMap *createPredMap(const _Graph &) {
+      return new PredMap();
+    }
+    /// \brief 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 concept::WriteMap "WriteMap" concept.
+    typedef NullMap<typename Graph::Node, Value> DistMap;
+    /// \brief Instantiates a DistMap.
+    ///
+    /// This function instantiates a \ref DistMap. 
+    static DistMap *createDistMap(const _Graph &) {
+      return new DistMap();
+    }
+  };
+  
+  /// \brief Default traits used by \ref DagShortestPathWizard
+  ///
+  /// To make it easier to use DagShortestPath algorithm
+  /// we have created a wizard class.
+  /// This \ref DagShortestPathWizard class needs default traits,
+  /// as well as the \ref DagShortestPath class.
+  /// The \ref DagShortestPathWizardBase is a class to be the default traits of the
+  /// \ref DagShortestPathWizard class.
+  /// \todo More named parameters are required...
+  template<class _Graph,class _LengthMap>
+  class DagShortestPathWizardBase 
+    : public DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> {
+
+    typedef DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> Base;
+  protected:
+    /// Type of the nodes in the graph.
+    typedef typename Base::Graph::Node Node;
+
+    /// Pointer to the underlying graph.
+    void *_graph;
+    /// Pointer to the length map
+    void *_length;
+    ///Pointer to the map of predecessors edges.
+    void *_pred;
+    ///Pointer to the map of distances.
+    void *_dist;
+    ///Pointer to the source node.
+    Node _source;
+
+    public:
+    /// Constructor.
+    
+    /// This constructor does not require parameters, therefore it initiates
+    /// all of the attributes to default values (0, INVALID).
+    DagShortestPathWizardBase() : _graph(0), _length(0), _pred(0),
+			   _dist(0), _source(INVALID) {}
+
+    /// Constructor.
+    
+    /// This constructor requires some parameters,
+    /// listed in the parameters list.
+    /// Others are initiated to 0.
+    /// \param graph is the initial value of  \ref _graph
+    /// \param length is the initial value of  \ref _length
+    /// \param source is the initial value of  \ref _source
+    DagShortestPathWizardBase(const _Graph& graph, 
+			  const _LengthMap& length, 
+			  Node source = INVALID) :
+      _graph((void *)&graph), _length((void *)&length), _pred(0),
+      _dist(0), _source(source) {}
+
+  };
+  
+  /// A class to make the usage of DagShortestPath algorithm easier
+
+  /// This class is created to make it easier to use DagShortestPath algorithm.
+  /// It uses the functions and features of the plain \ref DagShortestPath,
+  /// but it is much simpler to use it.
+  ///
+  /// Simplicity means that the way to change the types defined
+  /// in the traits class is based on functions that returns the new class
+  /// and not on templatable built-in classes.
+  /// When using the plain \ref DagShortestPath
+  /// the new class with the modified type comes from
+  /// the original class by using the ::
+  /// operator. In the case of \ref DagShortestPathWizard only
+  /// a function have to be called and it will
+  /// return the needed class.
+  ///
+  /// It does not have own \ref run method. When its \ref run method is called
+  /// it initiates a plain \ref DagShortestPath class, and calls the \ref 
+  /// DagShortestPath::run() method of it.
+  template<class _Traits>
+  class DagShortestPathWizard : public _Traits {
+    typedef _Traits Base;
+
+    ///The type of the underlying graph.
+    typedef typename _Traits::Graph Graph;
+
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt EdgeIt;
+    
+    ///The type of the map that stores the edge lengths.
+    typedef typename _Traits::LengthMap LengthMap;
+
+    ///The type of the length of the edges.
+    typedef typename LengthMap::Value Value;
+
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    typedef typename _Traits::PredMap PredMap;
+
+    ///The type of the map that stores the dists of the nodes.
+    typedef typename _Traits::DistMap DistMap;
+
+  public:
+    /// Constructor.
+    DagShortestPathWizard() : _Traits() {}
+
+    /// \brief Constructor that requires parameters.
+    ///
+    /// Constructor that requires parameters.
+    /// These parameters will be the default values for the traits class.
+    DagShortestPathWizard(const Graph& graph, const LengthMap& length, 
+		      Node source = INVALID) 
+      : _Traits(graph, length, source) {}
+
+    /// \brief Copy constructor
+    DagShortestPathWizard(const _Traits &b) : _Traits(b) {}
+
+    ~DagShortestPathWizard() {}
+
+    /// \brief Runs DagShortestPath algorithm from a given node.
+    ///    
+    /// Runs DagShortestPath algorithm from a given node.
+    /// The node can be given by the \ref source function.
+    void run() {
+      if(Base::_source == INVALID) throw UninitializedParameter();
+      DagShortestPath<Graph,LengthMap,_Traits> 
+	bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
+      if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
+      if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
+      bf.run(Base::_source);
+    }
+
+    /// \brief Runs DagShortestPath algorithm from the given node.
+    ///
+    /// Runs DagShortestPath algorithm from the given node.
+    /// \param s is the given source.
+    void run(Node source) {
+      Base::_source = source;
+      run();
+    }
+
+    template<class T>
+    struct DefPredMapBase : public Base {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Graph &) { return 0; };
+      DefPredMapBase(const _Traits &b) : _Traits(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    template<class T>
+    DagShortestPathWizard<DefPredMapBase<T> > predMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return DagShortestPathWizard<DefPredMapBase<T> >(*this);
+    }
+    
+    template<class T>
+    struct DefDistMapBase : public Base {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Graph &) { return 0; };
+      DefDistMapBase(const _Traits &b) : _Traits(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    template<class T>
+    DagShortestPathWizard<DefDistMapBase<T> > distMap(const T &t) {
+      Base::_dist=(void *)&t;
+      return DagShortestPathWizard<DefDistMapBase<T> >(*this);
+    }
+
+    template<class T>
+    struct DefOperationTraitsBase : public Base {
+      typedef T OperationTraits;
+      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting OperationTraits type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting OperationTraits type
+    ///
+    template<class T>
+    DagShortestPathWizard<DefOperationTraitsBase<T> > distMap() {
+      return DagShortestPathWizard<DefDistMapBase<T> >(*this);
+    }
+    
+    /// \brief Sets the source node, from which the DagShortestPath algorithm runs.
+    ///
+    /// Sets the source node, from which the DagShortestPath algorithm runs.
+    /// \param s is the source node.
+    DagShortestPathWizard<_Traits>& source(Node source) {
+      Base::_source = source;
+      return *this;
+    }
+    
+  };
+  
+  /// \brief Function type interface for DagShortestPath algorithm.
+  ///
+  /// \ingroup flowalgs
+  /// Function type interface for DagShortestPath algorithm.
+  ///
+  /// This function also has several \ref named-templ-func-param 
+  /// "named parameters", they are declared as the members of class 
+  /// \ref DagShortestPathWizard.
+  /// The following
+  /// example shows how to use these parameters.
+  /// \code
+  /// dagShortestPath(g,length,source).predMap(preds).run();
+  /// \endcode
+  /// \warning Don't forget to put the \ref DagShortestPathWizard::run() "run()"
+  /// to the end of the parameter list.
+  /// \sa DagShortestPathWizard
+  /// \sa DagShortestPath
+  template<class _Graph, class _LengthMap>
+  DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
+  dagShortestPath(const _Graph& graph,
+	      const _LengthMap& length, 
+	      typename _Graph::Node source = INVALID) {
+    return DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
+      (graph, length, source);
+  }
+
+} //END OF NAMESPACE LEMON
+
+#endif
+
Index: lemon/fredman_tarjan.h
===================================================================
--- lemon/fredman_tarjan.h	(revision 1912)
+++ lemon/fredman_tarjan.h	(revision 1912)
@@ -0,0 +1,509 @@
+/* -*- C++ -*-
+ * lemon/fredman_tarjan.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 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_FREDMAN_TARJAN_H
+#define LEMON_FREDMAN_TARJAN_H
+
+///\ingroup spantree
+///\file
+///\brief FredmanTarjan algorithm to compute minimum spanning forest.
+
+#include <limits>
+#include <vector>
+
+#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
+#include <lemon/fib_heap.h>
+#include <lemon/radix_sort.h>
+#include <lemon/invalid.h>
+#include <lemon/error.h>
+#include <lemon/maps.h>
+#include <lemon/traits.h>
+#include <lemon/graph_utils.h>
+
+#include <lemon/concept/ugraph.h>
+
+namespace lemon {
+
+  ///Default traits class of FredmanTarjan class.
+
+  ///Default traits class of FredmanTarjan class.
+  ///\param GR Graph type.
+  ///\param LM Type of cost map.
+  template<class GR, class LM>
+  struct FredmanTarjanDefaultTraits{
+    ///The graph type the algorithm runs on. 
+    typedef GR UGraph;
+    ///The type of the map that stores the edge costs.
+
+    ///The type of the map that stores the edge costs.
+    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
+    typedef LM CostMap;
+    //The type of the cost of the edges.
+    typedef typename LM::Value Value;
+    ///The type of the map that stores whether an edge is in the
+    ///spanning tree or not.
+
+    ///The type of the map that stores whether an edge is in the
+    ///spanning tree or not.
+    ///It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept.
+    ///By default it is a BoolEdgeMap.
+    typedef typename UGraph::template UEdgeMap<bool> TreeMap;
+    ///Instantiates a TreeMap.
+
+    ///This function instantiates a \ref TreeMap.
+    ///\param g is the graph, to which
+    ///we would like to define the \ref TreeMap
+    static TreeMap *createTreeMap(const GR &_graph){
+      return new TreeMap(_graph);
+    }
+  };
+  
+  ///%FredmanTarjan algorithm class to find a minimum spanning tree.
+  
+  /// \ingroup spantree
+  ///This class provides an efficient implementation of %FredmanTarjan algorithm
+  ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs.
+  ///Due to the structure of the algorithm, it has less controll functions than
+  ///Prim.
+  ///
+  ///The running time is O(e*B(e,n)) where e is the number of edges, n is the
+  ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n}
+  ///( log^(i+1) n = log(log^(i)) n )
+  ///
+  ///The edge costs are passed to the algorithm using a
+  ///\ref concept::ReadMap "ReadMap",
+  ///so it is easy to change it to any kind of cost.
+  ///
+  ///The type of the cost is determined by the
+  ///\ref concept::ReadMap::Value "Value" of the cost map.
+  ///
+  ///\param GR The graph type the algorithm runs on. The default value
+  ///is \ref ListUGraph. The value of GR is not used directly by
+  ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits.
+  ///
+  ///\param LM This read-only UEdgeMap determines the costs of the
+  ///edges. It is read once for each edge, so the map may involve in
+  ///relatively time consuming process to compute the edge cost if
+  ///it is necessary. The default map type is \ref
+  ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value
+  ///of LM is not used directly by FredmanTarjan, it is only passed to \ref
+  ///FredmanTarjanDefaultTraits.
+  ///
+  ///\param TR Traits class to set
+  ///various data types used by the algorithm.  The default traits
+  ///class is \ref FredmanTarjanDefaultTraits
+  ///"FredmanTarjanDefaultTraits<GR,LM>".  See \ref
+  ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits
+  ///class.
+  ///
+  ///\author Balazs Attila Mihaly
+
+#ifdef DOXYGEN
+  template <typename GR,
+	    typename LM,
+	    typename TR>
+#else
+  template <typename GR=ListUGraph,
+	    typename LM=typename GR::template UEdgeMap<int>,
+	    typename TR=FredmanTarjanDefaultTraits<GR,LM> >
+#endif
+  class FredmanTarjan {
+  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* exceptionName() const {
+	return "lemon::FredmanTarjan::UninitializedParameter";
+      }
+    };
+
+    typedef GR Graph;
+    typedef TR Traits;
+    ///The type of the underlying graph.
+    typedef typename TR::UGraph UGraph;
+    ///\e
+    typedef typename UGraph::Node Node;
+    ///\e
+    typedef typename UGraph::NodeIt NodeIt;
+    ///\e
+    typedef typename UGraph::UEdge UEdge;
+    ///\e
+    typedef typename UGraph::UEdgeIt UEdgeIt;
+    ///\e
+    typedef typename UGraph::IncEdgeIt IncEdgeIt;
+    
+    ///The type of the cost of the edges.
+    typedef typename TR::CostMap::Value Value;
+    ///The type of the map that stores the edge costs.
+    typedef typename TR::CostMap CostMap;
+    ///Edges of the spanning tree.
+    typedef typename TR::TreeMap TreeMap;
+  private:
+    ///Pointer to the underlying graph.
+    const UGraph *graph;
+    ///Pointer to the cost map
+    const CostMap *cost;
+    ///Pointer to the map of tree edges.
+    TreeMap *_tree;
+    ///Indicates if \ref _tree is locally allocated (\c true) or not.
+    bool local_tree;
+
+    ///Creates the maps if necessary.
+    
+    void create_maps(){
+      if(!_tree){
+	local_tree=true;
+	_tree=Traits::createTreeMap(*graph);
+      }
+    }
+    
+  public :
+
+    typedef FredmanTarjan Create;
+ 
+    ///\name Named template parameters
+
+    ///@{
+
+    template <class TM>
+    struct DefTreeMapTraits : public Traits {
+      typedef TM TreeMap;
+      static TreeMap *createTreeMap(const UGraph &) {
+	throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting TreeMap 
+
+    ///\ref named-templ-param "Named parameter" for setting TreeMap
+    ///
+    template <class TM>
+    struct DefTreeMap
+      : public FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > { 
+      typedef FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
+    };
+
+    ///@}
+
+
+  protected:
+
+    FredmanTarjan() {}
+
+  private:
+
+    template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
+    void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
+	ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
+      std::vector<typename SrcGraph::Node> tree_nodes;
+      int tree_index=tree_counter;
+      bool stop=false;
+      while(!heap.empty() && !stop){
+        typename SrcGraph::Node v=heap.top();
+        heap.pop();
+	if(processed[v]!=-1){
+	  heap.state(v,Heap::PRE_HEAP);
+	  tree_index=processed[v];
+	  _tree->set(orig[pred[v]],true);
+	  stop=true;
+	  break;
+        }
+	tree_nodes.push_back(v);
+	for(typename SrcGraph::IncEdgeIt e(graph,v);e!=INVALID;++e){
+	  typename SrcGraph::Node w=graph.oppositeNode(v,e);
+	  switch(heap.state(w)){
+	  case Heap::PRE_HEAP:
+	    if(heap.size()>=limit){
+	      stop=true;
+	    }
+	    else{
+	      heap.push(w,(*cost)[orig[e]]);
+	      pred.set(w,e);
+	    }
+	    break;
+	  case Heap::IN_HEAP:
+	    if ((*cost)[orig[e]]<heap[w]){
+	      heap.decrease(w,(*cost)[orig[e]]); 
+	      pred.set(w,e);
+	    }
+	    break;
+	  case Heap::POST_HEAP:
+	    break;
+	  }
+	}
+      }
+      for(int i=1;i<(int)tree_nodes.size();++i){
+	_tree->set(orig[pred[tree_nodes[i]]],true);
+        processed.set(tree_nodes[i],tree_index);
+        heap.state(tree_nodes[i], Heap::PRE_HEAP);
+      }
+      processed.set(tree_nodes[0],tree_index);
+      heap.state(tree_nodes[0],Heap::PRE_HEAP);
+      while (!heap.empty()) {
+        typename SrcGraph::Node v=heap.top();
+	heap.pop();
+        heap.state(v,Heap::PRE_HEAP);
+      }
+      if(!stop)++tree_counter;
+    }
+
+    template<class SrcGraph,class OrigMap,class ProcessedMap>
+    void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
+	int edgenum,int& tree_counter){
+      typedef typename SrcGraph::Node Node;
+      typedef typename SrcGraph::UEdge UEdge;
+      typedef typename SrcGraph::NodeIt NodeIt;
+      typedef typename SrcGraph::template NodeMap<int> HeapCrossRef;
+      typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
+      HeapCrossRef crossref(graph,-1);
+      FibHeap<Node,Value,HeapCrossRef> heap(crossref);
+      PredMap pred(graph,INVALID);
+      int rate=2*edgenum/countNodes(graph);
+      int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
+      for(NodeIt i(graph);i!=INVALID;++i){
+	if(processed[i]==-1){
+	  heap.push(i, Value());
+	  processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
+	}
+      }
+    }
+
+    template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
+    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
+	DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
+      typedef typename SrcGraph::Node Node;
+      typedef typename DestGraph::Node DNode;
+      typedef typename SrcGraph::UEdge UEdge;
+      typedef typename DestGraph::UEdge DUEdge;
+      typedef typename SrcGraph::Edge Edge;
+      typedef typename SrcGraph::EdgeIt EdgeIt;
+      std::vector<Edge> edges;
+      std::vector<DNode> nodes(tree_counter, INVALID);
+      for(EdgeIt i(srcgraph);i!=INVALID;++i){
+	if(processed[srcgraph.source(i)]<processed[srcgraph.target(i)]){
+	  edges.push_back(i);
+          if(nodes[processed[srcgraph.source(i)]]==INVALID) {
+	    nodes[processed[srcgraph.source(i)]]=destgraph.addNode();
+	  }
+          if(nodes[processed[srcgraph.target(i)]]==INVALID) {
+	    nodes[processed[srcgraph.target(i)]]=destgraph.addNode();
+	  }
+	}
+      }
+      
+      radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
+      counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
+      for(int i=0;i!=(int)edges.size();++i){
+	int srcproc=processed[srcgraph.source(edges[i])];
+	int trgproc=processed[srcgraph.target(edges[i])];
+        Value minval=(*cost)[srcorig[edges[i]]];
+        UEdge minpos=edges[i];
+	while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
+	  trgproc==processed[srcgraph.target(edges[i+1])]) {
+	  if (minval>(*cost)[srcorig[edges[i+1]]]) {
+            minval=(*cost)[srcorig[edges[i+1]]];
+            minpos=edges[i+1];
+	  }
+          ++i;
+	} 
+	destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
+      }
+    }
+
+    template<class SrcGraph,class OrigMap>
+    void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){
+      int tree_counter = 0;
+      typename SrcGraph::template NodeMap<int> processed(graph,-1);
+      SmartUGraph destgraph;
+      SmartUGraph::UEdgeMap<typename OrigMap::Value> destorig(destgraph);
+      createTrees(graph,orig,processed,edgenum,tree_counter);
+      collect(graph,orig,destgraph,destorig,processed,tree_counter);
+      if (countNodes(destgraph)>1) {
+        phase(destgraph,destorig,edgenum);
+      }
+    }
+
+  public:      
+    
+    ///Constructor.
+    
+    ///\param _graph the graph the algorithm will run on.
+    ///\param _cost the cost map used by the algorithm.
+    FredmanTarjan(const UGraph& _graph, const CostMap& _cost) :
+      graph(&_graph), cost(&_cost),
+      _tree(0), local_tree(false)
+    {
+      checkConcept<concept::UGraph, UGraph>();
+    }
+    
+    ///Destructor.
+    ~FredmanTarjan(){
+      if(local_tree) delete _tree;
+    }
+
+    ///Sets the cost map.
+
+    ///Sets the cost map.
+    ///\return <tt> (*this) </tt>
+    FredmanTarjan &costMap(const CostMap &m){
+      cost = &m;
+      return *this;
+    }
+
+    ///Sets the map storing the tree edges.
+
+    ///Sets the map storing the tree edges.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///By default this is a BoolEdgeMap.
+    ///\return <tt> (*this) </tt>
+    FredmanTarjan &treeMap(TreeMap &m){
+      if(local_tree) {
+	delete _tree;
+	local_tree=false;
+      }
+      _tree = &m;
+      return *this;
+    }
+
+  public:
+    ///\name Execution control
+    ///The simplest way to execute the algorithm is to use
+    ///one of the member functions called \c run(...).
+
+    ///@{
+
+    ///Initializes the internal data structures.
+
+    ///Initializes the internal data structures.
+    ///
+    void init(){
+      create_maps();
+      for(typename Graph::UEdgeIt i(*graph);i!=INVALID;++i){
+	_tree->set(i,false);
+      }
+    }
+
+    ///Executes the algorithm.
+
+    ///Executes the algorithm.
+    ///
+    ///\pre init() must be called and at least one node should be added
+    ///with addSource() before using this function.
+    ///
+    ///This method runs the %FredmanTarjan algorithm from the node(s)
+    ///in order to compute the
+    ///minimum spanning tree.
+    void start(){
+	phase(*graph,identityMap<UEdge>(),countEdges(*graph));
+    }
+    
+    ///Runs %FredmanTarjan algorithm.
+    
+    ///This method runs the %FredmanTarjan algorithm
+    ///in order to compute the minimum spanning forest.
+    ///
+    ///\note ft.run() is just a shortcut of the following code.
+    ///\code
+    ///  ft.init();
+    ///  ft.start();
+    ///\endcode
+    void run() {
+      init();
+      start();
+    }
+
+    ///@}
+
+    ///\name Query Functions
+    ///The result of the %FredmanTarjan algorithm can be obtained using these
+    ///functions.\n
+    ///Before the use of these functions,
+    ///either run() or start() must be called.
+    
+    ///@{
+
+    ///Returns a reference to the tree edges map.
+
+    ///Returns a reference to the TreeEdgeMap of the edges of the
+    ///minimum spanning tree. The value of the map is \c true only if the 
+    ///edge is in the minimum spanning tree.
+    ///
+    ///\pre \ref run() or \ref start() must be called before using this 
+    ///function.
+    const TreeMap &treeMap() const { return *_tree;}
+ 
+    ///Sets the tree edges map.
+
+    ///Sets the TreeMap of the edges of the minimum spanning tree.
+    ///The map values belonging to the edges of the minimum
+    ///spanning tree are set to \param tree_edge_value or \c true by default 
+    ///while the edge values not belonging to the minimum spanning tree are 
+    ///set to
+    ///\param tree_default_value or \c false by default.
+    ///
+    ///\pre \ref run() or \ref start() must be called before using this 
+    ///function.
+
+    template<class TreeMap>
+    void treeEdges(
+        TreeMap& tree,
+        const typename TreeMap::Value& tree_edge_value=true,
+        const typename TreeMap::Value& tree_default_value=false) const {
+      for(typename UGraph::UEdgeIt i(*graph);i!=INVALID;++i){
+	(*_tree)[i]?tree.set(i,tree_edge_value):tree.set(i,tree_default_value);
+      }
+    }
+
+    ///\brief Checks if an edge is in the spanning tree or not.
+
+    ///Checks if an edge is in the spanning tree or not.
+    ///\param e is the edge that will be checked
+    ///\return \c true if e is in the spanning tree, \c false otherwise
+    bool tree(UEdge e){
+      return (*_tree)[e];
+    }
+    ///@}
+  };
+
+  /// \ingroup spantree
+  ///
+  /// \brief Function type interface for FredmanTarjan algorithm.
+  ///
+  /// Function type interface for FredmanTarjan algorithm.
+  /// \param graph the UGraph that the algorithm runs on
+  /// \param cost the CostMap of the edges
+  /// \retval tree the EdgeMap that contains whether an edge is in the 
+  /// spanning tree or not
+  ///
+  /// \sa Prim
+  template<class Graph,class CostMap,class TreeMap>
+  void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){
+    typename FredmanTarjan<Graph,CostMap>::template DefTreeMap<TreeMap>::
+      Create ft(graph,cost);
+    ft.treeMap(tree);
+    ft.run();
+  };
+
+} //END OF NAMESPACE LEMON
+
+#endif
Index: lemon/prim.h
===================================================================
--- lemon/prim.h	(revision 1912)
+++ lemon/prim.h	(revision 1912)
@@ -0,0 +1,792 @@
+/* -*- C++ -*-
+ * lemon/prim.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 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_PRIM_H
+#define LEMON_PRIM_H
+
+///\ingroup spantree
+///\file
+///\brief Prim algorithm to compute minimum spanning tree.
+
+#include <lemon/list_graph.h>
+#include <lemon/bin_heap.h>
+#include <lemon/invalid.h>
+#include <lemon/error.h>
+#include <lemon/maps.h>
+#include <lemon/traits.h>
+
+#include <lemon/concept/ugraph.h>
+
+namespace lemon {
+
+  ///Default traits class of Prim class.
+
+  ///Default traits class of Prim class.
+  ///\param GR Graph type.
+  ///\param LM Type of cost map.
+  template<class GR, class LM>
+  struct PrimDefaultTraits{
+    ///The graph type the algorithm runs on. 
+    typedef GR UGraph;
+    ///The type of the map that stores the edge costs.
+
+    ///The type of the map that stores the edge costs.
+    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
+    typedef LM CostMap;
+    //The type of the cost of the edges.
+    typedef typename LM::Value Value;
+    /// The cross reference type used by heap.
+
+    /// The cross reference type used by heap.
+    /// Usually it is \c UGraph::NodeMap<int>.
+    typedef typename UGraph::template NodeMap<int> HeapCrossRef;
+    ///Instantiates a HeapCrossRef.
+
+    ///This function instantiates a \ref HeapCrossRef. 
+    /// \param G is the graph, to which we would like to define the 
+    /// HeapCrossRef.
+    static HeapCrossRef *createHeapCrossRef(const GR &_graph){
+      return new HeapCrossRef(_graph);
+    }
+    
+    ///The heap type used by Prim algorithm.
+
+    ///The heap type used by Prim algorithm.
+    ///
+    ///\sa BinHeap
+    ///\sa Prim
+    typedef BinHeap<typename UGraph::Node, typename LM::Value,
+		    HeapCrossRef, std::less<Value> > Heap;
+
+    static Heap *createHeap(HeapCrossRef& _ref){
+      return new Heap(_ref);
+    }
+
+    ///\brief The type of the map that stores the last
+    ///edges of the minimum spanning tree.
+    /// 
+    ///The type of the map that stores the last
+    ///edges of the minimum spanning tree.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap;
+    ///Instantiates a PredMap.
+ 
+    ///This function instantiates a \ref PredMap. 
+    ///\param G is the graph, to which we would like to define the PredMap.
+    static PredMap *createPredMap(const GR &_graph){
+      return new PredMap(_graph);
+    }
+
+    ///The type of the map that stores whether an edge is in the
+    ///spanning tree or not.
+
+    ///The type of the map that stores whether an edge is in the
+    ///spanning tree or not.
+    ///By default it is a NullMap.
+    typedef NullMap<typename UGraph::UEdge,bool> TreeMap;
+    ///Instantiates a TreeMap.
+
+    ///This function instantiates a \ref TreeMap.
+    ///\param g is the graph, to which
+    ///we would like to define the \ref TreeMap
+    static TreeMap *createTreeMap(const GR &){
+      return new TreeMap();
+    }
+
+    ///The type of the map that stores whether a nodes is processed.
+ 
+    ///The type of the map that stores whether a nodes is processed.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///By default it is a NodeMap<bool>.
+    typedef NullMap<typename UGraph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
+    ///\param g is the graph, to which
+    ///we would like to define the \ref ProcessedMap
+#ifdef DOXYGEN
+    static ProcessedMap *createProcessedMap(const GR &_graph)
+#else
+    static ProcessedMap *createProcessedMap(const GR &)
+#endif
+    {
+      return new ProcessedMap();
+    }
+  };
+  
+  ///%Prim algorithm class to find a minimum spanning tree.
+  
+  /// \ingroup spantree
+  ///This class provides an efficient implementation of %Prim algorithm.
+  ///
+  ///The running time is O(e*log n) where e is the number of edges and
+  ///n is the number of nodes in the graph.
+  ///
+  ///The edge costs are passed to the algorithm using a
+  ///\ref concept::ReadMap "ReadMap",
+  ///so it is easy to change it to any kind of cost.
+  ///
+  ///The type of the cost is determined by the
+  ///\ref concept::ReadMap::Value "Value" of the cost map.
+  ///
+  ///It is also possible to change the underlying priority heap.
+  ///
+  ///\param GR The graph type the algorithm runs on. The default value
+  ///is \ref ListUGraph. The value of GR is not used directly by
+  ///Prim, it is only passed to \ref PrimDefaultTraits.
+  ///
+  ///\param LM This read-only UEdgeMap determines the costs of the
+  ///edges. It is read once for each edge, so the map may involve in
+  ///relatively time consuming process to compute the edge cost if
+  ///it is necessary. The default map type is \ref
+  ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>".  The value
+  ///of LM is not used directly by Prim, it is only passed to \ref
+  ///PrimDefaultTraits.
+  ///
+  ///\param TR Traits class to set
+  ///various data types used by the algorithm.  The default traits
+  ///class is \ref PrimDefaultTraits
+  ///"PrimDefaultTraits<GR,LM>".  See \ref
+  ///PrimDefaultTraits for the documentation of a Prim traits
+  ///class.
+  ///
+  ///\author Balazs Attila Mihaly
+
+#ifdef DOXYGEN
+  template <typename GR,
+	    typename LM,
+	    typename TR>
+#else
+  template <typename GR=ListUGraph,
+	    typename LM=typename GR::template UEdgeMap<int>,
+	    typename TR=PrimDefaultTraits<GR,LM> >
+#endif
+  class Prim {
+  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* exceptionName() const {
+	return "lemon::Prim::UninitializedParameter";
+      }
+    };
+
+    typedef TR Traits;
+    ///The type of the underlying graph.
+    typedef typename TR::UGraph UGraph;
+    ///\e
+    typedef typename UGraph::Node Node;
+    ///\e
+    typedef typename UGraph::NodeIt NodeIt;
+    ///\e
+    typedef typename UGraph::UEdge UEdge;
+    ///\e
+    typedef typename UGraph::IncEdgeIt IncEdgeIt;
+    
+    ///The type of the cost of the edges.
+    typedef typename TR::CostMap::Value Value;
+    ///The type of the map that stores the edge costs.
+    typedef typename TR::CostMap CostMap;
+    ///\brief The type of the map that stores the last
+    ///predecessor edges of the spanning tree.
+    typedef typename TR::PredMap PredMap;
+    ///Edges of the spanning tree.
+    typedef typename TR::TreeMap TreeMap;
+    ///The type of the map indicating if a node is processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
+    ///The cross reference type used for the current heap.
+    typedef typename TR::HeapCrossRef HeapCrossRef;
+    ///The heap type used by the prim algorithm.
+    typedef typename TR::Heap Heap;
+  private:
+    /// Pointer to the underlying graph.
+    const UGraph *graph;
+    /// Pointer to the cost map
+    const CostMap *cost;
+    ///Pointer to the map of predecessors edges.
+    PredMap *_pred;
+    ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    bool local_pred;
+    ///Pointer to the map of tree edges.
+    TreeMap *_tree;
+    ///Indicates if \ref _tree is locally allocated (\c true) or not.
+    bool local_tree;
+    ///Pointer to the map of processed status of the nodes.
+    ProcessedMap *_processed;
+    ///Indicates if \ref _processed is locally allocated (\c true) or not.
+    bool local_processed;
+    ///Pointer to the heap cross references.
+    HeapCrossRef *_heap_cross_ref;
+    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
+    bool local_heap_cross_ref;
+    ///Pointer to the heap.
+    Heap *_heap;
+    ///Indicates if \ref _heap is locally allocated (\c true) or not.
+    bool local_heap;
+
+    ///Creates the maps if necessary.
+    void create_maps(){
+      if(!_pred) {
+	local_pred = true;
+	_pred = Traits::createPredMap(*graph);
+      }
+      if(!_tree) {
+	local_tree = true;
+	_tree = Traits::createTreeMap(*graph);
+      }
+      if(!_processed) {
+	local_processed = true;
+	_processed = Traits::createProcessedMap(*graph);
+      }
+      if (!_heap_cross_ref) {
+	local_heap_cross_ref = true;
+	_heap_cross_ref = Traits::createHeapCrossRef(*graph);
+      }
+      if (!_heap) {
+	local_heap = true;
+	_heap = Traits::createHeap(*_heap_cross_ref);
+      }
+    }
+    
+  public :
+
+    typedef Prim Create;
+ 
+    ///\name Named template parameters
+
+    ///@{
+
+    template <class T>
+    struct DefPredMapTraits : public Traits {
+      typedef T PredMap;
+      static PredMap *createPredMap(const UGraph &_graph){
+	throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+    ///
+    template <class T>
+    struct DefPredMap 
+      : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
+      typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
+    };
+    
+    template <class T>
+    struct DefProcessedMapTraits : public Traits {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const UGraph &_graph){
+	throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+    ///
+    template <class T>
+    struct DefProcessedMap 
+      : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > { 
+      typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
+    };
+    
+    struct DefGraphProcessedMapTraits : public Traits {
+      typedef typename UGraph::template NodeMap<bool> ProcessedMap;
+      static ProcessedMap *createProcessedMap(const UGraph &_graph){
+	return new ProcessedMap(_graph);
+      }
+    };
+
+
+    template <class H, class CR>
+    struct DefHeapTraits : public Traits {
+      typedef CR HeapCrossRef;
+      typedef H Heap;
+      static HeapCrossRef *createHeapCrossRef(const UGraph &) {
+	throw UninitializedParameter();
+      }
+      static Heap *createHeap(HeapCrossRef &){
+	return UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type
+
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type
+    ///
+    template <class H, class CR = typename UGraph::template NodeMap<int> >
+    struct DefHeap
+      : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
+      typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
+    };
+
+    template <class H, class CR>
+    struct DefStandardHeapTraits : public Traits {
+      typedef CR HeapCrossRef;
+      typedef H Heap;
+      static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) {
+	return new HeapCrossRef(_graph);
+      }
+      static Heap *createHeap(HeapCrossRef &ref){
+	return new Heap(ref);
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type with automatic allocation
+
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type. It can allocate the heap and the cross reference 
+    ///object if the cross reference's constructor waits for the graph as 
+    ///parameter and the heap's constructor waits for the cross reference.
+    template <class H, class CR = typename UGraph::template NodeMap<int> >
+    struct DefStandardHeap
+      : public Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > { 
+      typedef Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > 
+      Create;
+    };
+
+    template <class TM>
+    struct DefTreeMapTraits : public Traits {
+      typedef TM TreeMap;
+      static TreeMap *createTreeMap(const UGraph &) {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting TreeMap
+
+    ///\ref named-templ-param "Named parameter" for setting TreeMap
+    ///
+    template <class TM>
+    struct DefTreeMap
+      : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
+      typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
+    };    
+
+    struct DefGraphTreeMapTraits : public Traits {
+      typedef typename UGraph::template NodeMap<bool> TreeMap;
+      static TreeMap *createTreeMap(const UGraph &_graph){
+	return new TreeMap(_graph);
+      }
+    };
+
+    ///@}
+
+
+  protected:
+
+    Prim() {}
+
+  public:      
+    
+    ///Constructor.
+    
+    ///\param _graph the graph the algorithm will run on.
+    ///\param _cost the cost map used by the algorithm.
+    Prim(const UGraph& _graph, const CostMap& _cost) :
+      graph(&_graph), cost(&_cost),
+      _pred(NULL), local_pred(false),
+      _tree(NULL), local_tree(false),
+      _processed(NULL), local_processed(false),
+      _heap_cross_ref(NULL), local_heap_cross_ref(false),
+      _heap(NULL), local_heap(false)
+    {
+      checkConcept<concept::UGraph, UGraph>();
+    }
+    
+    ///Destructor.
+    ~Prim(){
+      if(local_pred) delete _pred;
+      if(local_tree) delete _tree;
+      if(local_processed) delete _processed;
+      if(local_heap_cross_ref) delete _heap_cross_ref;
+      if(local_heap) delete _heap;
+    }
+
+    ///\brief Sets the cost map.
+
+    ///Sets the cost map.
+    ///\return <tt> (*this) </tt>
+    Prim &costMap(const CostMap &m){
+      cost = &m;
+      return *this;
+    }
+
+    ///\brief Sets the map storing the predecessor edges.
+
+    ///Sets the map storing the predecessor edges.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Prim &predMap(PredMap &m){
+      if(local_pred) {
+	delete _pred;
+	local_pred=false;
+      }
+      _pred = &m;
+      return *this;
+    }
+
+    ///\brief Sets the map storing the tree edges.
+
+    ///Sets the map storing the tree edges.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///By default this is a NullMap.
+    ///\return <tt> (*this) </tt>
+    Prim &treeMap(TreeMap &m){
+      if(local_tree) {
+	delete _tree;
+	local_tree=false;
+      }
+      _tree = &m;
+      return *this;
+    }
+
+    ///\brief Sets the heap and the cross reference used by algorithm.
+
+    ///Sets the heap and the cross reference used by algorithm.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Prim &heap(Heap& heap, HeapCrossRef &crossRef){
+      if(local_heap_cross_ref) {
+	delete _heap_cross_ref;
+	local_heap_cross_ref=false;
+      }
+      _heap_cross_ref = &crossRef;
+      if(local_heap) {
+	delete _heap;
+	local_heap=false;
+      }
+      _heap = &heap;
+      return *this;
+    }
+
+  public:
+    ///\name Execution control
+    ///The simplest way to execute the algorithm is to use
+    ///one of the member functions called \c run(...).
+    ///\n
+    ///If you need more control on the execution,
+    ///first you must call \ref init(), then you can add several source nodes
+    ///with \ref addSource().
+    ///Finally \ref start() will perform the actual path
+    ///computation.
+
+    ///@{
+
+    ///\brief Initializes the internal data structures.
+
+    ///Initializes the internal data structures.
+    ///
+    void init(){
+      create_maps();
+      _heap->clear();
+      for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) {
+	_pred->set(u,INVALID);
+	_processed->set(u,false);
+	_heap_cross_ref->set(u,Heap::PRE_HEAP);
+      }
+    }
+    
+    ///\brief Adds a new source node.
+
+    ///Adds a new source node to the priority heap.
+    ///
+    ///It checks if the node has already been added to the heap and
+    ///it is pushed to the heap only if it was not in the heap.
+    void addSource(Node s){
+      if(_heap->state(s) != Heap::IN_HEAP) {
+	_heap->push(s,Value());
+      }
+    }
+    ///\brief Processes the next node in the priority heap
+
+    ///Processes the next node in the priority heap.
+    ///
+    ///\return The processed node.
+    ///
+    ///\warning The priority heap must not be empty!
+    Node processNextNode(){
+      Node v=_heap->top(); 
+      _heap->pop();
+      _processed->set(v,true);
+      
+      for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
+	Node w=graph->oppositeNode(v,e);
+	switch(_heap->state(w)) {
+	case Heap::PRE_HEAP:
+	  _heap->push(w,(*cost)[e]);
+	  _pred->set(w,e);
+	  break;
+	case Heap::IN_HEAP:
+	  if ( (*cost)[e] < (*_heap)[w] ) {
+	    _heap->decrease(w,(*cost)[e]); 
+	    _pred->set(w,e);
+	  }
+	  break;
+	case Heap::POST_HEAP:
+	  break;
+	}
+      }
+      if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
+      return v;
+    }
+
+    ///\brief Next node to be processed.
+    
+    ///Next node to be processed.
+    ///
+    ///\return The next node to be processed or INVALID if the priority heap
+    /// is empty.
+    Node nextNode(){ 
+      return _heap->empty()?_heap->top():INVALID;
+    }
+ 
+    ///\brief Returns \c false if there are nodes to be processed in the priority heap
+    ///
+    ///Returns \c false if there are nodes
+    ///to be processed in the priority heap
+    bool emptyQueue() { return _heap->empty(); }
+    ///\brief Returns the number of the nodes to be processed in the priority heap
+
+    ///Returns the number of the nodes to be processed in the priority heap
+    ///
+    int queueSize() { return _heap->size(); }
+    
+    ///\brief Executes the algorithm.
+
+    ///Executes the algorithm.
+    ///
+    ///\pre init() must be called and at least one node should be added
+    ///with addSource() before using this function.
+    ///
+    ///This method runs the %Prim algorithm from the node(s)
+    ///in order to compute the
+    ///minimum spanning tree.
+    ///
+    void start(){
+      while ( !_heap->empty() ) processNextNode();
+    }
+    
+    ///\brief Executes the algorithm until a condition is met.
+
+    ///Executes the algorithm until a condition is met.
+    ///
+    ///\pre init() must be called and at least one node should be added
+    ///with addSource() before using this function.
+    ///
+    ///\param nm must be a bool (or convertible) node map. The algorithm
+    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
+    template<class NodeBoolMap>
+    void start(const NodeBoolMap &nm){
+      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
+      if ( !_heap->empty() ) _processed->set(_heap->top(),true);
+    }
+    
+    ///\brief Runs %Prim algorithm.
+    
+    ///This method runs the %Prim algorithm
+    ///in order to compute the
+    ///minimum spanning tree (or minimum spanning forest).
+    ///The method also works on graphs that has more than one components.
+    ///In this case it computes the minimum spanning forest.
+    void run() {
+      init();
+      for(NodeIt it(*graph);it!=INVALID;++it){
+	if(!processed(it)){
+	  addSource(it);
+	  start();
+	}
+      }
+    }
+
+    ///\brief Runs %Prim algorithm from node \c s.
+    
+    ///This method runs the %Prim algorithm from node \c s
+    ///in order to
+    ///compute the
+    ///minimun spanning tree
+    ///
+    ///\note d.run(s) is just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start();
+    ///\endcode
+    ///\note If the graph has more than one components, the method
+    ///will compute the minimun spanning tree for only one component.
+    ///
+    ///See \ref run() if you want to compute the minimal spanning forest.
+    void run(Node s){
+      init();
+      addSource(s);
+      start();
+    }
+    
+    ///@}
+
+    ///\name Query Functions
+    ///The result of the %Prim algorithm can be obtained using these
+    ///functions.\n
+    ///Before the use of these functions,
+    ///either run() or start() must be called.
+    
+    ///@{
+
+    ///\brief Returns the 'previous edge' of the minimum spanning tree.
+
+    ///For a node \c v it returns the 'previous edge' of the minimum spanning tree,
+    ///i.e. it returns the edge from where \c v was reached. For a source node
+    ///or an unreachable node it is \ref INVALID.
+    ///The minimum spanning tree used here is equal to the minimum spanning tree used
+    ///in \ref predNode().  \pre \ref run() or \ref start() must be called before
+    ///using this function.
+    UEdge predEdge(Node v) const { return (*_pred)[v]; }
+
+    ///\brief Returns the 'previous node' of the minimum spanning tree.
+
+    ///For a node \c v it returns the 'previous node' of the minimum spanning tree,
+    ///i.e. it returns the node from where \c v was reached. For a source node
+    ///or an unreachable node it is \ref INVALID.
+    //The minimum spanning tree used here is equal to the minimum spanning
+    ///tree used in \ref predEdge().  \pre \ref run() or \ref start() must be called
+    ///before using this function.
+    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
+				  graph->source((*_pred)[v]); }
+    
+    ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
+
+    ///Returns a reference to the NodeMap of the edges of the
+    ///minimum spanning tree.
+    ///\pre \ref run() or \ref start() must be called before using this function.
+    const PredMap &predMap() const { return *_pred;}
+ 
+    ///\brief Returns a reference to the tree edges map.
+
+    ///Returns a reference to the TreeEdgeMap of the edges of the
+    ///minimum spanning tree. The value of the map is \c true only if the edge is in
+    ///the minimum spanning tree.
+    ///\warning By default, the TreeEdgeMap is a NullMap.
+    ///
+    ///If it is not set before the execution of the algorithm, use the \ref
+    ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the
+    ///edges of the minimum spanning tree in O(n) time where n is the number of
+    ///nodes in the graph.
+    ///\pre \ref run() or \ref start() must be called before using this function.
+    const TreeMap &treeMap() const { return *_tree;}
+ 
+    ///\brief Sets the tree edges map.
+
+    ///Sets the TreeMap of the edges of the minimum spanning tree.
+    ///The map values belonging to the edges of the minimum
+    ///spanning tree are set to \param tree_edge_value or \c true by default,
+    ///the other map values remain untouched.
+    ///
+    ///\pre \ref run() or \ref start() must be called before using this function.
+
+    template<class TreeMap>
+    void quickTreeEdges(
+        TreeMap& tree,
+        const typename TreeMap::Value& tree_edge_value=true) const {
+      for(NodeIt i(*graph);i!=INVALID;++i){
+        if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
+      }
+    }
+
+    ///\brief Sets the tree edges map.
+
+    ///Sets the TreeMap of the edges of the minimum spanning tree.
+    ///The map values belonging to the edges of the minimum
+    ///spanning tree are set to \param tree_edge_value or \c true by default while
+    ///the edge values not belonging to the minimum spanning tree are set to
+    ///\param tree_default_value or \c false by default.
+    ///
+    ///\pre \ref run() or \ref start() must be called before using this function.
+
+    template<class TreeMap>
+    void treeEdges(
+        TreeMap& tree,
+        const typename TreeMap::Value& tree_edge_value=true,
+        const typename TreeMap::Value& tree_default_value=false) const {
+      for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
+	tree.set(i,tree_default_value);
+      for(NodeIt i(*graph);i!=INVALID;++i){
+        if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
+      }
+    }
+
+    ///\brief Checks if a node is reachable from the starting node.
+
+    ///Returns \c true if \c v is reachable from the starting node.
+    ///\warning The source nodes are inditated as unreached.
+    ///\pre \ref run() or \ref start() must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
+
+    ///\brief Checks if a node is processed.
+
+    ///Returns \c true if \c v is processed, i.e. \c v is already connencted to the
+    ///minimum spanning tree.
+    ///\pre \ref run() or \ref start() must be called before using this function.
+    ///
+    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
+    
+
+    ///\brief Checks if an edge is in the spanning tree or not.
+
+    ///Checks if an edge is in the spanning tree or not.
+    ///\param e is the edge that will be checked
+    ///\return \c true if e is in the spanning tree, \c false otherwise
+    bool tree(UEdge e){
+      return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
+    }
+    ///@}
+  };
+
+
+  /// \ingroup spantree
+  ///
+  /// \brief Function type interface for Prim algorithm.
+  ///
+  /// Function type interface for Prim algorithm.
+  /// \param graph the UGraph that the algorithm runs on
+  /// \param cost the CostMap of the edges
+  /// \retval tree the EdgeMap that contains whether an edge is in 
+  /// the spanning tree or not
+  ///
+  ///\sa Prim
+  template<class Graph,class CostMap,class TreeMap>
+  void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
+    typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
+      Create prm(graph,cost);
+    prm.treeMap(tree);
+    prm.run();
+  };
+
+} //END OF NAMESPACE LEMON
+
+#endif
