deba@1912: /* -*- C++ -*-
deba@1912:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1912:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1912:  *
deba@1912:  * Permission to use, modify and distribute this software is granted
deba@1912:  * provided that this copyright notice appears in all copies. For
deba@1912:  * precise terms see the accompanying LICENSE file.
deba@1912:  *
deba@1912:  * This software is provided "AS IS" with no warranty of any kind,
deba@1912:  * express or implied, and with no claim as to its suitability for any
deba@1912:  * purpose.
deba@1912:  *
deba@1912:  */
deba@1912: 
deba@1912: #ifndef LEMON_FREDMAN_TARJAN_H
deba@1912: #define LEMON_FREDMAN_TARJAN_H
deba@1912: 
deba@1912: ///\ingroup spantree
deba@1912: ///\file
deba@1912: ///\brief FredmanTarjan algorithm to compute minimum spanning forest.
deba@1912: 
deba@1912: #include <limits>
deba@1912: #include <vector>
deba@1912: 
deba@1912: #include <lemon/list_graph.h>
deba@1912: #include <lemon/smart_graph.h>
deba@1912: #include <lemon/fib_heap.h>
deba@1912: #include <lemon/radix_sort.h>
deba@1993: #include <lemon/bits/invalid.h>
deba@1912: #include <lemon/error.h>
deba@1912: #include <lemon/maps.h>
deba@1993: #include <lemon/bits/traits.h>
deba@1912: #include <lemon/graph_utils.h>
deba@1912: 
deba@1912: #include <lemon/concept/ugraph.h>
deba@1912: 
deba@1912: namespace lemon {
deba@1912: 
deba@1912:   ///Default traits class of FredmanTarjan class.
deba@1912: 
deba@1912:   ///Default traits class of FredmanTarjan class.
deba@1912:   ///\param GR Graph type.
deba@1912:   ///\param LM Type of cost map.
deba@1912:   template<class GR, class LM>
deba@1912:   struct FredmanTarjanDefaultTraits{
deba@1912:     ///The graph type the algorithm runs on. 
deba@1912:     typedef GR UGraph;
deba@1912:     ///The type of the map that stores the edge costs.
deba@1912: 
deba@1912:     ///The type of the map that stores the edge costs.
deba@1912:     ///It must meet the \ref concept::ReadMap "ReadMap" concept.
deba@1912:     typedef LM CostMap;
deba@1912:     //The type of the cost of the edges.
deba@1912:     typedef typename LM::Value Value;
deba@1912:     ///The type of the map that stores whether an edge is in the
deba@1912:     ///spanning tree or not.
deba@1912: 
deba@1912:     ///The type of the map that stores whether an edge is in the
deba@1912:     ///spanning tree or not.
deba@1912:     ///It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept.
deba@1912:     ///By default it is a BoolEdgeMap.
deba@1912:     typedef typename UGraph::template UEdgeMap<bool> TreeMap;
deba@1912:     ///Instantiates a TreeMap.
deba@1912: 
deba@1912:     ///This function instantiates a \ref TreeMap.
alpar@1946:     ///\param _graph is the graph, to which
deba@1912:     ///we would like to define the \ref TreeMap
deba@1912:     static TreeMap *createTreeMap(const GR &_graph){
deba@1912:       return new TreeMap(_graph);
deba@1912:     }
deba@1912:   };
deba@1912:   
deba@1912:   ///%FredmanTarjan algorithm class to find a minimum spanning tree.
deba@1912:   
deba@1912:   /// \ingroup spantree
deba@1912:   ///This class provides an efficient implementation of %FredmanTarjan algorithm
deba@1912:   ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs.
deba@1912:   ///Due to the structure of the algorithm, it has less controll functions than
deba@1912:   ///Prim.
deba@1912:   ///
deba@1912:   ///The running time is O(e*B(e,n)) where e is the number of edges, n is the
deba@1912:   ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n}
deba@1912:   ///( log^(i+1) n = log(log^(i)) n )
deba@1912:   ///
deba@1912:   ///The edge costs are passed to the algorithm using a
deba@1912:   ///\ref concept::ReadMap "ReadMap",
deba@1912:   ///so it is easy to change it to any kind of cost.
deba@1912:   ///
deba@1912:   ///The type of the cost is determined by the
deba@1912:   ///\ref concept::ReadMap::Value "Value" of the cost map.
deba@1912:   ///
deba@1912:   ///\param GR The graph type the algorithm runs on. The default value
deba@1912:   ///is \ref ListUGraph. The value of GR is not used directly by
deba@1912:   ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits.
deba@1912:   ///
deba@1912:   ///\param LM This read-only UEdgeMap determines the costs of the
deba@1912:   ///edges. It is read once for each edge, so the map may involve in
deba@1912:   ///relatively time consuming process to compute the edge cost if
deba@1912:   ///it is necessary. The default map type is \ref
deba@1912:   ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value
deba@1912:   ///of LM is not used directly by FredmanTarjan, it is only passed to \ref
deba@1912:   ///FredmanTarjanDefaultTraits.
deba@1912:   ///
deba@1912:   ///\param TR Traits class to set
deba@1912:   ///various data types used by the algorithm.  The default traits
deba@1912:   ///class is \ref FredmanTarjanDefaultTraits
deba@1912:   ///"FredmanTarjanDefaultTraits<GR,LM>".  See \ref
deba@1912:   ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits
deba@1912:   ///class.
deba@1912:   ///
deba@1912:   ///\author Balazs Attila Mihaly
deba@1912: 
deba@1912: #ifdef DOXYGEN
deba@1912:   template <typename GR,
deba@1912: 	    typename LM,
deba@1912: 	    typename TR>
deba@1912: #else
deba@1912:   template <typename GR=ListUGraph,
deba@1912: 	    typename LM=typename GR::template UEdgeMap<int>,
deba@1912: 	    typename TR=FredmanTarjanDefaultTraits<GR,LM> >
deba@1912: #endif
deba@1912:   class FredmanTarjan {
deba@1912:   public:
deba@1912:     /**
deba@1912:      * \brief \ref Exception for uninitialized parameters.
deba@1912:      *
deba@1912:      * This error represents problems in the initialization
deba@1912:      * of the parameters of the algorithms.
deba@1912:      */
deba@1912:     class UninitializedParameter : public lemon::UninitializedParameter {
deba@1912:     public:
deba@1912:       virtual const char* exceptionName() const {
deba@1912: 	return "lemon::FredmanTarjan::UninitializedParameter";
deba@1912:       }
deba@1912:     };
deba@1912: 
deba@1912:     typedef GR Graph;
deba@1912:     typedef TR Traits;
deba@1912:     ///The type of the underlying graph.
deba@1912:     typedef typename TR::UGraph UGraph;
deba@1912:     ///\e
deba@1912:     typedef typename UGraph::Node Node;
deba@1912:     ///\e
deba@1912:     typedef typename UGraph::NodeIt NodeIt;
deba@1912:     ///\e
deba@1912:     typedef typename UGraph::UEdge UEdge;
deba@1912:     ///\e
deba@1912:     typedef typename UGraph::UEdgeIt UEdgeIt;
deba@1912:     ///\e
deba@1912:     typedef typename UGraph::IncEdgeIt IncEdgeIt;
deba@1912:     
deba@1912:     ///The type of the cost of the edges.
deba@1912:     typedef typename TR::CostMap::Value Value;
deba@1912:     ///The type of the map that stores the edge costs.
deba@1912:     typedef typename TR::CostMap CostMap;
deba@1912:     ///Edges of the spanning tree.
deba@1912:     typedef typename TR::TreeMap TreeMap;
deba@1912:   private:
deba@1912:     ///Pointer to the underlying graph.
deba@1912:     const UGraph *graph;
deba@1912:     ///Pointer to the cost map
deba@1912:     const CostMap *cost;
deba@1912:     ///Pointer to the map of tree edges.
deba@1912:     TreeMap *_tree;
deba@1912:     ///Indicates if \ref _tree is locally allocated (\c true) or not.
deba@1912:     bool local_tree;
deba@1912: 
deba@1912:     ///Creates the maps if necessary.
deba@1912:     
deba@1912:     void create_maps(){
deba@1912:       if(!_tree){
deba@1912: 	local_tree=true;
deba@1912: 	_tree=Traits::createTreeMap(*graph);
deba@1912:       }
deba@1912:     }
deba@1912:     
deba@1912:   public :
deba@1912: 
deba@1912:     typedef FredmanTarjan Create;
deba@1912:  
deba@1912:     ///\name Named template parameters
deba@1912: 
deba@1912:     ///@{
deba@1912: 
deba@1912:     template <class TM>
deba@1912:     struct DefTreeMapTraits : public Traits {
deba@1912:       typedef TM TreeMap;
deba@1912:       static TreeMap *createTreeMap(const UGraph &) {
deba@1912: 	throw UninitializedParameter();
deba@1912:       }
deba@1912:     };
deba@1912:     ///\ref named-templ-param "Named parameter" for setting TreeMap 
deba@1912: 
deba@1912:     ///\ref named-templ-param "Named parameter" for setting TreeMap
deba@1912:     ///
deba@1912:     template <class TM>
deba@1912:     struct DefTreeMap
deba@1912:       : public FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > { 
deba@1912:       typedef FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
deba@1912:     };
deba@1912: 
deba@1912:     ///@}
deba@1912: 
deba@1912: 
deba@1912:   protected:
deba@1912: 
deba@1912:     FredmanTarjan() {}
deba@1912: 
deba@1912:   private:
deba@1912: 
deba@1912:     template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
deba@1912:     void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
deba@1912: 	ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
deba@1912:       std::vector<typename SrcGraph::Node> tree_nodes;
deba@1912:       int tree_index=tree_counter;
deba@1912:       bool stop=false;
deba@1912:       while(!heap.empty() && !stop){
deba@1912:         typename SrcGraph::Node v=heap.top();
deba@1912:         heap.pop();
deba@1912: 	if(processed[v]!=-1){
deba@1912: 	  heap.state(v,Heap::PRE_HEAP);
deba@1912: 	  tree_index=processed[v];
deba@1912: 	  _tree->set(orig[pred[v]],true);
deba@1912: 	  stop=true;
deba@1912: 	  break;
deba@1912:         }
deba@1912: 	tree_nodes.push_back(v);
deba@1912: 	for(typename SrcGraph::IncEdgeIt e(graph,v);e!=INVALID;++e){
deba@1912: 	  typename SrcGraph::Node w=graph.oppositeNode(v,e);
deba@1912: 	  switch(heap.state(w)){
deba@1912: 	  case Heap::PRE_HEAP:
deba@1912: 	    if(heap.size()>=limit){
deba@1912: 	      stop=true;
deba@1912: 	    }
deba@1912: 	    else{
deba@1912: 	      heap.push(w,(*cost)[orig[e]]);
deba@1912: 	      pred.set(w,e);
deba@1912: 	    }
deba@1912: 	    break;
deba@1912: 	  case Heap::IN_HEAP:
deba@1912: 	    if ((*cost)[orig[e]]<heap[w]){
deba@1912: 	      heap.decrease(w,(*cost)[orig[e]]); 
deba@1912: 	      pred.set(w,e);
deba@1912: 	    }
deba@1912: 	    break;
deba@1912: 	  case Heap::POST_HEAP:
deba@1912: 	    break;
deba@1912: 	  }
deba@1912: 	}
deba@1912:       }
deba@1912:       for(int i=1;i<(int)tree_nodes.size();++i){
deba@1912: 	_tree->set(orig[pred[tree_nodes[i]]],true);
deba@1912:         processed.set(tree_nodes[i],tree_index);
deba@1912:         heap.state(tree_nodes[i], Heap::PRE_HEAP);
deba@1912:       }
deba@1912:       processed.set(tree_nodes[0],tree_index);
deba@1912:       heap.state(tree_nodes[0],Heap::PRE_HEAP);
deba@1912:       while (!heap.empty()) {
deba@1912:         typename SrcGraph::Node v=heap.top();
deba@1912: 	heap.pop();
deba@1912:         heap.state(v,Heap::PRE_HEAP);
deba@1912:       }
deba@1912:       if(!stop)++tree_counter;
deba@1912:     }
deba@1912: 
deba@1912:     template<class SrcGraph,class OrigMap,class ProcessedMap>
deba@1912:     void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
deba@1912: 	int edgenum,int& tree_counter){
deba@1912:       typedef typename SrcGraph::Node Node;
deba@1912:       typedef typename SrcGraph::UEdge UEdge;
deba@1912:       typedef typename SrcGraph::NodeIt NodeIt;
deba@1912:       typedef typename SrcGraph::template NodeMap<int> HeapCrossRef;
deba@1912:       typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
deba@1912:       HeapCrossRef crossref(graph,-1);
deba@1912:       FibHeap<Node,Value,HeapCrossRef> heap(crossref);
deba@1912:       PredMap pred(graph,INVALID);
deba@1912:       int rate=2*edgenum/countNodes(graph);
deba@1912:       int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
deba@1912:       for(NodeIt i(graph);i!=INVALID;++i){
deba@1912: 	if(processed[i]==-1){
deba@1912: 	  heap.push(i, Value());
deba@1912: 	  processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
deba@1912: 	}
deba@1912:       }
deba@1912:     }
deba@1912: 
deba@1912:     template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
deba@1912:     void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
deba@1912: 	DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
deba@1912:       typedef typename SrcGraph::Node Node;
deba@1912:       typedef typename DestGraph::Node DNode;
deba@1912:       typedef typename SrcGraph::UEdge UEdge;
deba@1912:       typedef typename DestGraph::UEdge DUEdge;
deba@1912:       typedef typename SrcGraph::Edge Edge;
deba@1912:       typedef typename SrcGraph::EdgeIt EdgeIt;
deba@1912:       std::vector<Edge> edges;
deba@1912:       std::vector<DNode> nodes(tree_counter, INVALID);
deba@1912:       for(EdgeIt i(srcgraph);i!=INVALID;++i){
deba@1912: 	if(processed[srcgraph.source(i)]<processed[srcgraph.target(i)]){
deba@1912: 	  edges.push_back(i);
deba@1912:           if(nodes[processed[srcgraph.source(i)]]==INVALID) {
deba@1912: 	    nodes[processed[srcgraph.source(i)]]=destgraph.addNode();
deba@1912: 	  }
deba@1912:           if(nodes[processed[srcgraph.target(i)]]==INVALID) {
deba@1912: 	    nodes[processed[srcgraph.target(i)]]=destgraph.addNode();
deba@1912: 	  }
deba@1912: 	}
deba@1912:       }
deba@1912:       
deba@1912:       radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
deba@1912:       counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
deba@1912:       for(int i=0;i!=(int)edges.size();++i){
deba@1912: 	int srcproc=processed[srcgraph.source(edges[i])];
deba@1912: 	int trgproc=processed[srcgraph.target(edges[i])];
deba@1912:         Value minval=(*cost)[srcorig[edges[i]]];
deba@1912:         UEdge minpos=edges[i];
deba@1912: 	while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
deba@1912: 	  trgproc==processed[srcgraph.target(edges[i+1])]) {
deba@1912: 	  if (minval>(*cost)[srcorig[edges[i+1]]]) {
deba@1912:             minval=(*cost)[srcorig[edges[i+1]]];
deba@1912:             minpos=edges[i+1];
deba@1912: 	  }
deba@1912:           ++i;
deba@1912: 	} 
deba@1912: 	destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
deba@1912:       }
deba@1912:     }
deba@1912: 
deba@1912:     template<class SrcGraph,class OrigMap>
deba@1912:     void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){
deba@1912:       int tree_counter = 0;
deba@1912:       typename SrcGraph::template NodeMap<int> processed(graph,-1);
deba@1912:       SmartUGraph destgraph;
deba@1912:       SmartUGraph::UEdgeMap<typename OrigMap::Value> destorig(destgraph);
deba@1912:       createTrees(graph,orig,processed,edgenum,tree_counter);
deba@1912:       collect(graph,orig,destgraph,destorig,processed,tree_counter);
deba@1912:       if (countNodes(destgraph)>1) {
deba@1912:         phase(destgraph,destorig,edgenum);
deba@1912:       }
deba@1912:     }
deba@1912: 
deba@1912:   public:      
deba@1912:     
deba@1912:     ///Constructor.
deba@1912:     
deba@1912:     ///\param _graph the graph the algorithm will run on.
deba@1912:     ///\param _cost the cost map used by the algorithm.
deba@1912:     FredmanTarjan(const UGraph& _graph, const CostMap& _cost) :
deba@1912:       graph(&_graph), cost(&_cost),
deba@1912:       _tree(0), local_tree(false)
deba@1912:     {
deba@1912:       checkConcept<concept::UGraph, UGraph>();
deba@1912:     }
deba@1912:     
deba@1912:     ///Destructor.
deba@1912:     ~FredmanTarjan(){
deba@1912:       if(local_tree) delete _tree;
deba@1912:     }
deba@1912: 
deba@1912:     ///Sets the cost map.
deba@1912: 
deba@1912:     ///Sets the cost map.
deba@1912:     ///\return <tt> (*this) </tt>
deba@1912:     FredmanTarjan &costMap(const CostMap &m){
deba@1912:       cost = &m;
deba@1912:       return *this;
deba@1912:     }
deba@1912: 
deba@1912:     ///Sets the map storing the tree edges.
deba@1912: 
deba@1912:     ///Sets the map storing the tree edges.
deba@1912:     ///If you don't use this function before calling \ref run(),
deba@1912:     ///it will allocate one. The destuctor deallocates this
deba@1912:     ///automatically allocated map, of course.
deba@1912:     ///By default this is a BoolEdgeMap.
deba@1912:     ///\return <tt> (*this) </tt>
deba@1912:     FredmanTarjan &treeMap(TreeMap &m){
deba@1912:       if(local_tree) {
deba@1912: 	delete _tree;
deba@1912: 	local_tree=false;
deba@1912:       }
deba@1912:       _tree = &m;
deba@1912:       return *this;
deba@1912:     }
deba@1912: 
deba@1912:   public:
deba@1912:     ///\name Execution control
deba@1912:     ///The simplest way to execute the algorithm is to use
deba@1912:     ///one of the member functions called \c run(...).
deba@1912: 
deba@1912:     ///@{
deba@1912: 
deba@1912:     ///Initializes the internal data structures.
deba@1912: 
deba@1912:     ///Initializes the internal data structures.
deba@1912:     ///
deba@1912:     void init(){
deba@1912:       create_maps();
deba@1912:       for(typename Graph::UEdgeIt i(*graph);i!=INVALID;++i){
deba@1912: 	_tree->set(i,false);
deba@1912:       }
deba@1912:     }
deba@1912: 
deba@1912:     ///Executes the algorithm.
deba@1912: 
deba@1912:     ///Executes the algorithm.
deba@1912:     ///
deba@1912:     ///\pre init() must be called and at least one node should be added
deba@1912:     ///with addSource() before using this function.
deba@1912:     ///
deba@1912:     ///This method runs the %FredmanTarjan algorithm from the node(s)
deba@1912:     ///in order to compute the
deba@1912:     ///minimum spanning tree.
deba@1912:     void start(){
deba@1912: 	phase(*graph,identityMap<UEdge>(),countEdges(*graph));
deba@1912:     }
deba@1912:     
deba@1912:     ///Runs %FredmanTarjan algorithm.
deba@1912:     
deba@1912:     ///This method runs the %FredmanTarjan algorithm
deba@1912:     ///in order to compute the minimum spanning forest.
deba@1912:     ///
deba@1912:     ///\note ft.run() is just a shortcut of the following code.
deba@1912:     ///\code
deba@1912:     ///  ft.init();
deba@1912:     ///  ft.start();
deba@1912:     ///\endcode
deba@1912:     void run() {
deba@1912:       init();
deba@1912:       start();
deba@1912:     }
deba@1912: 
deba@1912:     ///@}
deba@1912: 
deba@1912:     ///\name Query Functions
deba@1912:     ///The result of the %FredmanTarjan algorithm can be obtained using these
deba@1912:     ///functions.\n
deba@1912:     ///Before the use of these functions,
deba@1912:     ///either run() or start() must be called.
deba@1912:     
deba@1912:     ///@{
deba@1912: 
deba@1912:     ///Returns a reference to the tree edges map.
deba@1912: 
deba@1912:     ///Returns a reference to the TreeEdgeMap of the edges of the
deba@1912:     ///minimum spanning tree. The value of the map is \c true only if the 
deba@1912:     ///edge is in the minimum spanning tree.
deba@1912:     ///
deba@1912:     ///\pre \ref run() or \ref start() must be called before using this 
deba@1912:     ///function.
deba@1912:     const TreeMap &treeMap() const { return *_tree;}
deba@1912:  
deba@1912:     ///Sets the tree edges map.
deba@1912: 
deba@1912:     ///Sets the TreeMap of the edges of the minimum spanning tree.
deba@1912:     ///The map values belonging to the edges of the minimum
alpar@1953:     ///spanning tree are set to \c tree_edge_value or \c true by default 
deba@1912:     ///while the edge values not belonging to the minimum spanning tree are 
deba@1912:     ///set to
alpar@1953:     ///\c tree_default_value or \c false by default.
deba@1912:     ///
deba@1912:     ///\pre \ref run() or \ref start() must be called before using this 
deba@1912:     ///function.
deba@1912: 
deba@1912:     template<class TreeMap>
deba@1912:     void treeEdges(
deba@1912:         TreeMap& tree,
deba@1912:         const typename TreeMap::Value& tree_edge_value=true,
deba@1912:         const typename TreeMap::Value& tree_default_value=false) const {
deba@1912:       for(typename UGraph::UEdgeIt i(*graph);i!=INVALID;++i){
deba@1912: 	(*_tree)[i]?tree.set(i,tree_edge_value):tree.set(i,tree_default_value);
deba@1912:       }
deba@1912:     }
deba@1912: 
deba@1912:     ///\brief Checks if an edge is in the spanning tree or not.
deba@1912: 
deba@1912:     ///Checks if an edge is in the spanning tree or not.
deba@1912:     ///\param e is the edge that will be checked
deba@1912:     ///\return \c true if e is in the spanning tree, \c false otherwise
deba@1912:     bool tree(UEdge e){
deba@1912:       return (*_tree)[e];
deba@1912:     }
deba@1912:     ///@}
deba@1912:   };
deba@1912: 
deba@1912:   /// \ingroup spantree
deba@1912:   ///
deba@1912:   /// \brief Function type interface for FredmanTarjan algorithm.
deba@1912:   ///
deba@1912:   /// Function type interface for FredmanTarjan algorithm.
deba@1912:   /// \param graph the UGraph that the algorithm runs on
deba@1912:   /// \param cost the CostMap of the edges
deba@1912:   /// \retval tree the EdgeMap that contains whether an edge is in the 
deba@1912:   /// spanning tree or not
deba@1912:   ///
deba@1912:   /// \sa Prim
deba@1912:   template<class Graph,class CostMap,class TreeMap>
deba@1912:   void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){
deba@1912:     typename FredmanTarjan<Graph,CostMap>::template DefTreeMap<TreeMap>::
deba@1912:       Create ft(graph,cost);
deba@1912:     ft.treeMap(tree);
deba@1912:     ft.run();
deba@1979:   }
deba@1912: 
deba@1912: } //END OF NAMESPACE LEMON
deba@1912: 
deba@1912: #endif