00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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
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 }
00510
00511 #endif