source: lemon-0.x/lemon/prim.h @ 2490:31a93dd6f714

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * 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/bits/invalid.h>
#include <lemon/error.h>
#include <lemon/maps.h>
#include <lemon/bits/traits.h>

#include <lemon/concepts/ugraph.h>

namespace lemon {

  ///Default traits class of Prim class.

  ///Default traits class of Prim class.
  ///\param GR Graph type.
  ///\param CM Type of cost map.
  template<class GR, class CM>
  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 concepts::ReadMap "ReadMap" concept.
    typedef CM CostMap;
    //The type of the cost of the edges.
    typedef typename CM::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 _graph 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 CM::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 concepts::WriteMap "WriteMap" concept.
    ///
    typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap;
    ///Instantiates a PredMap.
 
    ///This function instantiates a \ref PredMap. 
    ///\param _graph 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.
    ///
    ///The first parameter 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 concepts::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 _graph 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 \f$ O(e\log(n)) \f$ 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 concepts::ReadMap "ReadMap",
  ///so it is easy to change it to any kind of cost.
  ///
  ///The type of the cost is determined by the
  ///\ref concepts::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 CM 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
  ///concepts::UGraph::UEdgeMap "UGraph::UEdgeMap<int>".  The value
  ///of CM 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,CM>".  See \ref
  ///PrimDefaultTraits for the documentation of a Prim traits
  ///class.
  ///
  ///\author Balazs Attila Mihaly

#ifdef DOXYGEN
  template <typename GR,
            typename CM,
            typename TR>
#else
  template <typename GR=ListUGraph,
            typename CM=typename GR::template UEdgeMap<int>,
            typename TR=PrimDefaultTraits<GR,CM> >
#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* what() const throw() {
        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();
      }
    };
    ///\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 
      : 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();
      }
    };
    ///\brief \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();
      }
    };
    ///\brief \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);
      }
    };
    ///\brief \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();
      }
    };
    ///\brief \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(0), local_pred(false),
      _tree(0), local_tree(false),
      _processed(0), local_processed(false),
      _heap_cross_ref(0), local_heap_cross_ref(false),
      _heap(0), local_heap(false)
    {
      checkConcept<concepts::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 p.run(s) is just a shortcut of the following code.
    ///\code
    ///  p.init();
    ///  p.addSource(s);
    ///  p.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 \c 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 {
      for(NodeIt i(*graph);i!=INVALID;++i){
        if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],true);
      }
    }

    ///\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 \c tree_edge_value or \c true by default while
    ///the edge values not belonging to the minimum spanning tree are set to
    ///\c 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 {
      typedef typename ItemSetTraits<UGraph,UEdge>::ItemIt TreeMapIt;
      for(TreeMapIt i(*graph); i != INVALID; ++i) {
        tree.set(i,false);
      }
      for(NodeIt i(*graph); i != INVALID; ++i){
        if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true);
      }
    }

    ///\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;
    }

    ///\brief Returns the value of the total cost of the spanning tree.
    ///
    /// Returns the value of the total cost of the spanning tree.
    Value treeValue() const {
      Value value = 0;
      for(NodeIt i(*graph); i!= INVALID; ++i){
        if ((*_pred)[i] != INVALID) value += (*cost)[(*_pred)[i]];
      }
      return value;
    }
    ///@}
  };


  /// \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
  /// \return The total cost of the spanning tree
  ///
  ///\sa Prim
  template<class Graph,class CostMap,class TreeMap>
  typename CostMap::Value 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();
    return prm.treeValue();
  }

  /// \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
  /// the spanning tree or not
  /// \return The total cost of the spanning tree
  ///
  ///\sa Prim
  template<class Graph,class CostMap,class TreeMap>
  typename CostMap::Value prim(const Graph& graph, 
                               const CostMap& cost){
    typename Prim<Graph,CostMap>::
      Create prm(graph,cost);
    prm.run();
    return prm.treeValue();
  }

} //END OF NAMESPACE LEMON

#endif