Changeset 1206:9c398137c2cb in lemon0.x
 Timestamp:
 03/09/05 15:10:21 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1625
 Location:
 src/test
 Files:

 1 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

src/test/Makefile.am
r1094 r1206 8 8 sym_graph_test.h \ 9 9 map_test.h \ 10 graph_utils_test.h 10 graph_utils_test.h \ 11 heap_test.h 11 12 12 13 check_PROGRAMS = \ … … 29 30 unionfind_test \ 30 31 undir_graph_test \ 31 xy_test 32 xy_test \ 33 heap_test 32 34 33 35 TESTS = $(check_PROGRAMS) … … 53 55 xy_test_SOURCES = xy_test.cc 54 56 undir_graph_test_SOURCES = undir_graph_test.cc 55 57 heap_test_SOURCES = heap_test.cc 
src/test/heap_test.cc
r1187 r1206 7 7 #include <lemon/concept_check.h> 8 8 9 #include <lemon/smart_graph.h> 10 11 #include <lemon/graph_reader.h> 12 9 13 #include <lemon/bin_heap.h> 10 14 #include <lemon/fib_heap.h> 11 15 #include <lemon/radix_heap.h> 12 16 13 #include <lemon/dimacs.h>17 #include "test_tools.h" 14 18 15 #include "test_tools.h"16 19 #include "heap_test.h" 17 #include "map_test.h"18 20 19 21 … … 32 34 Prio prio; 33 35 36 ignore_unused_variable_warning(item); 37 ignore_unused_variable_warning(prio); 38 34 39 typedef typename _Heap::state_enum state_enum; 35 40 state_enum state; 41 42 ignore_unused_variable_warning(state); 36 43 37 44 _Heap heap1 = _Heap(map); 45 46 ignore_unused_variable_warning(heap1); 38 47 39 48 heap.push(item, prio); … … 81 90 Node start; 82 91 83 std::ifstream input("preflow_graph.dim"); 84 readDimacs(input, graph, length, start); 92 /// \todo create own test graph 93 std::ifstream input("dijkstra_test.lemon"); 94 readGraph(input, graph, length, start); 85 95 86 96 { … … 89 99 typedef BinHeap<Item, Prio, ItemIntMap> IntHeap; 90 100 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>(); 91 heapSortTest<IntHeap>(20); 101 heapSortTest<IntHeap>(100); 102 heapIncreaseTest<IntHeap>(100); 92 103 93 104 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; … … 100 111 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap; 101 112 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>(); 102 heapSortTest<IntHeap>(20); 113 heapSortTest<IntHeap>(100); 114 heapIncreaseTest<IntHeap>(100); 103 115 104 116 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; … … 111 123 typedef RadixHeap<Item, ItemIntMap> IntHeap; 112 124 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>(); 113 heapSortTest<IntHeap>(20); 125 heapSortTest<IntHeap>(100); 126 heapIncreaseTest<IntHeap>(100); 114 127 115 128 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap; 
src/test/heap_test.h
r1187 r1206 1 1 // + c++ + 2 2 3 #include <vector> 3 4 #include <algorithm> 4 5 #include <lemon/bin_heap.h>6 #include <lemon/fib_heap.h>7 #include <lemon/radix_heap.h>8 5 9 6 #include <lemon/dijkstra.h> … … 43 40 } 44 41 42 template <typename _Heap> 43 void heapIncreaseTest(int n) { 44 typedef _Heap Heap; 45 IntIntMap map(n, 1); 46 47 Heap heap(map); 48 49 std::vector<int> v(n); 50 51 for (int i = 0; i < n; ++i) { 52 v[i] = rand() % 1000; 53 heap.push(i, v[i]); 54 } 55 for (int i = 0; i < n; ++i) { 56 v[i] += rand() % 1000; 57 heap.increase(i, v[i]); 58 } 59 std::sort(v.begin(), v.end()); 60 for (int i = 0; i < n; ++i) { 61 check(v[i] == heap.prio() ,"Wrong order in heap increase test."); 62 heap.pop(); 63 } 64 } 65 66 67 45 68 template <typename _Traits, typename _Heap> 46 69 struct DefHeapTraits : public _Traits { … … 77 100 78 101 for(NodeIt v(graph); v!=INVALID; ++v) { 79 if ( dijkstra.reached(v) ) {102 if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) { 80 103 Edge e=dijkstra.pred(v); 81 104 Node u=graph.source(e);
Note: See TracChangeset
for help on using the changeset viewer.