Changeset 2050:d9a221218ea4 in lemon0.x for lemon/fredman_tarjan.h
 Timestamp:
 04/14/06 20:05:02 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2693
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/fredman_tarjan.h
r2042 r2050 212 212 private: 213 213 214 template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap> 215 void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap, 216 ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){ 214 template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef, 215 class ProcessedMap,class PredMap> 216 void processNextTree(const SrcGraph& graph,const OrigMap& orig, 217 Heap &heap, HeapCrossRef& crossref, 218 ProcessedMap& processed,PredMap& pred, 219 int& tree_counter,const int limit){ 217 220 std::vector<typename SrcGraph::Node> tree_nodes; 218 221 int tree_index=tree_counter; … … 255 258 _tree>set(orig[pred[tree_nodes[i]]],true); 256 259 processed.set(tree_nodes[i],tree_index); 257 heap.state(tree_nodes[i], Heap::PRE_HEAP);260 crossref[tree_nodes[i]] = Heap::PRE_HEAP; 258 261 } 259 262 processed.set(tree_nodes[0],tree_index); 260 heap.state(tree_nodes[0],Heap::PRE_HEAP);263 crossref[tree_nodes[0]] = Heap::PRE_HEAP; 261 264 while (!heap.empty()) { 262 265 typename SrcGraph::Node v=heap.top(); 263 266 heap.pop(); 264 heap.state(v,Heap::PRE_HEAP); 265 } 267 crossref[v] = Heap::PRE_HEAP; 268 } 269 heap.clear(); 266 270 if(!stop)++tree_counter; 267 271 } 268 272 269 273 template<class SrcGraph,class OrigMap,class ProcessedMap> 270 void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed, 271 int edgenum,int& tree_counter){ 274 void createTrees(const SrcGraph& graph, const OrigMap& orig, 275 ProcessedMap& processed, 276 int edgenum,int& tree_counter){ 272 277 typedef typename SrcGraph::Node Node; 273 278 typedef typename SrcGraph::UEdge UEdge; … … 279 284 PredMap pred(graph,INVALID); 280 285 int rate=2*edgenum/countNodes(graph); 281 int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate); 286 int limit=(rate>std::numeric_limits<int>::digits)? 287 std::numeric_limits<int>::max() : (1<<rate); 282 288 for(NodeIt i(graph);i!=INVALID;++i){ 283 289 if(processed[i]==1){ 284 290 heap.push(i, Value()); 285 processNextTree(graph,orig,heap,processed,pred,tree_counter,limit); 291 processNextTree(graph,orig,heap,crossref, 292 processed,pred,tree_counter,limit); 286 293 } 287 294 } 288 295 } 289 296 290 template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap> 291 void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph, 292 DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){ 297 template<class SrcGraph,class DestGraph,class SrcOrigMap, 298 class DestOrigMap,class ProcessedMap> 299 void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig, 300 DestGraph& destgraph,DestOrigMap& destorig, 301 const ProcessedMap& processed,const int tree_counter){ 293 302 typedef typename SrcGraph::Node Node; 294 303 typedef typename DestGraph::Node DNode; … … 311 320 } 312 321 313 radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph)))); 314 counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph)))); 322 radixSort(edges.begin(),edges.end(), 323 mapFunctor(composeMap(processed,sourceMap(srcgraph)))); 324 counterSort(edges.begin(),edges.end(), 325 mapFunctor(composeMap(processed,targetMap(srcgraph)))); 315 326 for(int i=0;i!=(int)edges.size();++i){ 316 327 int srcproc=processed[srcgraph.source(edges[i])]; … … 318 329 Value minval=(*cost)[srcorig[edges[i]]]; 319 330 UEdge minpos=edges[i]; 320 while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] && 331 while (i+1!=(int)edges.size() && 332 srcproc==processed[srcgraph.source(edges[i+1])] && 321 333 trgproc==processed[srcgraph.target(edges[i+1])]) { 322 334 if (minval>(*cost)[srcorig[edges[i+1]]]) { … … 326 338 ++i; 327 339 } 328 destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos]; 340 destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]= 341 srcorig[minpos]; 329 342 } 330 343 }
Note: See TracChangeset
for help on using the changeset viewer.