Changeset 701:d1a9224f1e30 in lemon-main

Timestamp:

07/09/09 02:38:01 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Add fourary, k-ary, pairing and binomial heaps (#301)
These structures were implemented by Dorian Batha.

Files:

• lemon/Makefile.am (modified) (4 diffs)
• lemon/binom_heap.h (added)
• lemon/fourary_heap.h (added)
• lemon/kary_heap.h (added)
• lemon/pairing_heap.h (added)
• test/heap_test.cc (modified) (13 diffs)

lemon/Makefile.am

@@ -60 +60 @@
         lemon/bfs.h \
         lemon/bin_heap.h \
+        lemon/binom_heap.h \
         lemon/bucket_heap.h \
         lemon/cbc.h \
@@ -79 +80 @@
         lemon/euler.h \
         lemon/fib_heap.h \
+        lemon/fourary_heap.h \
         lemon/full_graph.h \
         lemon/glpk.h \
@@ -85 +87 @@
         lemon/grid_graph.h \
         lemon/hypercube_graph.h \
+        lemon/kary_heap.h \
         lemon/kruskal.h \
         lemon/hao_orlin.h \
@@ -100 +103 @@
         lemon/nauty_reader.h \
         lemon/network_simplex.h \
+        lemon/pairing_heap.h \
         lemon/path.h \
         lemon/preflow.h \

test/heap_test.cc

@@ -26 +26 @@
 
 #include <lemon/smart_graph.h>
-
 #include <lemon/lgf_reader.h>
 #include <lemon/dijkstra.h>
@@ -32 +31 @@
 
 #include <lemon/bin_heap.h>
+#include <lemon/fourary_heap.h>
+#include <lemon/kary_heap.h>
 #include <lemon/fib_heap.h>
+#include <lemon/pairing_heap.h>
 #include <lemon/radix_heap.h>
+#include <lemon/binom_heap.h>
 #include <lemon/bucket_heap.h>
 
@@ -90 +93 @@
 void heapSortTest() {
   RangeMap<int> map(test_len, -1);
-
   Heap heap(map);
 
   std::vector<int> v(test_len);
-
   for (int i = 0; i < test_len; ++i) {
     v[i] = test_seq[i];
@@ -101 +102 @@
   std::sort(v.begin(), v.end());
   for (int i = 0; i < test_len; ++i) {
-    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
+    check(v[i] == heap.prio(), "Wrong order in heap sort.");
     heap.pop();
   }
@@ -113 +114 @@
 
   std::vector<int> v(test_len);
-
   for (int i = 0; i < test_len; ++i) {
     v[i] = test_seq[i];
@@ -124 +124 @@
   std::sort(v.begin(), v.end());
   for (int i = 0; i < test_len; ++i) {
-    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
+    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
     heap.pop();
   }
 }
-
-
 
 template <typename Heap>
@@ -145 +143 @@
     if (dijkstra.reached(s)) {
       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
-             "Error in a shortest path tree!");
+             "Error in shortest path tree.");
     }
   }
@@ -154 +152 @@
       Node s = digraph.source(a);
       check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
-             "Error in a shortest path tree!");
+             "Error in shortest path tree.");
     }
   }
@@ -176 +174 @@
     run();
 
+  // BinHeap
   {
     typedef BinHeap<Prio, ItemIntMap> IntHeap;
@@ -187 +186 @@
   }
 
+  // FouraryHeap
+  {
+    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // KaryHeap
+  {
+    typedef KaryHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // FibHeap
   {
     typedef FibHeap<Prio, ItemIntMap> IntHeap;
@@ -198 +222 @@
   }
 
+  // PairingHeap
+//  {
+//    typedef PairingHeap<Prio, ItemIntMap> IntHeap;
+//    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+//    heapSortTest<IntHeap>();
+//    heapIncreaseTest<IntHeap>();
+//
+//    typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
+//    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+//    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+//  }
+
+  // RadixHeap
   {
     typedef RadixHeap<ItemIntMap> IntHeap;
@@ -209 +246 @@
   }
 
+  // BinomHeap
+  {
+    typedef BinomHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // BucketHeap, SimpleBucketHeap
   {
     typedef BucketHeap<ItemIntMap> IntHeap;
@@ -218 +268 @@
     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     dijkstraHeapTest<NodeHeap>(digraph, length, source);
-  }
-
+
+    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
+    heapSortTest<SimpleIntHeap>();
+  }
 
   return 0;