deba@1912: /* -*- C++ -*- deba@1912: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 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 deba@1912: #include deba@1912: deba@1912: #include deba@1912: #include deba@1912: #include deba@1912: #include deba@1993: #include deba@1912: #include deba@1912: #include deba@1993: #include deba@1912: #include deba@1912: alpar@2260: #include 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@2042: ///\param CM Type of cost map. deba@2042: template 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. alpar@2260: ///It must meet the \ref concepts::ReadMap "ReadMap" concept. deba@2042: typedef CM CostMap; deba@1912: //The type of the cost of the edges. deba@2042: typedef typename CM::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. alpar@2260: ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. deba@1912: ///By default it is a BoolEdgeMap. deba@1912: typedef typename UGraph::template UEdgeMap 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@2042: /// \ingroup spantree deba@1912: /// deba@2042: ///This class provides an efficient implementation of %FredmanTarjan deba@2042: ///algorithm whitch is sometimes a bit quicker than the Prim deba@2042: ///algorithm on larger graphs. Due to the structure of the deba@2042: ///algorithm, it has less controll functions than Prim. deba@1912: /// deba@2042: /// The running time is \f$ O(e\beta(e,n)) \f$ where deba@2042: /// \f$ \beta(e,n) = \min\{ i | \log^{i}(n) \le e/n\} \f$ and deba@2042: /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f$ deba@1912: /// deba@2042: ///The edge costs are passed to the algorithm using a \ref alpar@2260: ///concepts::ReadMap "ReadMap", so it is easy to change it to any deba@2042: ///kind of cost. deba@2042: /// deba@2042: ///The type of the cost is determined by the \ref alpar@2260: ///concepts::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@2042: ///FredmanTarjan, it is only passed to \ref deba@1912: ///FredmanTarjanDefaultTraits. deba@1912: /// deba@2042: ///\param CM This read-only UEdgeMap determines the costs of the deba@2042: ///edges. It is read once for each edge, so the map may involve in deba@2042: ///relatively time consuming process to compute the edge cost if it deba@2042: ///is necessary. The default map type is \ref alpar@2260: ///concepts::UGraph::UEdgeMap "UGraph::UEdgeMap". The value of deba@2042: ///CM is not used directly by FredmanTarjan, it is only passed to deba@2042: ///\ref FredmanTarjanDefaultTraits. deba@2042: /// deba@2042: ///\param TR Traits class to set various data types used by the deba@2042: ///algorithm. The default traits class is \ref deba@2042: ///FredmanTarjanDefaultTraits "FredmanTarjanDefaultTraits". deba@2042: ///See \ref FredmanTarjanDefaultTraits for the documentation of a deba@2042: ///FredmanTarjan traits class. deba@1912: /// deba@1912: ///\author Balazs Attila Mihaly deba@1912: deba@1912: #ifdef DOXYGEN deba@1912: template deba@1912: #else deba@1912: template , deba@2042: typename TR=FredmanTarjanDefaultTraits > deba@1912: #endif deba@1912: class FredmanTarjan { deba@1912: public: deba@2042: ///\brief \ref Exception for uninitialized parameters. deba@2042: /// deba@2042: ///This error represents problems in the initialization deba@2042: ///of the parameters of the algorithms. deba@1912: class UninitializedParameter : public lemon::UninitializedParameter { deba@1912: public: alpar@2151: virtual const char* what() const throw() { 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 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@2490: ///\brief \ref named-templ-param "Named parameter" for setting TreeMap deba@2490: /// deba@1912: ///\ref named-templ-param "Named parameter" for setting TreeMap deba@1912: /// deba@1912: template deba@1912: struct DefTreeMap deba@1912: : public FredmanTarjan< UGraph, CostMap, DefTreeMapTraits > { deba@1912: typedef FredmanTarjan< UGraph, CostMap, DefTreeMapTraits > 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@2050: template deba@2050: void processNextTree(const SrcGraph& graph,const OrigMap& orig, deba@2050: Heap &heap, HeapCrossRef& crossref, deba@2050: ProcessedMap& processed,PredMap& pred, deba@2050: int& tree_counter,const int limit){ deba@1912: std::vector 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]]set(orig[pred[tree_nodes[i]]],true); deba@1912: processed.set(tree_nodes[i],tree_index); deba@2050: crossref[tree_nodes[i]] = Heap::PRE_HEAP; deba@1912: } deba@1912: processed.set(tree_nodes[0],tree_index); deba@2050: crossref[tree_nodes[0]] = Heap::PRE_HEAP; deba@1912: while (!heap.empty()) { deba@1912: typename SrcGraph::Node v=heap.top(); deba@1912: heap.pop(); deba@2050: crossref[v] = Heap::PRE_HEAP; deba@1912: } deba@2050: heap.clear(); deba@1912: if(!stop)++tree_counter; deba@1912: } deba@1912: deba@1912: template deba@2050: void createTrees(const SrcGraph& graph, const OrigMap& orig, deba@2050: ProcessedMap& processed, deba@2050: 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 HeapCrossRef; deba@1912: typedef typename SrcGraph::template NodeMap PredMap; deba@1912: HeapCrossRef crossref(graph,-1); mqrelly@2263: FibHeap heap(crossref); deba@1912: PredMap pred(graph,INVALID); deba@1912: int rate=2*edgenum/countNodes(graph); deba@2050: int limit=(rate>std::numeric_limits::digits)? deba@2050: std::numeric_limits::max() : (1< deba@2050: void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig, deba@2050: DestGraph& destgraph,DestOrigMap& destorig, deba@2050: 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 edges; deba@1912: std::vector nodes(tree_counter, INVALID); deba@1912: for(EdgeIt i(srcgraph);i!=INVALID;++i){ deba@1912: if(processed[srcgraph.source(i)](*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@2050: destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]= deba@2050: srcorig[minpos]; deba@1912: } deba@1912: } deba@1912: deba@1912: template deba@1912: void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){ deba@1912: int tree_counter = 0; deba@1912: typename SrcGraph::template NodeMap processed(graph,-1); deba@1912: SmartUGraph destgraph; deba@1912: SmartUGraph::UEdgeMap 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: { alpar@2260: checkConcept(); 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 (*this) 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 (*this) 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(),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 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 deba@1912: void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){ deba@1912: typename FredmanTarjan::template DefTreeMap:: 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