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