equal
deleted
inserted
replaced
1 // -+- c++ -+- |
1 // -+- c++ -+- |
|
2 |
2 #include <vector> |
3 #include <vector> |
3 #include <algorithm> |
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 #include <lemon/dijkstra.h> |
6 #include <lemon/dijkstra.h> |
10 |
7 |
11 class IntIntMap : public std::vector<int> { |
8 class IntIntMap : public std::vector<int> { |
12 public: |
9 public: |
40 check(v[i] == heap.prio() ,"Wrong order in heap sort."); |
37 check(v[i] == heap.prio() ,"Wrong order in heap sort."); |
41 heap.pop(); |
38 heap.pop(); |
42 } |
39 } |
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 template <typename _Traits, typename _Heap> |
68 template <typename _Traits, typename _Heap> |
46 struct DefHeapTraits : public _Traits { |
69 struct DefHeapTraits : public _Traits { |
47 typedef _Heap Heap; |
70 typedef _Heap Heap; |
48 }; |
71 }; |
49 |
72 |
74 "Error in a shortest path tree edge!"); |
97 "Error in a shortest path tree edge!"); |
75 } |
98 } |
76 } |
99 } |
77 |
100 |
78 for(NodeIt v(graph); v!=INVALID; ++v) { |
101 for(NodeIt v(graph); v!=INVALID; ++v) { |
79 if ( dijkstra.reached(v) ) { |
102 if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) { |
80 Edge e=dijkstra.pred(v); |
103 Edge e=dijkstra.pred(v); |
81 Node u=graph.source(e); |
104 Node u=graph.source(e); |
82 check( dijkstra.dist(v) - dijkstra .dist(u) == length[e], |
105 check( dijkstra.dist(v) - dijkstra .dist(u) == length[e], |
83 "Error in a shortest path tree edge!"); |
106 "Error in a shortest path tree edge!"); |
84 } |
107 } |