[209] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
[100] | 2 | * |
---|
[209] | 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
[100] | 4 | * |
---|
[440] | 5 | * Copyright (C) 2003-2009 |
---|
[100] | 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 | |
---|
[203] | 27 | #include <lemon/smart_graph.h> |
---|
| 28 | #include <lemon/lgf_reader.h> |
---|
| 29 | #include <lemon/dijkstra.h> |
---|
| 30 | #include <lemon/maps.h> |
---|
[100] | 31 | |
---|
| 32 | #include <lemon/bin_heap.h> |
---|
[855] | 33 | #include <lemon/quad_heap.h> |
---|
| 34 | #include <lemon/dheap.h> |
---|
[681] | 35 | #include <lemon/fib_heap.h> |
---|
[701] | 36 | #include <lemon/pairing_heap.h> |
---|
[681] | 37 | #include <lemon/radix_heap.h> |
---|
[855] | 38 | #include <lemon/binomial_heap.h> |
---|
[681] | 39 | #include <lemon/bucket_heap.h> |
---|
[100] | 40 | |
---|
| 41 | #include "test_tools.h" |
---|
| 42 | |
---|
| 43 | using namespace lemon; |
---|
| 44 | using namespace lemon::concepts; |
---|
| 45 | |
---|
[203] | 46 | typedef ListDigraph Digraph; |
---|
| 47 | DIGRAPH_TYPEDEFS(Digraph); |
---|
| 48 | |
---|
[209] | 49 | char 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" |
---|
[212] | 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" |
---|
[209] | 84 | "@attributes\n" |
---|
[203] | 85 | "source 3\n"; |
---|
| 86 | |
---|
| 87 | int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34}; |
---|
| 88 | int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37}; |
---|
| 89 | |
---|
| 90 | int test_len = sizeof(test_seq) / sizeof(test_seq[0]); |
---|
| 91 | |
---|
| 92 | template <typename Heap> |
---|
| 93 | void heapSortTest() { |
---|
| 94 | RangeMap<int> map(test_len, -1); |
---|
| 95 | Heap heap(map); |
---|
[209] | 96 | |
---|
[203] | 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) { |
---|
[701] | 104 | check(v[i] == heap.prio(), "Wrong order in heap sort."); |
---|
[203] | 105 | heap.pop(); |
---|
| 106 | } |
---|
| 107 | } |
---|
| 108 | |
---|
| 109 | template <typename Heap> |
---|
| 110 | void heapIncreaseTest() { |
---|
| 111 | RangeMap<int> map(test_len, -1); |
---|
| 112 | |
---|
| 113 | Heap heap(map); |
---|
[209] | 114 | |
---|
[203] | 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) { |
---|
[701] | 126 | check(v[i] == heap.prio(), "Wrong order in heap increase test."); |
---|
[203] | 127 | heap.pop(); |
---|
| 128 | } |
---|
| 129 | } |
---|
| 130 | |
---|
| 131 | template <typename Heap> |
---|
[209] | 132 | void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, |
---|
| 133 | Node source) { |
---|
| 134 | |
---|
[257] | 135 | typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>:: |
---|
[203] | 136 | Create dijkstra(digraph, length); |
---|
| 137 | |
---|
| 138 | dijkstra.run(source); |
---|
| 139 | |
---|
| 140 | for(ArcIt a(digraph); a != INVALID; ++a) { |
---|
[209] | 141 | Node s = digraph.source(a); |
---|
[203] | 142 | Node t = digraph.target(a); |
---|
| 143 | if (dijkstra.reached(s)) { |
---|
| 144 | check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], |
---|
[701] | 145 | "Error in shortest path tree."); |
---|
[203] | 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], |
---|
[701] | 154 | "Error in shortest path tree."); |
---|
[203] | 155 | } |
---|
| 156 | } |
---|
| 157 | |
---|
| 158 | } |
---|
| 159 | |
---|
[100] | 160 | int main() { |
---|
| 161 | |
---|
| 162 | typedef int Item; |
---|
| 163 | typedef int Prio; |
---|
[203] | 164 | typedef RangeMap<int> ItemIntMap; |
---|
[209] | 165 | |
---|
[203] | 166 | Digraph digraph; |
---|
| 167 | IntArcMap length(digraph); |
---|
| 168 | Node source; |
---|
[100] | 169 | |
---|
[203] | 170 | std::istringstream input(test_lgf); |
---|
[293] | 171 | digraphReader(digraph, input). |
---|
[203] | 172 | arcMap("capacity", length). |
---|
| 173 | node("source", source). |
---|
[209] | 174 | run(); |
---|
| 175 | |
---|
[701] | 176 | // BinHeap |
---|
[100] | 177 | { |
---|
| 178 | typedef BinHeap<Prio, ItemIntMap> IntHeap; |
---|
| 179 | checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
---|
[203] | 180 | heapSortTest<IntHeap>(); |
---|
| 181 | heapIncreaseTest<IntHeap>(); |
---|
[209] | 182 | |
---|
[203] | 183 | typedef BinHeap<Prio, IntNodeMap > NodeHeap; |
---|
| 184 | checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
---|
| 185 | dijkstraHeapTest<NodeHeap>(digraph, length, source); |
---|
[100] | 186 | } |
---|
| 187 | |
---|
[855] | 188 | // QuadHeap |
---|
[701] | 189 | { |
---|
[855] | 190 | typedef QuadHeap<Prio, ItemIntMap> IntHeap; |
---|
[701] | 191 | checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
---|
| 192 | heapSortTest<IntHeap>(); |
---|
| 193 | heapIncreaseTest<IntHeap>(); |
---|
| 194 | |
---|
[855] | 195 | typedef QuadHeap<Prio, IntNodeMap > NodeHeap; |
---|
[701] | 196 | checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
---|
| 197 | dijkstraHeapTest<NodeHeap>(digraph, length, source); |
---|
| 198 | } |
---|
| 199 | |
---|
[855] | 200 | // DHeap |
---|
[701] | 201 | { |
---|
[855] | 202 | typedef DHeap<Prio, ItemIntMap> IntHeap; |
---|
[701] | 203 | checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
---|
| 204 | heapSortTest<IntHeap>(); |
---|
| 205 | heapIncreaseTest<IntHeap>(); |
---|
| 206 | |
---|
[855] | 207 | typedef DHeap<Prio, IntNodeMap > NodeHeap; |
---|
[701] | 208 | checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
---|
| 209 | dijkstraHeapTest<NodeHeap>(digraph, length, source); |
---|
| 210 | } |
---|
| 211 | |
---|
| 212 | // FibHeap |
---|
[681] | 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 | |
---|
[701] | 224 | // PairingHeap |
---|
[702] | 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 | } |
---|
[701] | 235 | |
---|
| 236 | // RadixHeap |
---|
[681] | 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 | |
---|
[855] | 248 | // BinomialHeap |
---|
[701] | 249 | { |
---|
[855] | 250 | typedef BinomialHeap<Prio, ItemIntMap> IntHeap; |
---|
[701] | 251 | checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
---|
| 252 | heapSortTest<IntHeap>(); |
---|
| 253 | heapIncreaseTest<IntHeap>(); |
---|
| 254 | |
---|
[855] | 255 | typedef BinomialHeap<Prio, IntNodeMap > NodeHeap; |
---|
[701] | 256 | checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
---|
| 257 | dijkstraHeapTest<NodeHeap>(digraph, length, source); |
---|
| 258 | } |
---|
| 259 | |
---|
| 260 | // BucketHeap, SimpleBucketHeap |
---|
[681] | 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); |
---|
[701] | 270 | |
---|
| 271 | typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap; |
---|
| 272 | heapSortTest<SimpleIntHeap>(); |
---|
[681] | 273 | } |
---|
| 274 | |
---|
[100] | 275 | return 0; |
---|
| 276 | } |
---|