COIN-OR::LEMON - Graph Library

source: lemon-main/test/heap_test.h @ 100:4f754b4cf82b

Last change on this file since 100:4f754b4cf82b was 100:4f754b4cf82b, checked in by Alpar Juttner <alpar@…>, 17 years ago

Bfs/Dfs/Dijkstra? and their deps ported from svn trung -r 3441.

File size: 2.9 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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  typedef int Key;
29  typedef int Value;
30
31  IntIntMap() : Parent() {}
32  IntIntMap(int n) : Parent(n) {}
33  IntIntMap(int n, int v) : Parent(n, v) {}
34
35  void set(int key, int value) {
36    Parent::operator[](key) = value;
37  }
38};
39
40
41template <typename _Heap>
42void heapSortTest(int n) {
43  typedef _Heap Heap;
44  IntIntMap map(n, -1);
45
46  Heap heap(map);
47 
48  std::vector<int> v(n);
49
50  for (int i = 0; i < n; ++i) {
51    v[i] = rnd[1000];
52    heap.push(i, v[i]);
53  }
54  std::sort(v.begin(), v.end());
55  for (int i = 0; i < n; ++i) {
56    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
57    heap.pop();
58  }
59}
60
61template <typename _Heap>
62void heapIncreaseTest(int n) {
63  typedef _Heap Heap;
64  IntIntMap map(n, -1);
65
66  Heap heap(map);
67 
68  std::vector<int> v(n);
69
70  for (int i = 0; i < n; ++i) {
71    v[i] = rnd[1000];
72    heap.push(i, v[i]);
73  }
74  for (int i = 0; i < n; ++i) {
75    v[i] += rnd[1000];
76    heap.increase(i, v[i]);
77  }
78  std::sort(v.begin(), v.end());
79  for (int i = 0; i < n; ++i) {
80    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
81    heap.pop();
82  }
83}
84
85
86
87template <typename _Digraph, typename _LengthMap, typename _Heap>
88void dijkstraHeapTest(_Digraph& digraph, _LengthMap& length,
89                      typename _Digraph::Node& start) {
90
91  typedef _Heap Heap;
92  typedef _Digraph Digraph;
93  typedef _LengthMap LengthMap;
94
95  typedef typename Digraph::Node Node;
96  typedef typename Digraph::Arc Arc;
97  typedef typename Digraph::NodeIt NodeIt;
98  typedef typename Digraph::ArcIt ArcIt;
99
100  typename Dijkstra<Digraph, LengthMap>::template DefStandardHeap<Heap>::
101    Create dijkstra(digraph, length);
102
103  dijkstra.run(start);
104
105  for(ArcIt e(digraph); e!=INVALID; ++e) {
106    Node u=digraph.source(e);
107    Node v=digraph.target(e);
108    if (dijkstra.reached(u)) {
109      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
110             "Error in a shortest path tree arc!");
111    }
112  }
113
114  for(NodeIt v(digraph); v!=INVALID; ++v) {
115    if ( dijkstra.reached(v) && dijkstra.predArc(v) != INVALID ) {
116      Arc e=dijkstra.predArc(v);
117      Node u=digraph.source(e);
118      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
119             "Error in a shortest path tree arc!");
120    }
121  }
122
123}
Note: See TracBrowser for help on using the repository browser.