COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/heap_test.h @ 1187:04e5825000c5

Last change on this file since 1187:04e5825000c5 was 1187:04e5825000c5, checked in by Balazs Dezso, 16 years ago

concept and checking functions for heaps

File size: 1.9 KB
Line 
1// -+- c++ -+-
2#include <vector>
3#include <algorithm>
4
5#include <lemon/bin_heap.h>
6#include <lemon/fib_heap.h>
7#include <lemon/radix_heap.h>
8
9#include <lemon/dijkstra.h>
10
11class IntIntMap : public std::vector<int> {
12public:
13  typedef std::vector<int> Parent;
14
15  IntIntMap() : Parent() {}
16  IntIntMap(int n) : Parent(n) {}
17  IntIntMap(int n, int v) : Parent(n, v) {}
18
19  void set(int key, int value) {
20    Parent::operator[](key) = value;
21  }
22};
23
24
25template <typename _Heap>
26void heapSortTest(int n) {
27  typedef _Heap Heap;
28  IntIntMap map(n, -1);
29
30  Heap heap(map);
31 
32  std::vector<int> v(n);
33
34  for (int i = 0; i < n; ++i) {
35    v[i] = rand() % 1000;
36    heap.push(i, v[i]);
37  }
38  std::sort(v.begin(), v.end());
39  for (int i = 0; i < n; ++i) {
40    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
41    heap.pop();
42  }
43}
44
45template <typename _Traits, typename _Heap>
46struct DefHeapTraits : public _Traits {
47  typedef _Heap Heap;
48};
49
50template <typename _Graph, typename _LengthMap, typename _Heap>
51void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
52                      typename _Graph::Node& start) {
53
54  typedef _Heap Heap;
55  typedef _Graph Graph;
56  typedef _LengthMap LengthMap;
57
58  typedef typename Graph::Node Node;
59  typedef typename Graph::Edge Edge;
60  typedef typename Graph::NodeIt NodeIt;
61  typedef typename Graph::EdgeIt EdgeIt;
62
63  Dijkstra<Graph, LengthMap,
64    DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> >
65    dijkstra(graph, length);
66
67  dijkstra.run(start);
68
69  for(EdgeIt e(graph); e!=INVALID; ++e) {
70    Node u=graph.source(e);
71    Node v=graph.target(e);
72    if (dijkstra.reached(u)) {
73      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
74             "Error in a shortest path tree edge!");
75    }
76  }
77
78  for(NodeIt v(graph); v!=INVALID; ++v) {
79    if ( dijkstra.reached(v) ) {
80      Edge e=dijkstra.pred(v);
81      Node u=graph.source(e);
82      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
83             "Error in a shortest path tree edge!");
84    }
85  }
86
87}
Note: See TracBrowser for help on using the repository browser.