Changeset 1206:9c398137c2cb in lemon-0.x

Timestamp:

03/09/05 15:10:21 (20 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Increase test
Changing test graph

Location:

src/test

Files:

• Makefile.am (modified) (3 diffs)
• dijkstra_test.lemon (added)
• heap_test.cc (modified) (6 diffs)
• heap_test.h (modified) (3 diffs)

src/test/Makefile.am

@@ -8 +8 @@
         sym_graph_test.h \
         map_test.h \
-        graph_utils_test.h
+        graph_utils_test.h \
+        heap_test.h
 
 check_PROGRAMS = \
@@ -29 +30 @@
         unionfind_test \
         undir_graph_test \
-        xy_test
+        xy_test \
+        heap_test
 
 TESTS = $(check_PROGRAMS)
@@ -53 +55 @@
 xy_test_SOURCES = xy_test.cc
 undir_graph_test_SOURCES = undir_graph_test.cc
-
+heap_test_SOURCES = heap_test.cc

src/test/heap_test.cc

@@ -7 +7 @@
 #include <lemon/concept_check.h>
 
+#include <lemon/smart_graph.h>
+
+#include <lemon/graph_reader.h>
+
 #include <lemon/bin_heap.h>
 #include <lemon/fib_heap.h>
 #include <lemon/radix_heap.h>
 
-#include <lemon/dimacs.h>
+#include "test_tools.h"
 
-#include "test_tools.h"
 #include "heap_test.h"
-#include "map_test.h"
 
 
@@ -32 +34 @@
       Prio prio;
 
+      ignore_unused_variable_warning(item);
+      ignore_unused_variable_warning(prio);
+
       typedef typename _Heap::state_enum state_enum;
       state_enum state;
+
+      ignore_unused_variable_warning(state);
       
       _Heap heap1 = _Heap(map);
+
+      ignore_unused_variable_warning(heap1);
       
       heap.push(item, prio);
@@ -81 +90 @@
   Node start;
 
-  std::ifstream input("preflow_graph.dim");
-  readDimacs(input, graph, length, start);  
+  /// \todo create own test graph
+  std::ifstream input("dijkstra_test.lemon");
+  readGraph(input, graph, length, start);  
  
   {
@@ -89 +99 @@
     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(20);
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
     
     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
@@ -100 +111 @@
     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(20);
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
 
     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
@@ -111 +123 @@
     typedef RadixHeap<Item, ItemIntMap> IntHeap;
     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(20);
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
 
     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;

src/test/heap_test.h

@@ -1 +1 @@
 // -+- c++ -+-
+
 #include <vector>
 #include <algorithm>
-
-#include <lemon/bin_heap.h>
-#include <lemon/fib_heap.h>
-#include <lemon/radix_heap.h>
 
 #include <lemon/dijkstra.h>
@@ -43 +40 @@
 }
 
+template <typename _Heap>
+void heapIncreaseTest(int n) {
+  typedef _Heap Heap;
+  IntIntMap map(n, -1);
+
+  Heap heap(map);
+  
+  std::vector<int> v(n);
+
+  for (int i = 0; i < n; ++i) {
+    v[i] = rand() % 1000;
+    heap.push(i, v[i]);
+  }
+  for (int i = 0; i < n; ++i) {
+    v[i] += rand() % 1000;
+    heap.increase(i, v[i]);
+  }
+  std::sort(v.begin(), v.end());
+  for (int i = 0; i < n; ++i) {
+    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
+    heap.pop();
+  }
+}
+
+
+
 template <typename _Traits, typename _Heap>
 struct DefHeapTraits : public _Traits {
@@ -77 +100 @@
 
   for(NodeIt v(graph); v!=INVALID; ++v) {
-    if ( dijkstra.reached(v) ) {
+    if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) {
       Edge e=dijkstra.pred(v);
       Node u=graph.source(e);