deba@1912: /* -*- C++ -*-
deba@1912: *
alpar@1956: * This file is a part of LEMON, a generic C++ optimization library
alpar@1956: *
alpar@2391: * Copyright (C) 2003-2007
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:
alpar@2260: #include <lemon/concepts/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@2042: ///\param CM Type of cost map.
deba@2042: template<class GR, class CM>
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<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@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<int>". 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<GR,CM>".
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 <typename GR,
deba@2042: typename CM,
deba@1912: typename TR>
deba@1912: #else
deba@1912: template <typename GR=ListUGraph,
deba@2042: typename CM=typename GR::template UEdgeMap<int>,
deba@2042: typename TR=FredmanTarjanDefaultTraits<GR,CM> >
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 <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@2050: template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef,
deba@2050: class ProcessedMap,class PredMap>
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<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@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<class SrcGraph,class OrigMap,class ProcessedMap>
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<int> HeapCrossRef;
deba@1912: typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
deba@1912: HeapCrossRef crossref(graph,-1);
mqrelly@2263: FibHeap<Value,HeapCrossRef> heap(crossref);
deba@1912: PredMap pred(graph,INVALID);
deba@1912: int rate=2*edgenum/countNodes(graph);
deba@2050: int limit=(rate>std::numeric_limits<int>::digits)?
deba@2050: 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@2050: processNextTree(graph,orig,heap,crossref,
deba@2050: processed,pred,tree_counter,limit);
deba@1912: }
deba@1912: }
deba@1912: }
deba@1912:
deba@2050: template<class SrcGraph,class DestGraph,class SrcOrigMap,
deba@2050: class DestOrigMap,class ProcessedMap>
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<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@2050: radixSort(edges.begin(),edges.end(),
deba@2050: mapFunctor(composeMap(processed,sourceMap(srcgraph))));
deba@2050: counterSort(edges.begin(),edges.end(),
deba@2050: 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@2050: while (i+1!=(int)edges.size() &&
deba@2050: 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@2050: destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=
deba@2050: 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: {
alpar@2260: checkConcept<concepts::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