Changeset 2050:d9a221218ea4 in lemon-0.x

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

Location:

lemon

Files:

• bin_heap.h (modified) (1 diff)
• bucket_heap.h (modified) (2 diffs)
• fib_heap.h (modified) (1 diff)
• fredman_tarjan.h (modified) (6 diffs)
• radix_heap.h (modified) (1 diff)

lemon/bin_heap.h

@@ -113 +113 @@
     /// \brief Make empty this heap.
     /// 
-    /// Make empty this heap.
+    /// Make empty this heap. It does not change the cross reference map.
+    /// If you want to reuse what is not surely empty you should first clear
+    /// the heap and after that you should set the cross reference map for
+    /// each item to \c PRE_HEAP.
     void clear() { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-        iim.set(data[i].first, POST_HEAP);
-      }
       data.clear(); 
     }

lemon/bucket_heap.h

@@ -91 +91 @@
     /// \brief Make empty this heap.
     /// 
-    /// Make empty this heap.
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear() { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-        index[data[i].item] = -2;
-      }
       data.clear(); first.clear(); minimal = 0;
     }
@@ -350 +350 @@
 
     void clear() { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-        index[data[i].item] = -2;
-      }
       data.clear(); first.clear(); maximal = -1; 
     }

lemon/fib_heap.h

@@ -117 +117 @@
     /// \brief Make empty this heap.
     /// 
-    /// Make empty this heap.
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear() {
-      if (num_items != 0) {
-        for (int i = 0; i < (int)container.size(); ++i) {
-          iimap[container[i].name] = -2;
-        }
-      }
       container.clear(); minimum = 0; num_items = 0;
     }

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];
       }
     }

lemon/radix_heap.h

@@ -137 +137 @@
     /// \brief Make empty this heap.
     /// 
-    /// Make empty this heap.
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear(int minimal = 0, int capacity = 0) { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-        iim[data[i].item] = -2;
-      }
       data.clear(); boxes.clear(); 
       boxes.push_back(RadixBox(minimal, 1));