COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/heap_test.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

File size: 2.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <vector>
20#include <algorithm>
21
22#include <lemon/dijkstra.h>
23
24class IntIntMap : public std::vector<int> {
25public:
26  typedef std::vector<int> Parent;
27
28  IntIntMap() : Parent() {}
29  IntIntMap(int n) : Parent(n) {}
30  IntIntMap(int n, int v) : Parent(n, v) {}
31
32  void set(int key, int value) {
33    Parent::operator[](key) = value;
34  }
35};
36
37
38template <typename _Heap>
39void heapSortTest(int n) {
40  typedef _Heap Heap;
41  IntIntMap map(n, -1);
42
43  Heap heap(map);
44 
45  std::vector<int> v(n);
46
47  for (int i = 0; i < n; ++i) {
48    v[i] = rand() % 1000;
49    heap.push(i, v[i]);
50  }
51  std::sort(v.begin(), v.end());
52  for (int i = 0; i < n; ++i) {
53    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
54    heap.pop();
55  }
56}
57
58template <typename _Heap>
59void heapIncreaseTest(int n) {
60  typedef _Heap Heap;
61  IntIntMap map(n, -1);
62
63  Heap heap(map);
64 
65  std::vector<int> v(n);
66
67  for (int i = 0; i < n; ++i) {
68    v[i] = rand() % 1000;
69    heap.push(i, v[i]);
70  }
71  for (int i = 0; i < n; ++i) {
72    v[i] += rand() % 1000;
73    heap.increase(i, v[i]);
74  }
75  std::sort(v.begin(), v.end());
76  for (int i = 0; i < n; ++i) {
77    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
78    heap.pop();
79  }
80}
81
82
83
84template <typename _Graph, typename _LengthMap, typename _Heap>
85void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
86                      typename _Graph::Node& start) {
87
88  typedef _Heap Heap;
89  typedef _Graph Graph;
90  typedef _LengthMap LengthMap;
91
92  typedef typename Graph::Node Node;
93  typedef typename Graph::Edge Edge;
94  typedef typename Graph::NodeIt NodeIt;
95  typedef typename Graph::EdgeIt EdgeIt;
96
97  typename Dijkstra<Graph, LengthMap>::template DefStandardHeap<Heap>::
98    Create dijkstra(graph, length);
99
100  dijkstra.run(start);
101
102  for(EdgeIt e(graph); e!=INVALID; ++e) {
103    Node u=graph.source(e);
104    Node v=graph.target(e);
105    if (dijkstra.reached(u)) {
106      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
107             "Error in a shortest path tree edge!");
108    }
109  }
110
111  for(NodeIt v(graph); v!=INVALID; ++v) {
112    if ( dijkstra.reached(v) && dijkstra.predEdge(v) != INVALID ) {
113      Edge e=dijkstra.predEdge(v);
114      Node u=graph.source(e);
115      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
116             "Error in a shortest path tree edge!");
117    }
118  }
119
120}
Note: See TracBrowser for help on using the repository browser.