COIN-OR::LEMON - Graph Library

source: lemon-main/test/heap_test.cc @ 1005:c5990f454032

Last change on this file since 1005:c5990f454032 was 681:532697c9fa53, checked in by Balazs Dezso <deba@…>, 15 years ago

Port remaining heaps from SVN -r 3509 (#50)

File size: 5.4 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
29#include <lemon/lgf_reader.h>
30#include <lemon/dijkstra.h>
31#include <lemon/maps.h>
32
33#include <lemon/bin_heap.h>
34#include <lemon/fib_heap.h>
35#include <lemon/radix_heap.h>
36#include <lemon/bucket_heap.h>
37
38#include "test_tools.h"
39
40using namespace lemon;
41using namespace lemon::concepts;
42
43typedef ListDigraph Digraph;
44DIGRAPH_TYPEDEFS(Digraph);
45
46char test_lgf[] =
47  "@nodes\n"
48  "label\n"
49  "0\n"
50  "1\n"
51  "2\n"
52  "3\n"
53  "4\n"
54  "5\n"
55  "6\n"
56  "7\n"
57  "8\n"
58  "9\n"
59  "@arcs\n"
60  "                label   capacity\n"
61  "0       5       0       94\n"
62  "3       9       1       11\n"
63  "8       7       2       83\n"
64  "1       2       3       94\n"
65  "5       7       4       35\n"
66  "7       4       5       84\n"
67  "9       5       6       38\n"
68  "0       4       7       96\n"
69  "6       7       8       6\n"
70  "3       1       9       27\n"
71  "5       2       10      77\n"
72  "5       6       11      69\n"
73  "6       5       12      41\n"
74  "4       6       13      70\n"
75  "3       2       14      45\n"
76  "7       9       15      93\n"
77  "5       9       16      50\n"
78  "9       0       17      94\n"
79  "9       6       18      67\n"
80  "0       9       19      86\n"
81  "@attributes\n"
82  "source 3\n";
83
84int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
85int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
86
87int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
88
89template <typename Heap>
90void heapSortTest() {
91  RangeMap<int> map(test_len, -1);
92
93  Heap heap(map);
94
95  std::vector<int> v(test_len);
96
97  for (int i = 0; i < test_len; ++i) {
98    v[i] = test_seq[i];
99    heap.push(i, v[i]);
100  }
101  std::sort(v.begin(), v.end());
102  for (int i = 0; i < test_len; ++i) {
103    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
104    heap.pop();
105  }
106}
107
108template <typename Heap>
109void heapIncreaseTest() {
110  RangeMap<int> map(test_len, -1);
111
112  Heap heap(map);
113
114  std::vector<int> v(test_len);
115
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
131
132
133template <typename Heap>
134void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
135                      Node source) {
136
137  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
138    Create dijkstra(digraph, length);
139
140  dijkstra.run(source);
141
142  for(ArcIt a(digraph); a != INVALID; ++a) {
143    Node s = digraph.source(a);
144    Node t = digraph.target(a);
145    if (dijkstra.reached(s)) {
146      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
147             "Error in a shortest path tree!");
148    }
149  }
150
151  for(NodeIt n(digraph); n != INVALID; ++n) {
152    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
153      Arc a = dijkstra.predArc(n);
154      Node s = digraph.source(a);
155      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
156             "Error in a shortest path tree!");
157    }
158  }
159
160}
161
162int main() {
163
164  typedef int Item;
165  typedef int Prio;
166  typedef RangeMap<int> ItemIntMap;
167
168  Digraph digraph;
169  IntArcMap length(digraph);
170  Node source;
171
172  std::istringstream input(test_lgf);
173  digraphReader(digraph, input).
174    arcMap("capacity", length).
175    node("source", source).
176    run();
177
178  {
179    typedef BinHeap<Prio, ItemIntMap> IntHeap;
180    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
181    heapSortTest<IntHeap>();
182    heapIncreaseTest<IntHeap>();
183
184    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
185    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
186    dijkstraHeapTest<NodeHeap>(digraph, length, source);
187  }
188
189  {
190    typedef FibHeap<Prio, ItemIntMap> IntHeap;
191    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
192    heapSortTest<IntHeap>();
193    heapIncreaseTest<IntHeap>();
194
195    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
196    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
197    dijkstraHeapTest<NodeHeap>(digraph, length, source);
198  }
199
200  {
201    typedef RadixHeap<ItemIntMap> IntHeap;
202    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
203    heapSortTest<IntHeap>();
204    heapIncreaseTest<IntHeap>();
205
206    typedef RadixHeap<IntNodeMap > NodeHeap;
207    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
208    dijkstraHeapTest<NodeHeap>(digraph, length, source);
209  }
210
211  {
212    typedef BucketHeap<ItemIntMap> IntHeap;
213    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
214    heapSortTest<IntHeap>();
215    heapIncreaseTest<IntHeap>();
216
217    typedef BucketHeap<IntNodeMap > NodeHeap;
218    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
219    dijkstraHeapTest<NodeHeap>(digraph, length, source);
220  }
221
222
223  return 0;
224}
Note: See TracBrowser for help on using the repository browser.