Changeset 2050:d9a221218ea4 in lemon-0.x for lemon/fredman_tarjan.h

Timestamp:

04/14/06 20:05:02 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2693

Message:

Changing the mining of the clear in heaps
It does not touch the heap cross ref. It is
sometimes more clean useable and more efficient

File:

• lemon/fredman_tarjan.h (modified) (6 diffs)

lemon/fredman_tarjan.h

@@ -212 +212 @@
   private:
 
-    template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
-    void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
-        ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
+    template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef,
+             class ProcessedMap,class PredMap>
+    void processNextTree(const SrcGraph& graph,const OrigMap& orig,
+                         Heap &heap, HeapCrossRef& crossref,
+                         ProcessedMap& processed,PredMap& pred,
+                         int& tree_counter,const int limit){
       std::vector<typename SrcGraph::Node> tree_nodes;
       int tree_index=tree_counter;
@@ -255 +258 @@
         _tree->set(orig[pred[tree_nodes[i]]],true);
         processed.set(tree_nodes[i],tree_index);
-        heap.state(tree_nodes[i], Heap::PRE_HEAP);
+        crossref[tree_nodes[i]] = Heap::PRE_HEAP;
       }
       processed.set(tree_nodes[0],tree_index);
-      heap.state(tree_nodes[0],Heap::PRE_HEAP);
+      crossref[tree_nodes[0]] = Heap::PRE_HEAP;
       while (!heap.empty()) {
         typename SrcGraph::Node v=heap.top();
         heap.pop();
-        heap.state(v,Heap::PRE_HEAP);
-      }
+        crossref[v] = Heap::PRE_HEAP;
+      }
+      heap.clear();
       if(!stop)++tree_counter;
     }
 
     template<class SrcGraph,class OrigMap,class ProcessedMap>
-    void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
-        int edgenum,int& tree_counter){
+    void createTrees(const SrcGraph& graph, const OrigMap& orig, 
+                     ProcessedMap& processed,
+                     int edgenum,int& tree_counter){
       typedef typename SrcGraph::Node Node;
       typedef typename SrcGraph::UEdge UEdge;
@@ -279 +284 @@
       PredMap pred(graph,INVALID);
       int rate=2*edgenum/countNodes(graph);
-      int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
+      int limit=(rate>std::numeric_limits<int>::digits)?
+      std::numeric_limits<int>::max() : (1<<rate);
       for(NodeIt i(graph);i!=INVALID;++i){
         if(processed[i]==-1){
           heap.push(i, Value());
-          processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
+          processNextTree(graph,orig,heap,crossref,
+                          processed,pred,tree_counter,limit);
         }
       }
     }
 
-    template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
-    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
-        DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
+    template<class SrcGraph,class DestGraph,class SrcOrigMap,
+             class DestOrigMap,class ProcessedMap>
+    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,
+                 DestGraph& destgraph,DestOrigMap& destorig,
+                 const ProcessedMap& processed,const int tree_counter){
       typedef typename SrcGraph::Node Node;
       typedef typename DestGraph::Node DNode;
@@ -311 +320 @@
       }
       
-      radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
-      counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
+      radixSort(edges.begin(),edges.end(),
+                mapFunctor(composeMap(processed,sourceMap(srcgraph))));
+      counterSort(edges.begin(),edges.end(),
+                  mapFunctor(composeMap(processed,targetMap(srcgraph))));
       for(int i=0;i!=(int)edges.size();++i){
         int srcproc=processed[srcgraph.source(edges[i])];
@@ -318 +329 @@
         Value minval=(*cost)[srcorig[edges[i]]];
         UEdge minpos=edges[i];
-        while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
+        while (i+1!=(int)edges.size() && 
+               srcproc==processed[srcgraph.source(edges[i+1])] &&
           trgproc==processed[srcgraph.target(edges[i+1])]) {
           if (minval>(*cost)[srcorig[edges[i+1]]]) {
@@ -326 +338 @@
           ++i;
         } 
-        destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
+        destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=
+          srcorig[minpos];
       }
     }