COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/heap_test.h @ 1508:389a94a1d9eb

Last change on this file since 1508:389a94a1d9eb was 1435:8e85e6bbefdf, checked in by Akos Ladanyi, 19 years ago

trunk/src/* move to trunk/

File size: 2.4 KB
Line 
1// -+- c++ -+-
2
3#include <vector>
4#include <algorithm>
5
6#include <lemon/dijkstra.h>
7
8class IntIntMap : public std::vector<int> {
9public:
10  typedef std::vector<int> Parent;
11
12  IntIntMap() : Parent() {}
13  IntIntMap(int n) : Parent(n) {}
14  IntIntMap(int n, int v) : Parent(n, v) {}
15
16  void set(int key, int value) {
17    Parent::operator[](key) = value;
18  }
19};
20
21
22template <typename _Heap>
23void heapSortTest(int n) {
24  typedef _Heap Heap;
25  IntIntMap map(n, -1);
26
27  Heap heap(map);
28 
29  std::vector<int> v(n);
30
31  for (int i = 0; i < n; ++i) {
32    v[i] = rand() % 1000;
33    heap.push(i, v[i]);
34  }
35  std::sort(v.begin(), v.end());
36  for (int i = 0; i < n; ++i) {
37    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
38    heap.pop();
39  }
40}
41
42template <typename _Heap>
43void 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
68template <typename _Traits, typename _Heap>
69struct DefHeapTraits : public _Traits {
70  typedef _Heap Heap;
71};
72
73template <typename _Graph, typename _LengthMap, typename _Heap>
74void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
75                      typename _Graph::Node& start) {
76
77  typedef _Heap Heap;
78  typedef _Graph Graph;
79  typedef _LengthMap LengthMap;
80
81  typedef typename Graph::Node Node;
82  typedef typename Graph::Edge Edge;
83  typedef typename Graph::NodeIt NodeIt;
84  typedef typename Graph::EdgeIt EdgeIt;
85
86  Dijkstra<Graph, LengthMap,
87    DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> >
88    dijkstra(graph, length);
89
90  dijkstra.run(start);
91
92  for(EdgeIt e(graph); e!=INVALID; ++e) {
93    Node u=graph.source(e);
94    Node v=graph.target(e);
95    if (dijkstra.reached(u)) {
96      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
97             "Error in a shortest path tree edge!");
98    }
99  }
100
101  for(NodeIt v(graph); v!=INVALID; ++v) {
102    if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) {
103      Edge e=dijkstra.pred(v);
104      Node u=graph.source(e);
105      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
106             "Error in a shortest path tree edge!");
107    }
108  }
109
110}
Note: See TracBrowser for help on using the repository browser.