Changes in / [205:436fe75092b7:204:77d56a21c3ab] in lemon-main

Files:

• lemon/concepts/heap.h (modified) (3 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (3 diffs)
• test/heap_test.cc (modified) (2 diffs)
• test/heap_test.h (added)

lemon/concepts/heap.h

@@ -182 +182 @@
           Item item;
           Prio prio;
+          State state;
           item=Item();
           prio=Prio();
           ignore_unused_variable_warning(item);
           ignore_unused_variable_warning(prio);
+          ignore_unused_variable_warning(state);
 
           OwnItem own_item;
@@ -202 +204 @@
           
           int s = heap.size();
-          ignore_unused_variable_warning(s);
           bool e = heap.empty();
-          ignore_unused_variable_warning(e);
 
           prio = heap.prio();
@@ -228 +228 @@
           heap.clear();
 
-          own_state = heap.state(own_item);
+          state = heap.state(item);
+          heap.state(item, state);
+          state = heap.state(own_item);
           heap.state(own_item, own_state);
 
+          state = _Heap::PRE_HEAP;
+          state = _Heap::IN_HEAP;
+          state = _Heap::POST_HEAP;
           own_state = _Heap::PRE_HEAP;
           own_state = _Heap::IN_HEAP;

test/CMakeLists.txt

@@ -14 +14 @@
   graph_test
   graph_utils_test
-  heap_test
   kruskal_test
   maps_test

test/Makefile.am

@@ -4 +4 @@
 noinst_HEADERS += \
         test/graph_test.h \
+        test/heap_test.h \
         test/graph_maps_test.h \
         test/test_tools.h
@@ -18 +19 @@
         test/graph_test \
         test/graph_utils_test \
-        test/heap_test \
         test/kruskal_test \
         test/maps_test \
@@ -41 +41 @@
 test_graph_test_SOURCES = test/graph_test.cc
 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
-test_heap_test_SOURCES = test/heap_test.cc
+# test_heap_test_SOURCES = test/heap_test.cc
 test_kruskal_test_SOURCES = test/kruskal_test.cc
 test_maps_test_SOURCES = test/maps_test.cc

test/heap_test.cc

@@ -25 +25 @@
 #include <lemon/concepts/heap.h>
 
-#include <lemon/smart_graph.h>
+#include <lemon/list_graph.h>
 
-#include <lemon/lgf_reader.h>
-#include <lemon/dijkstra.h>
-#include <lemon/maps.h>
+#include <lemon/digraph_reader.h>
 
 #include <lemon/bin_heap.h>
+#include <lemon/fib_heap.h>
+#include <lemon/radix_heap.h>
+#include <lemon/bucket_heap.h>
 
 #include "test_tools.h"
 
+#include "heap_test.h"
+
+#include <lemon/time_measure.h>
+
 using namespace lemon;
 using namespace lemon::concepts;
-
-typedef ListDigraph Digraph;
-DIGRAPH_TYPEDEFS(Digraph);
-
-char test_lgf[] = 
-  "@nodes\n" 
-  "label\n"     
-  "0\n" 
-  "1\n" 
-  "2\n" 
-  "3\n" 
-  "4\n" 
-  "5\n" 
-  "6\n" 
-  "7\n" 
-  "8\n" 
-  "9\n" 
-  "@arcs\n" 
-  "             label   capacity\n"     
-  "0    5       0       94\n"   
-  "3    9       1       11\n"   
-  "8    7       2       83\n"   
-  "1    2       3       94\n"   
-  "5    7       4       35\n"   
-  "7    4       5       84\n"   
-  "9    5       6       38\n"   
-  "0    4       7       96\n"   
-  "6    7       8       6\n"    
-  "3    1       9       27\n"   
-  "5    2       10      77\n"   
-  "5    6       11      69\n"   
-  "6    5       12      41\n"   
-  "4    6       13      70\n"   
-  "3    2       14      45\n"   
-  "7    9       15      93\n"   
-  "5    9       16      50\n"   
-  "9    0       17      94\n"   
-  "9    6       18      67\n"   
-  "0    9       19      86\n"   
-  "@attributes\n" 
-  "source 3\n";
-
-int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
-int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
-
-int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
-
-template <typename Heap>
-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];
-    heap.push(i, v[i]);
-  }
-  std::sort(v.begin(), v.end());
-  for (int i = 0; i < test_len; ++i) {
-    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
-    heap.pop();
-  }
-}
-
-template <typename Heap>
-void heapIncreaseTest() {
-  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];
-    heap.push(i, v[i]);
-  }
-  for (int i = 0; i < test_len; ++i) {
-    v[i] += test_inc[i];
-    heap.increase(i, v[i]);
-  }
-  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.");
-    heap.pop();
-  }
-}
-
-
-
-template <typename Heap>
-void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 
-                      Node source) {
-  
-  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
-    Create dijkstra(digraph, length);
-
-  dijkstra.run(source);
-
-  for(ArcIt a(digraph); a != INVALID; ++a) {
-    Node s = digraph.source(a); 
-    Node t = digraph.target(a);
-    if (dijkstra.reached(s)) {
-      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
-             "Error in a shortest path tree!");
-    }
-  }
-
-  for(NodeIt n(digraph); n != INVALID; ++n) {
-    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
-      Arc a = dijkstra.predArc(n);
-      Node s = digraph.source(a);
-      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
-             "Error in a shortest path tree!");
-    }
-  }
-
-}
 
 int main() {
@@ -161 +47 @@
   typedef int Item;
   typedef int Prio;
-  typedef RangeMap<int> ItemIntMap;
+  typedef IntIntMap ItemIntMap;
+
+  typedef ListDigraph Digraph;
+
+  typedef Digraph::Arc Arc;
+  typedef Digraph::Node Node;
+  typedef Digraph::ArcIt ArcIt;
+  typedef Digraph::NodeIt NodeIt;
+  typedef Digraph::ArcMap<int> LengthMap;
+
+  Digraph digraph;
+  LengthMap length(digraph);
+  Node start;
+
+  /// \todo create own test digraph
+
+  std::string f_name;
+  if( getenv("srcdir") )
+    f_name = std::string(getenv("srcdir"));
+  else f_name = ".";
+  f_name += "/test/dijkstra_test.lgf";
   
-  Digraph digraph;
-  IntArcMap length(digraph);
-  Node source;
-
-  std::istringstream input(test_lgf);
-  digraphReader(input, digraph).
-    arcMap("capacity", length).
-    node("source", source).
+  std::ifstream input(f_name.c_str());
+  check(input, "Input file '" << f_name << "' not found.");
+  DigraphReader<Digraph>(input, digraph).
+    readArcMap("capacity", length).
+    readNode("source", start).
     run();  
  
   {
+    std::cout << "Checking Bin Heap" << std::endl;
+
     typedef BinHeap<Prio, ItemIntMap> IntHeap;
     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
     
-    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
+    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
+    Timer timer;
+    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
+    std::cout << timer << std::endl;
+  }
+  {
+    std::cout << "Checking Fib Heap" << std::endl;
+
+    typedef FibHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
+
+    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
+    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
+    Timer timer;
+    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
+    std::cout << timer << std::endl;
+  }
+  {
+    std::cout << "Checking Radix Heap" << std::endl;
+
+    typedef RadixHeap<ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
+
+    typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
+    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
+    Timer timer;
+    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
+    std::cout << timer << std::endl;
+  }
+
+  {
+    std::cout << "Checking Bucket Heap" << std::endl;
+
+    typedef BucketHeap<ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
+
+    typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
+    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
+    Timer timer;
+    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
+    std::cout << timer << std::endl;
   }