fredman_tarjan.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_FREDMAN_TARJAN_H
00020 #define LEMON_FREDMAN_TARJAN_H
00021 
00025 
00026 #include <limits>
00027 #include <vector>
00028 
00029 #include <lemon/list_graph.h>
00030 #include <lemon/smart_graph.h>
00031 #include <lemon/fib_heap.h>
00032 #include <lemon/radix_sort.h>
00033 #include <lemon/invalid.h>
00034 #include <lemon/error.h>
00035 #include <lemon/maps.h>
00036 #include <lemon/traits.h>
00037 #include <lemon/graph_utils.h>
00038 
00039 #include <lemon/concept/ugraph.h>
00040 
00041 namespace lemon {
00042 
00044 
00048   template<class GR, class LM>
00049   struct FredmanTarjanDefaultTraits{
00051     typedef GR UGraph;
00053 
00056     typedef LM CostMap;
00057     //The type of the cost of the edges.
00058     typedef typename LM::Value Value;
00061 
00066     typedef typename UGraph::template UEdgeMap<bool> TreeMap;
00068 
00072     static TreeMap *createTreeMap(const GR &_graph){
00073       return new TreeMap(_graph);
00074     }
00075   };
00076   
00078   
00116 
00117 #ifdef DOXYGEN
00118   template <typename GR,
00119             typename LM,
00120             typename TR>
00121 #else
00122   template <typename GR=ListUGraph,
00123             typename LM=typename GR::template UEdgeMap<int>,
00124             typename TR=FredmanTarjanDefaultTraits<GR,LM> >
00125 #endif
00126   class FredmanTarjan {
00127   public:
00134     class UninitializedParameter : public lemon::UninitializedParameter {
00135     public:
00136       virtual const char* exceptionName() const {
00137         return "lemon::FredmanTarjan::UninitializedParameter";
00138       }
00139     };
00140 
00141     typedef GR Graph;
00142     typedef TR Traits;
00144     typedef typename TR::UGraph UGraph;
00146     typedef typename UGraph::Node Node;
00148     typedef typename UGraph::NodeIt NodeIt;
00150     typedef typename UGraph::UEdge UEdge;
00152     typedef typename UGraph::UEdgeIt UEdgeIt;
00154     typedef typename UGraph::IncEdgeIt IncEdgeIt;
00155     
00157     typedef typename TR::CostMap::Value Value;
00159     typedef typename TR::CostMap CostMap;
00161     typedef typename TR::TreeMap TreeMap;
00162   private:
00164     const UGraph *graph;
00166     const CostMap *cost;
00168     TreeMap *_tree;
00170     bool local_tree;
00171 
00173     
00174     void create_maps(){
00175       if(!_tree){
00176         local_tree=true;
00177         _tree=Traits::createTreeMap(*graph);
00178       }
00179     }
00180     
00181   public :
00182 
00183     typedef FredmanTarjan Create;
00184  
00186 
00188 
00189     template <class TM>
00190     struct DefTreeMapTraits : public Traits {
00191       typedef TM TreeMap;
00192       static TreeMap *createTreeMap(const UGraph &) {
00193         throw UninitializedParameter();
00194       }
00195     };
00197 
00200     template <class TM>
00201     struct DefTreeMap
00202       : public FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > { 
00203       typedef FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
00204     };
00205 
00207 
00208 
00209   protected:
00210 
00211     FredmanTarjan() {}
00212 
00213   private:
00214 
00215     template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
00216     void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
00217         ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
00218       std::vector<typename SrcGraph::Node> tree_nodes;
00219       int tree_index=tree_counter;
00220       bool stop=false;
00221       while(!heap.empty() && !stop){
00222         typename SrcGraph::Node v=heap.top();
00223         heap.pop();
00224         if(processed[v]!=-1){
00225           heap.state(v,Heap::PRE_HEAP);
00226           tree_index=processed[v];
00227           _tree->set(orig[pred[v]],true);
00228           stop=true;
00229           break;
00230         }
00231         tree_nodes.push_back(v);
00232         for(typename SrcGraph::IncEdgeIt e(graph,v);e!=INVALID;++e){
00233           typename SrcGraph::Node w=graph.oppositeNode(v,e);
00234           switch(heap.state(w)){
00235           case Heap::PRE_HEAP:
00236             if(heap.size()>=limit){
00237               stop=true;
00238             }
00239             else{
00240               heap.push(w,(*cost)[orig[e]]);
00241               pred.set(w,e);
00242             }
00243             break;
00244           case Heap::IN_HEAP:
00245             if ((*cost)[orig[e]]<heap[w]){
00246               heap.decrease(w,(*cost)[orig[e]]); 
00247               pred.set(w,e);
00248             }
00249             break;
00250           case Heap::POST_HEAP:
00251             break;
00252           }
00253         }
00254       }
00255       for(int i=1;i<(int)tree_nodes.size();++i){
00256         _tree->set(orig[pred[tree_nodes[i]]],true);
00257         processed.set(tree_nodes[i],tree_index);
00258         heap.state(tree_nodes[i], Heap::PRE_HEAP);
00259       }
00260       processed.set(tree_nodes[0],tree_index);
00261       heap.state(tree_nodes[0],Heap::PRE_HEAP);
00262       while (!heap.empty()) {
00263         typename SrcGraph::Node v=heap.top();
00264         heap.pop();
00265         heap.state(v,Heap::PRE_HEAP);
00266       }
00267       if(!stop)++tree_counter;
00268     }
00269 
00270     template<class SrcGraph,class OrigMap,class ProcessedMap>
00271     void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
00272         int edgenum,int& tree_counter){
00273       typedef typename SrcGraph::Node Node;
00274       typedef typename SrcGraph::UEdge UEdge;
00275       typedef typename SrcGraph::NodeIt NodeIt;
00276       typedef typename SrcGraph::template NodeMap<int> HeapCrossRef;
00277       typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
00278       HeapCrossRef crossref(graph,-1);
00279       FibHeap<Node,Value,HeapCrossRef> heap(crossref);
00280       PredMap pred(graph,INVALID);
00281       int rate=2*edgenum/countNodes(graph);
00282       int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
00283       for(NodeIt i(graph);i!=INVALID;++i){
00284         if(processed[i]==-1){
00285           heap.push(i, Value());
00286           processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
00287         }
00288       }
00289     }
00290 
00291     template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
00292     void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
00293         DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
00294       typedef typename SrcGraph::Node Node;
00295       typedef typename DestGraph::Node DNode;
00296       typedef typename SrcGraph::UEdge UEdge;
00297       typedef typename DestGraph::UEdge DUEdge;
00298       typedef typename SrcGraph::Edge Edge;
00299       typedef typename SrcGraph::EdgeIt EdgeIt;
00300       std::vector<Edge> edges;
00301       std::vector<DNode> nodes(tree_counter, INVALID);
00302       for(EdgeIt i(srcgraph);i!=INVALID;++i){
00303         if(processed[srcgraph.source(i)]<processed[srcgraph.target(i)]){
00304           edges.push_back(i);
00305           if(nodes[processed[srcgraph.source(i)]]==INVALID) {
00306             nodes[processed[srcgraph.source(i)]]=destgraph.addNode();
00307           }
00308           if(nodes[processed[srcgraph.target(i)]]==INVALID) {
00309             nodes[processed[srcgraph.target(i)]]=destgraph.addNode();
00310           }
00311         }
00312       }
00313       
00314       radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
00315       counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
00316       for(int i=0;i!=(int)edges.size();++i){
00317         int srcproc=processed[srcgraph.source(edges[i])];
00318         int trgproc=processed[srcgraph.target(edges[i])];
00319         Value minval=(*cost)[srcorig[edges[i]]];
00320         UEdge minpos=edges[i];
00321         while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
00322           trgproc==processed[srcgraph.target(edges[i+1])]) {
00323           if (minval>(*cost)[srcorig[edges[i+1]]]) {
00324             minval=(*cost)[srcorig[edges[i+1]]];
00325             minpos=edges[i+1];
00326           }
00327           ++i;
00328         } 
00329         destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
00330       }
00331     }
00332 
00333     template<class SrcGraph,class OrigMap>
00334     void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){
00335       int tree_counter = 0;
00336       typename SrcGraph::template NodeMap<int> processed(graph,-1);
00337       SmartUGraph destgraph;
00338       SmartUGraph::UEdgeMap<typename OrigMap::Value> destorig(destgraph);
00339       createTrees(graph,orig,processed,edgenum,tree_counter);
00340       collect(graph,orig,destgraph,destorig,processed,tree_counter);
00341       if (countNodes(destgraph)>1) {
00342         phase(destgraph,destorig,edgenum);
00343       }
00344     }
00345 
00346   public:      
00347     
00349     
00352     FredmanTarjan(const UGraph& _graph, const CostMap& _cost) :
00353       graph(&_graph), cost(&_cost),
00354       _tree(0), local_tree(false)
00355     {
00356       checkConcept<concept::UGraph, UGraph>();
00357     }
00358     
00360     ~FredmanTarjan(){
00361       if(local_tree) delete _tree;
00362     }
00363 
00365 
00368     FredmanTarjan &costMap(const CostMap &m){
00369       cost = &m;
00370       return *this;
00371     }
00372 
00374 
00381     FredmanTarjan &treeMap(TreeMap &m){
00382       if(local_tree) {
00383         delete _tree;
00384         local_tree=false;
00385       }
00386       _tree = &m;
00387       return *this;
00388     }
00389 
00390   public:
00394 
00396 
00398 
00401     void init(){
00402       create_maps();
00403       for(typename Graph::UEdgeIt i(*graph);i!=INVALID;++i){
00404         _tree->set(i,false);
00405       }
00406     }
00407 
00409 
00418     void start(){
00419         phase(*graph,identityMap<UEdge>(),countEdges(*graph));
00420     }
00421     
00423     
00432     void run() {
00433       init();
00434       start();
00435     }
00436 
00438 
00444     
00446 
00448 
00455     const TreeMap &treeMap() const { return *_tree;}
00456  
00458 
00468 
00469     template<class TreeMap>
00470     void treeEdges(
00471         TreeMap& tree,
00472         const typename TreeMap::Value& tree_edge_value=true,
00473         const typename TreeMap::Value& tree_default_value=false) const {
00474       for(typename UGraph::UEdgeIt i(*graph);i!=INVALID;++i){
00475         (*_tree)[i]?tree.set(i,tree_edge_value):tree.set(i,tree_default_value);
00476       }
00477     }
00478 
00480 
00484     bool tree(UEdge e){
00485       return (*_tree)[e];
00486     }
00488   };
00489 
00501   template<class Graph,class CostMap,class TreeMap>
00502   void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){
00503     typename FredmanTarjan<Graph,CostMap>::template DefTreeMap<TreeMap>::
00504       Create ft(graph,cost);
00505     ft.treeMap(tree);
00506     ft.run();
00507   };
00508 
00509 } //END OF NAMESPACE LEMON
00510 
00511 #endif

Generated on Fri Feb 3 18:36:58 2006 for LEMON by  doxygen 1.4.6