lemon/prim.h
author deba
Fri, 31 Aug 2007 08:40:49 +0000
changeset 2469 d6f12a9b5cbf
parent 2391 14a343be7a5a
child 2490 31a93dd6f714
permissions -rw-r--r--
Invalid assignments ambiguity handling
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_PRIM_H
    20 #define LEMON_PRIM_H
    21 
    22 ///\ingroup spantree
    23 ///\file
    24 ///\brief Prim algorithm to compute minimum spanning tree.
    25 
    26 #include <lemon/list_graph.h>
    27 #include <lemon/bin_heap.h>
    28 #include <lemon/bits/invalid.h>
    29 #include <lemon/error.h>
    30 #include <lemon/maps.h>
    31 #include <lemon/bits/traits.h>
    32 
    33 #include <lemon/concepts/ugraph.h>
    34 
    35 namespace lemon {
    36 
    37   ///Default traits class of Prim class.
    38 
    39   ///Default traits class of Prim class.
    40   ///\param GR Graph type.
    41   ///\param CM Type of cost map.
    42   template<class GR, class CM>
    43   struct PrimDefaultTraits{
    44     ///The graph type the algorithm runs on. 
    45     typedef GR UGraph;
    46     ///The type of the map that stores the edge costs.
    47 
    48     ///The type of the map that stores the edge costs.
    49     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef CM CostMap;
    51     //The type of the cost of the edges.
    52     typedef typename CM::Value Value;
    53     /// The cross reference type used by heap.
    54 
    55     /// The cross reference type used by heap.
    56     /// Usually it is \c UGraph::NodeMap<int>.
    57     typedef typename UGraph::template NodeMap<int> HeapCrossRef;
    58     ///Instantiates a HeapCrossRef.
    59 
    60     ///This function instantiates a \ref HeapCrossRef. 
    61     /// \param _graph is the graph, to which we would like to define the 
    62     /// HeapCrossRef.
    63     static HeapCrossRef *createHeapCrossRef(const GR &_graph){
    64       return new HeapCrossRef(_graph);
    65     }
    66     
    67     ///The heap type used by Prim algorithm.
    68 
    69     ///The heap type used by Prim algorithm.
    70     ///
    71     ///\sa BinHeap
    72     ///\sa Prim
    73     typedef BinHeap<typename CM::Value,
    74 		    HeapCrossRef, std::less<Value> > Heap;
    75 
    76     static Heap *createHeap(HeapCrossRef& _ref){
    77       return new Heap(_ref);
    78     }
    79 
    80     ///\brief The type of the map that stores the last
    81     ///edges of the minimum spanning tree.
    82     /// 
    83     ///The type of the map that stores the last
    84     ///edges of the minimum spanning tree.
    85     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    86     ///
    87     typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap;
    88     ///Instantiates a PredMap.
    89  
    90     ///This function instantiates a \ref PredMap. 
    91     ///\param _graph is the graph, to which we would like to define the PredMap.
    92     static PredMap *createPredMap(const GR &_graph){
    93       return new PredMap(_graph);
    94     }
    95 
    96     ///The type of the map that stores whether an edge is in the
    97     ///spanning tree or not.
    98 
    99     ///The type of the map that stores whether an edge is in the
   100     ///spanning tree or not.
   101     ///By default it is a NullMap.
   102     typedef NullMap<typename UGraph::UEdge,bool> TreeMap;
   103     ///Instantiates a TreeMap.
   104 
   105     ///This function instantiates a \ref TreeMap.
   106     ///
   107     ///The first parameter is the graph, to which
   108     ///we would like to define the \ref TreeMap
   109     static TreeMap *createTreeMap(const GR &){
   110       return new TreeMap();
   111     }
   112 
   113     ///The type of the map that stores whether a nodes is processed.
   114  
   115     ///The type of the map that stores whether a nodes is processed.
   116     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   117     ///By default it is a NodeMap<bool>.
   118     typedef NullMap<typename UGraph::Node,bool> ProcessedMap;
   119     ///Instantiates a ProcessedMap.
   120  
   121     ///This function instantiates a \ref ProcessedMap. 
   122     ///\param _graph is the graph, to which
   123     ///we would like to define the \ref ProcessedMap
   124 #ifdef DOXYGEN
   125     static ProcessedMap *createProcessedMap(const GR &_graph)
   126 #else
   127     static ProcessedMap *createProcessedMap(const GR &)
   128 #endif
   129     {
   130       return new ProcessedMap();
   131     }
   132   };
   133   
   134   ///%Prim algorithm class to find a minimum spanning tree.
   135   
   136   /// \ingroup spantree
   137   ///This class provides an efficient implementation of %Prim algorithm.
   138   ///
   139   ///The running time is \f$ O(e\log(n)) \f$ where e is the number of edges and
   140   ///n is the number of nodes in the graph.
   141   ///
   142   ///The edge costs are passed to the algorithm using a
   143   ///\ref concepts::ReadMap "ReadMap",
   144   ///so it is easy to change it to any kind of cost.
   145   ///
   146   ///The type of the cost is determined by the
   147   ///\ref concepts::ReadMap::Value "Value" of the cost map.
   148   ///
   149   ///It is also possible to change the underlying priority heap.
   150   ///
   151   ///\param GR The graph type the algorithm runs on. The default value
   152   ///is \ref ListUGraph. The value of GR is not used directly by
   153   ///Prim, it is only passed to \ref PrimDefaultTraits.
   154   ///
   155   ///\param CM This read-only UEdgeMap determines the costs of the
   156   ///edges. It is read once for each edge, so the map may involve in
   157   ///relatively time consuming process to compute the edge cost if
   158   ///it is necessary. The default map type is \ref
   159   ///concepts::UGraph::UEdgeMap "UGraph::UEdgeMap<int>".  The value
   160   ///of CM is not used directly by Prim, it is only passed to \ref
   161   ///PrimDefaultTraits.
   162   ///
   163   ///\param TR Traits class to set
   164   ///various data types used by the algorithm.  The default traits
   165   ///class is \ref PrimDefaultTraits
   166   ///"PrimDefaultTraits<GR,CM>".  See \ref
   167   ///PrimDefaultTraits for the documentation of a Prim traits
   168   ///class.
   169   ///
   170   ///\author Balazs Attila Mihaly
   171 
   172 #ifdef DOXYGEN
   173   template <typename GR,
   174 	    typename CM,
   175 	    typename TR>
   176 #else
   177   template <typename GR=ListUGraph,
   178 	    typename CM=typename GR::template UEdgeMap<int>,
   179 	    typename TR=PrimDefaultTraits<GR,CM> >
   180 #endif
   181   class Prim {
   182   public:
   183     
   184     /// \brief \ref Exception for uninitialized parameters.
   185     ///
   186     /// This error represents problems in the initialization
   187     /// of the parameters of the algorithms.
   188     class UninitializedParameter : public lemon::UninitializedParameter {
   189     public:
   190       virtual const char* what() const throw() {
   191 	return "lemon::Prim::UninitializedParameter";
   192       }
   193     };
   194 
   195     typedef TR Traits;
   196     ///The type of the underlying graph.
   197     typedef typename TR::UGraph UGraph;
   198     ///\e
   199     typedef typename UGraph::Node Node;
   200     ///\e
   201     typedef typename UGraph::NodeIt NodeIt;
   202     ///\e
   203     typedef typename UGraph::UEdge UEdge;
   204     ///\e
   205     typedef typename UGraph::IncEdgeIt IncEdgeIt;
   206     
   207     ///The type of the cost of the edges.
   208     typedef typename TR::CostMap::Value Value;
   209     ///The type of the map that stores the edge costs.
   210     typedef typename TR::CostMap CostMap;
   211     ///\brief The type of the map that stores the last
   212     ///predecessor edges of the spanning tree.
   213     typedef typename TR::PredMap PredMap;
   214     ///Edges of the spanning tree.
   215     typedef typename TR::TreeMap TreeMap;
   216     ///The type of the map indicating if a node is processed.
   217     typedef typename TR::ProcessedMap ProcessedMap;
   218     ///The cross reference type used for the current heap.
   219     typedef typename TR::HeapCrossRef HeapCrossRef;
   220     ///The heap type used by the prim algorithm.
   221     typedef typename TR::Heap Heap;
   222   private:
   223     /// Pointer to the underlying graph.
   224     const UGraph *graph;
   225     /// Pointer to the cost map
   226     const CostMap *cost;
   227     ///Pointer to the map of predecessors edges.
   228     PredMap *_pred;
   229     ///Indicates if \ref _pred is locally allocated (\c true) or not.
   230     bool local_pred;
   231     ///Pointer to the map of tree edges.
   232     TreeMap *_tree;
   233     ///Indicates if \ref _tree is locally allocated (\c true) or not.
   234     bool local_tree;
   235     ///Pointer to the map of processed status of the nodes.
   236     ProcessedMap *_processed;
   237     ///Indicates if \ref _processed is locally allocated (\c true) or not.
   238     bool local_processed;
   239     ///Pointer to the heap cross references.
   240     HeapCrossRef *_heap_cross_ref;
   241     ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
   242     bool local_heap_cross_ref;
   243     ///Pointer to the heap.
   244     Heap *_heap;
   245     ///Indicates if \ref _heap is locally allocated (\c true) or not.
   246     bool local_heap;
   247 
   248     ///Creates the maps if necessary.
   249     void create_maps(){
   250       if(!_pred) {
   251 	local_pred = true;
   252 	_pred = Traits::createPredMap(*graph);
   253       }
   254       if(!_tree) {
   255 	local_tree = true;
   256 	_tree = Traits::createTreeMap(*graph);
   257       }
   258       if(!_processed) {
   259 	local_processed = true;
   260 	_processed = Traits::createProcessedMap(*graph);
   261       }
   262       if (!_heap_cross_ref) {
   263 	local_heap_cross_ref = true;
   264 	_heap_cross_ref = Traits::createHeapCrossRef(*graph);
   265       }
   266       if (!_heap) {
   267 	local_heap = true;
   268 	_heap = Traits::createHeap(*_heap_cross_ref);
   269       }
   270     }
   271     
   272   public :
   273 
   274     typedef Prim Create;
   275  
   276     ///\name Named template parameters
   277 
   278     ///@{
   279 
   280     template <class T>
   281     struct DefPredMapTraits : public Traits {
   282       typedef T PredMap;
   283       static PredMap *createPredMap(const UGraph &_graph){
   284 	throw UninitializedParameter();
   285       }
   286     };
   287     ///\ref named-templ-param "Named parameter" for setting PredMap type
   288 
   289     ///\ref named-templ-param "Named parameter" for setting PredMap type
   290     ///
   291     template <class T>
   292     struct DefPredMap 
   293       : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
   294       typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
   295     };
   296     
   297     template <class T>
   298     struct DefProcessedMapTraits : public Traits {
   299       typedef T ProcessedMap;
   300       static ProcessedMap *createProcessedMap(const UGraph &_graph){
   301 	throw UninitializedParameter();
   302       }
   303     };
   304     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   305 
   306     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   307     ///
   308     template <class T>
   309     struct DefProcessedMap 
   310       : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > { 
   311       typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
   312     };
   313     
   314     struct DefGraphProcessedMapTraits : public Traits {
   315       typedef typename UGraph::template NodeMap<bool> ProcessedMap;
   316       static ProcessedMap *createProcessedMap(const UGraph &_graph){
   317 	return new ProcessedMap(_graph);
   318       }
   319     };
   320 
   321 
   322     template <class H, class CR>
   323     struct DefHeapTraits : public Traits {
   324       typedef CR HeapCrossRef;
   325       typedef H Heap;
   326       static HeapCrossRef *createHeapCrossRef(const UGraph &) {
   327 	throw UninitializedParameter();
   328       }
   329       static Heap *createHeap(HeapCrossRef &){
   330 	return UninitializedParameter();
   331       }
   332     };
   333     ///\brief \ref named-templ-param "Named parameter" for setting
   334     ///heap and cross reference type
   335     ///
   336     ///\ref named-templ-param "Named parameter" for setting heap and cross 
   337     ///reference type
   338     ///
   339     template <class H, class CR = typename UGraph::template NodeMap<int> >
   340     struct DefHeap
   341       : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
   342       typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
   343     };
   344 
   345     template <class H, class CR>
   346     struct DefStandardHeapTraits : public Traits {
   347       typedef CR HeapCrossRef;
   348       typedef H Heap;
   349       static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) {
   350 	return new HeapCrossRef(_graph);
   351       }
   352       static Heap *createHeap(HeapCrossRef &ref){
   353 	return new Heap(ref);
   354       }
   355     };
   356     ///\brief \ref named-templ-param "Named parameter" for setting
   357     ///heap and cross reference type with automatic allocation
   358     ///
   359     ///\ref named-templ-param "Named parameter" for setting heap and cross 
   360     ///reference type. It can allocate the heap and the cross reference 
   361     ///object if the cross reference's constructor waits for the graph as 
   362     ///parameter and the heap's constructor waits for the cross reference.
   363     template <class H, class CR = typename UGraph::template NodeMap<int> >
   364     struct DefStandardHeap
   365       : public Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > { 
   366       typedef Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > 
   367       Create;
   368     };
   369 
   370     template <class TM>
   371     struct DefTreeMapTraits : public Traits {
   372       typedef TM TreeMap;
   373       static TreeMap *createTreeMap(const UGraph &) {
   374         throw UninitializedParameter();
   375       }
   376     };
   377     ///\ref named-templ-param "Named parameter" for setting TreeMap
   378 
   379     ///\ref named-templ-param "Named parameter" for setting TreeMap
   380     ///
   381     template <class TM>
   382     struct DefTreeMap
   383       : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
   384       typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
   385     };    
   386 
   387     struct DefGraphTreeMapTraits : public Traits {
   388       typedef typename UGraph::template NodeMap<bool> TreeMap;
   389       static TreeMap *createTreeMap(const UGraph &_graph){
   390 	return new TreeMap(_graph);
   391       }
   392     };
   393 
   394     ///@}
   395 
   396 
   397   protected:
   398 
   399     Prim() {}
   400 
   401   public:      
   402     
   403     ///Constructor.
   404     ///
   405     ///\param _graph the graph the algorithm will run on.
   406     ///\param _cost the cost map used by the algorithm.
   407     Prim(const UGraph& _graph, const CostMap& _cost) :
   408       graph(&_graph), cost(&_cost),
   409       _pred(0), local_pred(false),
   410       _tree(0), local_tree(false),
   411       _processed(0), local_processed(false),
   412       _heap_cross_ref(0), local_heap_cross_ref(false),
   413       _heap(0), local_heap(false)
   414     {
   415       checkConcept<concepts::UGraph, UGraph>();
   416     }
   417     
   418     ///Destructor.
   419     ~Prim(){
   420       if(local_pred) delete _pred;
   421       if(local_tree) delete _tree;
   422       if(local_processed) delete _processed;
   423       if(local_heap_cross_ref) delete _heap_cross_ref;
   424       if(local_heap) delete _heap;
   425     }
   426 
   427     ///\brief Sets the cost map.
   428     ///
   429     ///Sets the cost map.
   430     ///\return <tt> (*this) </tt>
   431     Prim &costMap(const CostMap &m){
   432       cost = &m;
   433       return *this;
   434     }
   435 
   436     ///\brief Sets the map storing the predecessor edges.
   437     ///
   438     ///Sets the map storing the predecessor edges.
   439     ///If you don't use this function before calling \ref run(),
   440     ///it will allocate one. The destuctor deallocates this
   441     ///automatically allocated map, of course.
   442     ///\return <tt> (*this) </tt>
   443     Prim &predMap(PredMap &m){
   444       if(local_pred) {
   445 	delete _pred;
   446 	local_pred=false;
   447       }
   448       _pred = &m;
   449       return *this;
   450     }
   451 
   452     ///\brief Sets the map storing the tree edges.
   453     ///
   454     ///Sets the map storing the tree edges.
   455     ///If you don't use this function before calling \ref run(),
   456     ///it will allocate one. The destuctor deallocates this
   457     ///automatically allocated map, of course.
   458     ///By default this is a NullMap.
   459     ///\return <tt> (*this) </tt>
   460     Prim &treeMap(TreeMap &m){
   461       if(local_tree) {
   462 	delete _tree;
   463 	local_tree=false;
   464       }
   465       _tree = &m;
   466       return *this;
   467     }
   468 
   469     ///\brief Sets the heap and the cross reference used by algorithm.
   470     ///
   471     ///Sets the heap and the cross reference used by algorithm.
   472     ///If you don't use this function before calling \ref run(),
   473     ///it will allocate one. The destuctor deallocates this
   474     ///automatically allocated map, of course.
   475     ///\return <tt> (*this) </tt>
   476     Prim &heap(Heap& heap, HeapCrossRef &crossRef){
   477       if(local_heap_cross_ref) {
   478 	delete _heap_cross_ref;
   479 	local_heap_cross_ref=false;
   480       }
   481       _heap_cross_ref = &crossRef;
   482       if(local_heap) {
   483 	delete _heap;
   484 	local_heap=false;
   485       }
   486       _heap = &heap;
   487       return *this;
   488     }
   489 
   490   public:
   491     ///\name Execution control
   492     ///The simplest way to execute the algorithm is to use
   493     ///one of the member functions called \c run(...).
   494     ///\n
   495     ///If you need more control on the execution,
   496     ///first you must call \ref init(), then you can add several source nodes
   497     ///with \ref addSource().
   498     ///Finally \ref start() will perform the actual path
   499     ///computation.
   500 
   501     ///@{
   502 
   503     ///\brief Initializes the internal data structures.
   504     ///
   505     ///Initializes the internal data structures.
   506     ///
   507     void init(){
   508       create_maps();
   509       _heap->clear();
   510       for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) {
   511 	_pred->set(u,INVALID);
   512 	_processed->set(u,false);
   513 	_heap_cross_ref->set(u,Heap::PRE_HEAP);
   514       }
   515     }
   516     
   517     ///\brief Adds a new source node.
   518     ///
   519     ///Adds a new source node to the priority heap.
   520     ///
   521     ///It checks if the node has already been added to the heap and
   522     ///it is pushed to the heap only if it was not in the heap.
   523     void addSource(Node s){
   524       if(_heap->state(s) != Heap::IN_HEAP) {
   525 	_heap->push(s,Value());
   526       }
   527     }
   528     ///\brief Processes the next node in the priority heap
   529     ///
   530     ///Processes the next node in the priority heap.
   531     ///
   532     ///\return The processed node.
   533     ///
   534     ///\warning The priority heap must not be empty!
   535     Node processNextNode(){
   536       Node v=_heap->top(); 
   537       _heap->pop();
   538       _processed->set(v,true);
   539       
   540       for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
   541 	Node w=graph->oppositeNode(v,e);
   542 	switch(_heap->state(w)) {
   543 	case Heap::PRE_HEAP:
   544 	  _heap->push(w,(*cost)[e]);
   545 	  _pred->set(w,e);
   546 	  break;
   547 	case Heap::IN_HEAP:
   548 	  if ( (*cost)[e] < (*_heap)[w] ) {
   549 	    _heap->decrease(w,(*cost)[e]); 
   550 	    _pred->set(w,e);
   551 	  }
   552 	  break;
   553 	case Heap::POST_HEAP:
   554 	  break;
   555 	}
   556       }
   557       if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
   558       return v;
   559     }
   560 
   561     ///\brief Next node to be processed.
   562     ///
   563     ///Next node to be processed.
   564     ///
   565     ///\return The next node to be processed or INVALID if the priority heap
   566     /// is empty.
   567     Node nextNode(){ 
   568       return _heap->empty()?_heap->top():INVALID;
   569     }
   570  
   571     ///\brief Returns \c false if there are nodes to be processed in
   572     ///the priority heap
   573     ///
   574     ///Returns \c false if there are nodes
   575     ///to be processed in the priority heap
   576     bool emptyQueue() { return _heap->empty(); }
   577 
   578     ///\brief Returns the number of the nodes to be processed in the
   579     ///priority heap
   580     ///
   581     ///Returns the number of the nodes to be processed in the priority heap
   582     ///
   583     int queueSize() { return _heap->size(); }
   584     
   585     ///\brief Executes the algorithm.
   586     ///
   587     ///Executes the algorithm.
   588     ///
   589     ///\pre init() must be called and at least one node should be added
   590     ///with addSource() before using this function.
   591     ///
   592     ///This method runs the %Prim algorithm from the node(s)
   593     ///in order to compute the
   594     ///minimum spanning tree.
   595     ///
   596     void start(){
   597       while ( !_heap->empty() ) processNextNode();
   598     }
   599     
   600     ///\brief Executes the algorithm until a condition is met.
   601     ///
   602     ///Executes the algorithm until a condition is met.
   603     ///
   604     ///\pre init() must be called and at least one node should be added
   605     ///with addSource() before using this function.
   606     ///
   607     ///\param nm must be a bool (or convertible) node map. The algorithm
   608     ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
   609     template<class NodeBoolMap>
   610     void start(const NodeBoolMap &nm){
   611       while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
   612       if ( !_heap->empty() ) _processed->set(_heap->top(),true);
   613     }
   614     
   615     ///\brief Runs %Prim algorithm.
   616     ///
   617     ///This method runs the %Prim algorithm
   618     ///in order to compute the
   619     ///minimum spanning tree (or minimum spanning forest).
   620     ///The method also works on graphs that has more than one components.
   621     ///In this case it computes the minimum spanning forest.
   622     void run() {
   623       init();
   624       for(NodeIt it(*graph);it!=INVALID;++it){
   625 	if(!processed(it)){
   626 	  addSource(it);
   627 	  start();
   628 	}
   629       }
   630     }
   631 
   632     ///\brief Runs %Prim algorithm from node \c s.
   633     ///
   634     ///This method runs the %Prim algorithm from node \c s
   635     ///in order to
   636     ///compute the
   637     ///minimun spanning tree
   638     ///
   639     ///\note p.run(s) is just a shortcut of the following code.
   640     ///\code
   641     ///  p.init();
   642     ///  p.addSource(s);
   643     ///  p.start();
   644     ///\endcode
   645     ///\note If the graph has more than one components, the method
   646     ///will compute the minimun spanning tree for only one component.
   647     ///
   648     ///See \ref run() if you want to compute the minimal spanning forest.
   649     void run(Node s){
   650       init();
   651       addSource(s);
   652       start();
   653     }
   654     
   655     ///@}
   656 
   657     ///\name Query Functions
   658     ///The result of the %Prim algorithm can be obtained using these
   659     ///functions.\n
   660     ///Before the use of these functions,
   661     ///either run() or start() must be called.
   662     
   663     ///@{
   664 
   665     ///\brief Returns the 'previous edge' of the minimum spanning tree.
   666 
   667     ///For a node \c v it returns the 'previous edge' of the minimum
   668     ///spanning tree, i.e. it returns the edge from where \c v was
   669     ///reached. For a source node or an unreachable node it is \ref
   670     ///INVALID.  The minimum spanning tree used here is equal to the
   671     ///minimum spanning tree used in \ref predNode().  
   672     ///\pre \ref run() or \ref start() must be called before using
   673     ///this function.
   674     UEdge predEdge(Node v) const { return (*_pred)[v]; }
   675 
   676     ///\brief Returns the 'previous node' of the minimum spanning
   677     ///tree.
   678     ///
   679     ///For a node \c v it returns the 'previous node' of the minimum
   680     ///spanning tree, i.e. it returns the node from where \c v was
   681     ///reached. For a source node or an unreachable node it is \ref
   682     ///INVALID.  //The minimum spanning tree used here is equal to the
   683     ///minimum spanning tree used in \ref predEdge().  
   684     ///\pre \ref run() or \ref start() must be called before using
   685     ///this function.
   686     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   687 				  graph->source((*_pred)[v]); }
   688     
   689     ///\brief Returns a reference to the NodeMap of the edges of the
   690     ///minimum spanning tree.
   691     ///
   692     ///Returns a reference to the NodeMap of the edges of the minimum
   693     ///spanning tree.
   694     ///\pre \ref run() or \ref start() must be called before using
   695     ///this function.
   696     const PredMap &predMap() const { return *_pred;}
   697  
   698     ///\brief Returns a reference to the tree edges map.
   699 
   700     ///Returns a reference to the TreeEdgeMap of the edges of the
   701     ///minimum spanning tree. The value of the map is \c true only if
   702     ///the edge is in the minimum spanning tree.
   703     ///
   704     ///\warning By default, the TreeEdgeMap is a NullMap.
   705     ///
   706     ///If it is not set before the execution of the algorithm, use the
   707     ///\ref treeMap(TreeMap&) function (after the execution) to set an
   708     ///UEdgeMap with the edges of the minimum spanning tree in O(n)
   709     ///time where n is the number of nodes in the graph.
   710     ///\pre \ref run() or \ref start() must be called before using
   711     ///this function.
   712     const TreeMap &treeMap() const { return *_tree;}
   713  
   714     ///\brief Sets the tree edges map.
   715     ///
   716     ///Sets the TreeMap of the edges of the minimum spanning tree.
   717     ///The map values belonging to the edges of the minimum
   718     ///spanning tree are set to \c tree_edge_value or \c true by default,
   719     ///the other map values remain untouched.
   720     ///
   721     ///\pre \ref run() or \ref start() must be called before using
   722     ///this function.
   723 
   724     template<class TreeMap>
   725     void quickTreeEdges(TreeMap& tree) const {
   726       for(NodeIt i(*graph);i!=INVALID;++i){
   727         if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],true);
   728       }
   729     }
   730 
   731     ///\brief Sets the tree edges map.
   732     ///
   733     ///Sets the TreeMap of the edges of the minimum spanning tree.
   734     ///The map values belonging to the edges of the minimum
   735     ///spanning tree are set to \c tree_edge_value or \c true by default while
   736     ///the edge values not belonging to the minimum spanning tree are set to
   737     ///\c tree_default_value or \c false by default.
   738     ///
   739     ///\pre \ref run() or \ref start() must be called before using
   740     ///this function.
   741     template <class TreeMap>
   742     void treeEdges(TreeMap& tree) const {
   743       typedef typename ItemSetTraits<UGraph,UEdge>::ItemIt TreeMapIt;
   744       for(TreeMapIt i(*graph); i != INVALID; ++i) {
   745 	tree.set(i,false);
   746       }
   747       for(NodeIt i(*graph); i != INVALID; ++i){
   748         if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true);
   749       }
   750     }
   751 
   752     ///\brief Checks if a node is reachable from the starting node.
   753     ///
   754     ///Returns \c true if \c v is reachable from the starting node.
   755     ///\warning The source nodes are inditated as unreached.
   756     ///\pre \ref run() or \ref start() must be called before using
   757     ///this function.
   758     ///
   759     bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
   760 
   761     ///\brief Checks if a node is processed.
   762     ///
   763     ///Returns \c true if \c v is processed, i.e. \c v is already
   764     ///connencted to the minimum spanning tree.  \pre \ref run() or
   765     ///\ref start() must be called before using this function.
   766     bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
   767     
   768 
   769     ///\brief Checks if an edge is in the spanning tree or not.
   770     ///
   771     ///Checks if an edge is in the spanning tree or not.
   772     ///\param e is the edge that will be checked
   773     ///\return \c true if e is in the spanning tree, \c false otherwise
   774     bool tree(UEdge e){
   775       return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
   776     }
   777 
   778     ///\brief Returns the value of the total cost of the spanning tree.
   779     ///
   780     /// Returns the value of the total cost of the spanning tree.
   781     Value treeValue() const {
   782       Value value = 0;
   783       for(NodeIt i(*graph); i!= INVALID; ++i){
   784         if ((*_pred)[i] != INVALID) value += (*cost)[(*_pred)[i]];
   785       }
   786       return value;
   787     }
   788     ///@}
   789   };
   790 
   791 
   792   /// \ingroup spantree
   793   ///
   794   /// \brief Function type interface for Prim algorithm.
   795   ///
   796   /// Function type interface for Prim algorithm.
   797   /// \param graph the UGraph that the algorithm runs on
   798   /// \param cost the CostMap of the edges
   799   /// \retval tree the EdgeMap that contains whether an edge is in 
   800   /// the spanning tree or not
   801   /// \return The total cost of the spanning tree
   802   ///
   803   ///\sa Prim
   804   template<class Graph,class CostMap,class TreeMap>
   805   typename CostMap::Value prim(const Graph& graph, 
   806                                const CostMap& cost,
   807                                TreeMap& tree){
   808     typename Prim<Graph,CostMap>::
   809       template DefTreeMap<TreeMap>::
   810       Create prm(graph,cost);
   811     prm.treeMap(tree);
   812     prm.run();
   813     return prm.treeValue();
   814   }
   815 
   816   /// \ingroup spantree
   817   ///
   818   /// \brief Function type interface for Prim algorithm.
   819   ///
   820   /// Function type interface for Prim algorithm.
   821   /// \param graph the UGraph that the algorithm runs on
   822   /// \param cost the CostMap of the edges
   823   /// the spanning tree or not
   824   /// \return The total cost of the spanning tree
   825   ///
   826   ///\sa Prim
   827   template<class Graph,class CostMap,class TreeMap>
   828   typename CostMap::Value prim(const Graph& graph, 
   829                                const CostMap& cost){
   830     typename Prim<Graph,CostMap>::
   831       Create prm(graph,cost);
   832     prm.run();
   833     return prm.treeValue();
   834   }
   835 
   836 } //END OF NAMESPACE LEMON
   837 
   838 #endif