COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/heap_test.cc @ 857:abb95d48e89e

Last change on this file since 857:abb95d48e89e was 702:bdc7dfc8c054, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Bug fix in PairingHeap::pop() (#301)

File size: 7.1 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
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 <iostream>
20#include <fstream>
21#include <string>
22#include <vector>
23
24#include <lemon/concept_check.h>
25#include <lemon/concepts/heap.h>
26
27#include <lemon/smart_graph.h>
28#include <lemon/lgf_reader.h>
29#include <lemon/dijkstra.h>
30#include <lemon/maps.h>
31
32#include <lemon/bin_heap.h>
33#include <lemon/fourary_heap.h>
34#include <lemon/kary_heap.h>
35#include <lemon/fib_heap.h>
36#include <lemon/pairing_heap.h>
37#include <lemon/radix_heap.h>
38#include <lemon/binom_heap.h>
39#include <lemon/bucket_heap.h>
40
41#include "test_tools.h"
42
43using namespace lemon;
44using namespace lemon::concepts;
45
46typedef ListDigraph Digraph;
47DIGRAPH_TYPEDEFS(Digraph);
48
49char test_lgf[] =
50  "@nodes\n"
51  "label\n"
52  "0\n"
53  "1\n"
54  "2\n"
55  "3\n"
56  "4\n"
57  "5\n"
58  "6\n"
59  "7\n"
60  "8\n"
61  "9\n"
62  "@arcs\n"
63  "                label   capacity\n"
64  "0       5       0       94\n"
65  "3       9       1       11\n"
66  "8       7       2       83\n"
67  "1       2       3       94\n"
68  "5       7       4       35\n"
69  "7       4       5       84\n"
70  "9       5       6       38\n"
71  "0       4       7       96\n"
72  "6       7       8       6\n"
73  "3       1       9       27\n"
74  "5       2       10      77\n"
75  "5       6       11      69\n"
76  "6       5       12      41\n"
77  "4       6       13      70\n"
78  "3       2       14      45\n"
79  "7       9       15      93\n"
80  "5       9       16      50\n"
81  "9       0       17      94\n"
82  "9       6       18      67\n"
83  "0       9       19      86\n"
84  "@attributes\n"
85  "source 3\n";
86
87int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
88int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
89
90int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
91
92template <typename Heap>
93void heapSortTest() {
94  RangeMap<int> map(test_len, -1);
95  Heap heap(map);
96
97  std::vector<int> v(test_len);
98  for (int i = 0; i < test_len; ++i) {
99    v[i] = test_seq[i];
100    heap.push(i, v[i]);
101  }
102  std::sort(v.begin(), v.end());
103  for (int i = 0; i < test_len; ++i) {
104    check(v[i] == heap.prio(), "Wrong order in heap sort.");
105    heap.pop();
106  }
107}
108
109template <typename Heap>
110void heapIncreaseTest() {
111  RangeMap<int> map(test_len, -1);
112
113  Heap heap(map);
114
115  std::vector<int> v(test_len);
116  for (int i = 0; i < test_len; ++i) {
117    v[i] = test_seq[i];
118    heap.push(i, v[i]);
119  }
120  for (int i = 0; i < test_len; ++i) {
121    v[i] += test_inc[i];
122    heap.increase(i, v[i]);
123  }
124  std::sort(v.begin(), v.end());
125  for (int i = 0; i < test_len; ++i) {
126    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
127    heap.pop();
128  }
129}
130
131template <typename Heap>
132void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
133                      Node source) {
134
135  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
136    Create dijkstra(digraph, length);
137
138  dijkstra.run(source);
139
140  for(ArcIt a(digraph); a != INVALID; ++a) {
141    Node s = digraph.source(a);
142    Node t = digraph.target(a);
143    if (dijkstra.reached(s)) {
144      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
145             "Error in shortest path tree.");
146    }
147  }
148
149  for(NodeIt n(digraph); n != INVALID; ++n) {
150    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
151      Arc a = dijkstra.predArc(n);
152      Node s = digraph.source(a);
153      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
154             "Error in shortest path tree.");
155    }
156  }
157
158}
159
160int main() {
161
162  typedef int Item;
163  typedef int Prio;
164  typedef RangeMap<int> ItemIntMap;
165
166  Digraph digraph;
167  IntArcMap length(digraph);
168  Node source;
169
170  std::istringstream input(test_lgf);
171  digraphReader(digraph, input).
172    arcMap("capacity", length).
173    node("source", source).
174    run();
175
176  // BinHeap
177  {
178    typedef BinHeap<Prio, ItemIntMap> IntHeap;
179    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
180    heapSortTest<IntHeap>();
181    heapIncreaseTest<IntHeap>();
182
183    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
184    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
185    dijkstraHeapTest<NodeHeap>(digraph, length, source);
186  }
187
188  // FouraryHeap
189  {
190    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
191    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
192    heapSortTest<IntHeap>();
193    heapIncreaseTest<IntHeap>();
194
195    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
196    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
197    dijkstraHeapTest<NodeHeap>(digraph, length, source);
198  }
199
200  // KaryHeap
201  {
202    typedef KaryHeap<Prio, ItemIntMap> IntHeap;
203    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
204    heapSortTest<IntHeap>();
205    heapIncreaseTest<IntHeap>();
206
207    typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
208    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
209    dijkstraHeapTest<NodeHeap>(digraph, length, source);
210  }
211
212  // FibHeap
213  {
214    typedef FibHeap<Prio, ItemIntMap> IntHeap;
215    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
216    heapSortTest<IntHeap>();
217    heapIncreaseTest<IntHeap>();
218
219    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
220    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
221    dijkstraHeapTest<NodeHeap>(digraph, length, source);
222  }
223
224  // PairingHeap
225  {
226    typedef PairingHeap<Prio, ItemIntMap> IntHeap;
227    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
228    heapSortTest<IntHeap>();
229    heapIncreaseTest<IntHeap>();
230
231    typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
232    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
233    dijkstraHeapTest<NodeHeap>(digraph, length, source);
234  }
235
236  // RadixHeap
237  {
238    typedef RadixHeap<ItemIntMap> IntHeap;
239    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
240    heapSortTest<IntHeap>();
241    heapIncreaseTest<IntHeap>();
242
243    typedef RadixHeap<IntNodeMap > NodeHeap;
244    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
245    dijkstraHeapTest<NodeHeap>(digraph, length, source);
246  }
247
248  // BinomHeap
249  {
250    typedef BinomHeap<Prio, ItemIntMap> IntHeap;
251    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
252    heapSortTest<IntHeap>();
253    heapIncreaseTest<IntHeap>();
254
255    typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
256    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
257    dijkstraHeapTest<NodeHeap>(digraph, length, source);
258  }
259
260  // BucketHeap, SimpleBucketHeap
261  {
262    typedef BucketHeap<ItemIntMap> IntHeap;
263    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
264    heapSortTest<IntHeap>();
265    heapIncreaseTest<IntHeap>();
266
267    typedef BucketHeap<IntNodeMap > NodeHeap;
268    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
269    dijkstraHeapTest<NodeHeap>(digraph, length, source);
270
271    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
272    heapSortTest<SimpleIntHeap>();
273  }
274
275  return 0;
276}
Note: See TracBrowser for help on using the repository browser.