Changeset 2038:33db14058543 in lemon-0.x

Timestamp:

04/04/06 19:45:35 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

LinearHeap? is renamed to BucketHeap? which is more conform
and widely used name for this data structure

Files:

• demo/coloring.cc (modified) (2 diffs)
• lemon/Makefile.am (modified) (1 diff)
• lemon/bucket_heap.h (added)
• lemon/linear_heap.h (deleted)
• lemon/min_cut.h (modified) (4 diffs)
• lemon/topology.h (modified) (1 diff)
• test/heap_test.cc (modified) (2 diffs)

demo/coloring.cc

@@ -31 +31 @@
 
 #include <lemon/smart_graph.h>
-#include <lemon/linear_heap.h>
+#include <lemon/bucket_heap.h>
 #include <lemon/graph_reader.h>
 #include <lemon/graph_to_eps.h>
@@ -64 +64 @@
   
   Graph::NodeMap<int> heapMap(graph, -1);
-  LinearHeap<Node, Graph::NodeMap<int> > heap(heapMap);
+  BucketHeap<Node, Graph::NodeMap<int> > heap(heapMap);
   
   for (NodeIt it(graph); it != INVALID; ++it) {

lemon/Makefile.am

@@ -54 +54 @@
         johnson.h \
         kruskal.h \
-        linear_heap.h \
+        bucket_heap.h \
         list_graph.h \
         lp.h \

lemon/min_cut.h

@@ -25 +25 @@
 #include <lemon/list_graph.h>
 #include <lemon/bin_heap.h>
-#include <lemon/linear_heap.h>
+#include <lemon/bucket_heap.h>
 
 #include <lemon/bits/invalid.h>
@@ -49 +49 @@
       template <typename Key, typename Value, typename Ref>
       struct Selector {
-        typedef LinearHeap<Key, Ref, false > Heap;
+        typedef BucketHeap<Key, Ref, false > Heap;
       };
     };
@@ -95 +95 @@
     /// the \ref BinHeap, but it is specialized when the
     /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
-    /// to LinearHeap.
+    /// to BucketHeap.
     ///
     /// \sa MaxCardinalitySearch
@@ -842 +842 @@
   /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci 
   /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity 
-  /// map is used then it uses LinearHeap which results O(n*e) time complexity.
+  /// map is used then it uses BucketHeap which results O(n*e) time complexity.
 #ifdef DOXYGEN
   template <typename _Graph, typename _CapacityMap, typename _Traits>

lemon/topology.h

@@ -31 +31 @@
 
 #include <lemon/bin_heap.h>
-#include <lemon/linear_heap.h>
+#include <lemon/bucket_heap.h>
 
 #include <stack>

test/heap_test.cc

@@ -32 +32 @@
 #include <lemon/fib_heap.h>
 #include <lemon/radix_heap.h>
-#include <lemon/linear_heap.h>
+#include <lemon/bucket_heap.h>
 
 #include "test_tools.h"
@@ -121 +121 @@
 
   {
-    std::cerr << "Checking Linear Heap" << std::endl;
+    std::cerr << "Checking Bucket Heap" << std::endl;
 
-    typedef LinearHeap<Item, ItemIntMap> IntHeap;
+    typedef BucketHeap<Item, ItemIntMap> IntHeap;
     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
     heapSortTest<IntHeap>(100);
     heapIncreaseTest<IntHeap>(100);
 
-    typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
+    typedef BucketHeap<Node, Graph::NodeMap<int> > NodeHeap;
     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
     Timer timer;