1/** \file
2 * \brief Tests for implementations of various heaps.
3 *
4 * \author Łukasz Hanuszczak, Tilo Wiedera
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include <vector>
33#include <queue>
34#include <set>
35#include <algorithm>
36#include <numeric>
37
38#include <ogdf/basic/comparer.h>
39#include <ogdf/basic/graph_generators.h>
40#include <ogdf/basic/PriorityQueue.h>
41#include <ogdf/graphalg/Dijkstra.h>
42
43#include <ogdf/basic/heap/BinaryHeap.h>
44#include <ogdf/basic/heap/BinomialHeap.h>
45#include <ogdf/basic/heap/FibonacciHeap.h>
46#include <ogdf/basic/heap/RMHeap.h>
47#include <ogdf/basic/heap/RadixHeap.h>
48#include <ogdf/basic/heap/HotQueue.h>
49
50#include <testing.h>
51
52static std::vector<int> randomVector(size_t n)
53{
54 std::default_random_engine rng(n);
55 std::uniform_int_distribution<int> dist;
56
57 std::vector<int> values;
58 for (size_t i = 0; i < n; i++) {
59 values.push_back(dist(rng));
60 }
61
62 return values;
63}
64
65template<template<typename T, typename C> class H>
66void simpleScenarioTest(bool supportsDecrease, bool supportsMerge)
67{
68 describe("simple scenario test", [&]() {
69 using Handle = typename H<int, std::less<int>>::Handle;
70 constexpr void *invalidHandle = nullptr;
71 Handle handle = nullptr;
72
73 it("pushes values", [&]() {
74 H<int, std::less<int>> heap;
75
76 handle = heap.push(3);
77 AssertThat(handle, Is().Not().EqualTo(invalidHandle));
78 AssertThat(heap.value(handle), Equals(3));
79
80 handle = heap.push(10);
81 AssertThat(handle, Is().Not().EqualTo(invalidHandle));
82 AssertThat(heap.value(handle), Equals(10));
83
84 handle = heap.push(5);
85 AssertThat(handle, Is().Not().EqualTo(invalidHandle));
86 AssertThat(heap.value(handle), Equals(5));
87
88 handle = heap.push(7);
89 AssertThat(handle, Is().Not().EqualTo(invalidHandle));
90 AssertThat(heap.value(handle), Equals(7));
91 });
92
93 it("pops in the right order", [&]() {
94 H<int, std::less<int>> heap;
95 heap.push(3);
96 heap.push(10);
97 heap.push(5);
98 heap.push(7);
99
100 AssertThat(heap.top(), Equals(3));
101 heap.pop();
102 AssertThat(heap.top(), Equals(5));
103 heap.pop();
104 AssertThat(heap.top(), Equals(7));
105 heap.pop();
106 AssertThat(heap.top(), Equals(10));
107 });
108
109 if (supportsDecrease) {
110 it("decreases values and pops in the right order", []() {
111 H<int, std::less<int>> heap;
112 heap.push(3);
113 heap.push(10);
114 Handle node5 = heap.push(5);
115 Handle node7 = heap.push(7);
116
117 AssertThat(heap.top(), Equals(3));
118 heap.decrease(node7, 2);
119 AssertThat(heap.value(node7), Equals(2));
120 AssertThat(heap.top(), Equals(2));
121 heap.pop();
122 AssertThat(heap.top(), Equals(3));
123 heap.pop();
124 AssertThat(heap.top(), Equals(5));
125 heap.decrease(node5, 1);
126 AssertThat(heap.value(node5), Equals(1));
127 AssertThat(heap.top(), Equals(1));
128 heap.pop();
129 AssertThat(heap.top(), Equals(10));
130 });
131 }
132
133 if(supportsMerge) {
134 it("merges two heaps", []() {
135 H<int, std::less<int>> h1, h2;
136 h1.push(3);
137 h1.push(5);
138 h1.push(-2);
139
140 h2.push(1);
141 h2.push(-1);
142 h2.push(4);
143
144 h1.merge(h2);
145
146 AssertThat(h1.top(), Equals(-2));
147 h1.pop();
148 AssertThat(h1.top(), Equals(-1));
149 h1.pop();
150 AssertThat(h1.top(), Equals(1));
151 h1.pop();
152 AssertThat(h1.top(), Equals(3));
153 h1.pop();
154 AssertThat(h1.top(), Equals(4));
155 h1.pop();
156 AssertThat(h1.top(), Equals(5));
157 });
158 }
159 });
160}
161
162template<typename T, typename C, template<typename X, typename Y> class H>
163void sortingDatasetTest(const std::vector<T> &values)
164{
165 using Handle = typename H<T, C>::Handle;
166
167 it("pushes and pops values in correct order", [&]() {
168 H<T, C> heap;
169
170 for(const T &v : values) {
171 Handle node = heap.push(v);
172 AssertThat(heap.value(node), Equals(v));
173 }
174
175 C compare;
176 std::vector<int> sorted(values);
177 std::sort(sorted.begin(), sorted.end(), compare);
178
179 for (const T &v : sorted) {
180 // compare is either "greater" or "less"
181 AssertThat(compare(heap.top(), v), IsFalse());
182 AssertThat(compare(v, heap.top()), IsFalse());
183 heap.pop();
184 }
185 });
186}
187
188template<typename T, typename C, template<typename X, typename Y> class H>
189void mergingDatasetTest(const std::vector<T> &a, const std::vector<T> &b)
190{
191 using Handle = typename H<T, C>::Handle;
192
193 it("pushes values and merges heaps", [&]() {
194 H<T, C> heapA, heapB;
195
196 for(const T &v : a) {
197 Handle node = heapA.push(v);
198 AssertThat(heapA.value(node), Equals(v));
199 }
200 for(const T &v : b) {
201 Handle node = heapB.push(v);
202 AssertThat(heapB.value(node), Equals(v));
203 }
204
205 std::vector<int> merged, sortedA(a), sortedB(b);
206 std::sort(sortedA.begin(), sortedA.end(), C());
207 std::sort(sortedB.begin(), sortedB.end(), C());
208 std::merge(
209 sortedA.begin(), sortedA.end(),
210 sortedB.begin(), sortedB.end(),
211 std::back_inserter(merged));
212
213 heapA.merge(heapB);
214
215 for(const T &v : merged) {
216 AssertThat(heapA.top(), Equals(v));
217 heapA.pop();
218 }
219 });
220}
221
222template<template<typename T, typename C> class H>
223void sortingRandomTest(size_t n)
224{
225 std::string desc = "sorting on " + std::to_string(n) + " random values";
226 describe(desc.data(), [&]() {
227 std::vector<int> data;
228
229 before_each([&](){
230 data = randomVector(n);
231 });
232
233 sortingDatasetTest<int, std::less<int>, H>(data);
234 });
235}
236
237template<template<typename T, typename C> class H>
238void sortingComparerTest(size_t n)
239{
240 std::string descStandard = "sorting on " + std::to_string(n) + " random values with standard comparer";
241 describe(descStandard.data(), [&]() {
242 std::vector<int> data;
243
244 before_each([&](){
245 data = randomVector(n);
246 });
247
248 sortingDatasetTest<int, ogdf::StlGreater<int, ogdf::StdComparer<int>>, H>(data);
249 });
250
251 class ModComparer {
252 public:
253 static int compare(const int &x, const int &y) {
254 return x % 3 - y % 3;
255 }
256 OGDF_AUGMENT_STATICCOMPARER(int)
257 };
258
259 std::string descCustom = "sorting on " + std::to_string(n) + " random values with custom comparer";
260 describe(descCustom.data(), [&]() {
261 std::vector<int> data;
262
263 before_each([&](){
264 data = randomVector(n);
265 });
266
267 sortingDatasetTest<int, ogdf::StlLess<int, ModComparer>, H>(data);
268 });
269}
270
271template<template<typename T, typename C> class H>
272void mergingRandomTest(size_t n)
273{
274 std::string desc = "merging on " + std::to_string(n) + " random values";
275 describe(desc.data(), [&]() {
276 std::vector<int> a;
277 std::vector<int> b;
278
279 before_each([&](){
280 a = (randomVector(n / 3));
281 b = (randomVector(2 * (n / 3) + n % 3));
282 });
283
284 mergingDatasetTest<int, std::less<int>, H>(a, b);
285 });
286}
287
288template<template<typename T, typename C> class H>
289void destructorTest()
290{
291 describe("destructor test", []() {
292 size_t N = 1000;
293
294 it("should push random values and release memory", [&]() {
295 std::vector<int> data(randomVector(N));
296
297 H<int, std::less<int>> h;
298 std::for_each(data.begin(), data.end(), [&](int v) { h.push(v); });
299 });
300
301 it("shoud push sorted values and release memory", [&]() {
302 std::vector<int> data(N);
303 std::iota(data.begin(), data.end(), 1);
304
305 H<int, std::less<int>> h;
306 std::for_each(data.begin(), data.end(), [&](int v) { h.push(v); });
307 });
308
309 it("should push and pop random values and release memory", [&]() {
310 std::vector<int> data(randomVector(N));
311
312 H<int, std::less<int>> h;
313 for(size_t i = 0; i < N; i++) {
314 if(i % 3 < 2) {
315 h.push(data[i]);
316 } else {
317 h.pop();
318 }
319 }
320 });
321 });
322}
323
324template<template<typename T, class C> class Impl>
325void prioritizedQueueWrapperTest(std::size_t n)
326{
327 std::string desc = "prioritized queue wrapper test on " + std::to_string(n) + " rands";
328 describe(desc.data(), [&]() {
329
330 std::default_random_engine rng(n);
331
332 it("works for integers", [&]() {
333 std::vector<int> data(randomVector(n));
334 PrioritizedQueue<int, int, std::greater<int>, Impl> queue;
335
336 std::set<int> indices;
337 for(int i = 0; i < static_cast<int>(data.size()); i++) {
338 indices.insert(i);
339 }
340
341 std::uniform_int_distribution<int> dist;
342
343 // randomly insert elements
344 for(int i = 0; i < static_cast<int>(data.size()); i++) {
345 int pos = dist(rng) % (int) indices.size();
346 std::set<int>::iterator it = indices.begin();
347 advance(it, pos);
348 queue.push(data[*it], *it);
349 indices.erase(it);
350 }
351
352 AssertThat(queue.size(), Equals(data.size()));
353
354 // pop elements in order
355 for(int i = (int) queue.size() - 1; !queue.empty(); i--) {
356 AssertThat(queue.topElement(), Equals(data.back()));
357 AssertThat(queue.topPriority(), Equals(i));
358 queue.pop();
359 data.pop_back();
360 }
361
362 queue.clear();
363 });
364
365 it("works for nodes", [&]() {
366 std::uniform_int_distribution<int> dist(0, (int) n);
367
368 Graph graph;
369 int m = (int) dist(rng);
370 randomGraph(graph, (int) std::sqrt(m), m);
371 PrioritizedMapQueue<node, int, std::less<int>, Impl> queue(graph);
372
373 for(node v : graph.nodes) {
374 AssertThat(queue.contains(v), Is().False());
375 queue.push(v, v->degree());
376 AssertThat(queue.contains(v), Is().True());
377 }
378
379 AssertThat((int) queue.size(), Equals(graph.numberOfNodes()));
380
381 int lastDegree = 0;
382 while(!queue.empty()) {
383 node v = queue.topElement();
384 AssertThat(queue.contains(v), Is().True());
385 AssertThat(v->degree(), Equals(queue.topPriority()));
386 AssertThat(v->degree(), !IsLessThan(lastDegree));
387 lastDegree = v->degree();
388 queue.pop();
389 AssertThat(queue.contains(v), Is().False());
390 }
391
392 queue.clear();
393 });
394
395 it("works for edges", [&]() {
396 Graph graph;
397 randomTree(graph, (int)(n+1));
398 PrioritizedMapQueue<edge, int, std::less<int>, Impl> queue(graph);
399
400 for(edge e : graph.edges) {
401 AssertThat(queue.contains(e), Is().False());
402 queue.push(e, e->index());
403 AssertThat(queue.contains(e), Is().True());
404 }
405
406 AssertThat((int) queue.size(), Equals(graph.numberOfEdges()));
407
408 for(int i = 0; i < graph.numberOfEdges(); i++) {
409 edge e = queue.topElement();
410 AssertThat(queue.contains(e), Is().True());
411 AssertThat(e->index(), Equals(i));
412 queue.pop();
413 AssertThat(queue.contains(e), Is().False());
414 }
415
416 AssertThat(queue.empty(), IsTrue());
417 queue.clear();
418 });
419 });
420}
421
422template<template<typename T, class C> class Impl>
423void priorityQueueWrapperTest(std::size_t n, bool supportsMerge = true)
424{
425 using PQ = PriorityQueue<int, std::greater<int>, Impl>;
426
427 std::string desc = "queue wrapper test on " + std::to_string(n) + " rands";
428 describe(desc.data(), [&]() {
429 std::vector<int> data;
430 auto init = { 3, 1, 6, -20, 4, 2, -4, 1, 6 };
431 PQ ogdfPQ;
432
433 before_each([&](){
434 ogdfPQ.clear();
435 data = randomVector(n);
436 });
437
438 it("behaves like std::priority_queue", [&]() {
439 std::priority_queue<int> stdPQ;
440
441 for(int e : data) {
442 ogdfPQ.push(e);
443 stdPQ.push(e);
444
445 AssertThat(ogdfPQ.size(), Equals(stdPQ.size()));
446 AssertThat(ogdfPQ.top(), Equals(stdPQ.top()));
447 }
448
449 while(!stdPQ.empty()) {
450 AssertThat(ogdfPQ.empty(), IsFalse());
451 AssertThat(ogdfPQ.top(), Equals(stdPQ.top()));
452 AssertThat(ogdfPQ.size(), Equals(stdPQ.size()));
453
454 ogdfPQ.pop();
455 stdPQ.pop();
456 }
457
458 AssertThat(ogdfPQ.empty(), IsTrue());
459 });
460
461
462 it("allows to be initialized with initializer list", [&]() {
463 ogdfPQ = init;
464 AssertThat(ogdfPQ.size(), Equals(init.size()));
465 std::vector<int> elems = init;
466
467 while(!ogdfPQ.empty()) {
468 int value = ogdfPQ.top();
469 auto it = std::find(elems.begin(), elems.end(), value);
470
471 AssertThat(it != elems.end(), IsTrue());
472
473 elems.erase(it);
474 ogdfPQ.pop();
475 }
476 });
477
478 it("supports move-construction", [&]() {
479 ogdfPQ = init;
480 PQ tmp(std::move(ogdfPQ));
481 AssertThat(tmp.size() == init.size(), IsTrue());
482 std::vector<int> elems = init;
483
484 while(!tmp.empty()) {
485 int value = tmp.top();
486 auto it = std::find(elems.begin(), elems.end(), value);
487
488 AssertThat(it != elems.end(), IsTrue());
489
490 elems.erase(it);
491 tmp.pop();
492 }
493 });
494
495 it("allows swapping operation", [&]() {
496 ogdfPQ.clear();
497 AssertThat(ogdfPQ.size(), Equals(0u));
498
499 PQ tmp = { 1, 2, 3 };
500
501 using std::swap;
502 swap(tmp, ogdfPQ);
503 AssertThat(ogdfPQ.size(), Equals(3u));
504 AssertThat(tmp.size(), Equals(0u));
505 });
506
507 if (supportsMerge) {
508 it("correctly merges and clears another PriorityQueue", [&]() {
509 ogdfPQ = init;
510 AssertThat(ogdfPQ.size(), Equals(init.size()));
511
512 PQ tmp = { 1, 2, 3 };
513 ogdfPQ.merge(tmp);
514 AssertThat(ogdfPQ.size(), Equals(init.size() + 3));
515 AssertThat(tmp.size(), Equals(0u));
516
517 tmp = { 1, 2, 3 };
518 PQ orig = init;
519 while (!tmp.empty() && !orig.empty()) {
520 AssertThat(ogdfPQ.empty(), IsFalse());
521 int val = ogdfPQ.top();
522 AssertThat((val == orig.top() || val == tmp.top()), IsTrue());
523 if (val == orig.top()) {
524 orig.pop();
525 }
526 else { // val == tmp.top()
527 tmp.pop();
528 }
529 ogdfPQ.pop();
530 }
531 });
532 }
533 });
534}
535
536void radixHeapSortingTest(std::size_t n)
537{
538 std::string desc = "sorting test on " + std::to_string(n) + " rands";
539 describe(desc.data(), [&]() {
540 using RadixHeapType = RadixHeap<std::string, std::size_t>;
541 std::unique_ptr<RadixHeapType> heap;
542
543 before_each([&](){
544 std::default_random_engine rng(n);
545 std::uniform_int_distribution<std::size_t> size_dist(1, 100);
546 std::uniform_int_distribution<char> char_dist('a', 'z');
547
548 heap.reset(new RadixHeapType());
549
550 for(std::size_t i = 0; i < n; i++) {
551 std::string str(size_dist(rng), char_dist(rng));
552 heap->push(str, str.length());
553 }
554 });
555
556 it("has correct size after insertions", [&]() {
557 AssertThat(heap->size(), Equals(n));
558 });
559
560 it("correctly sorts inserted values", [&]() {
561 std::size_t last = 0;
562 while(!heap->empty()) {
563 std::string str = heap->pop();
564 AssertThat(str.size(), Is().Not().LessThan(last));
565 last = str.size();
566 }
567 });
568 });
569}
570
571template<template<typename T, class C> class H>
572void hotQueueSimpleScenario(std::size_t levels, bool supportsDecrease)
573{
574 using Queue = HotQueue<std::string, int, H>;
575
576 it("creates empty queue", [&]() {
577 Queue queue(100, levels);
578 AssertThat(queue.empty(), IsTrue());
579 });
580
581 it("inserts elements", [&]() {
582 Queue queue(100, levels);
583 queue.push("abc", 10);
584 queue.push("def", 31);
585 queue.push("ghi", 15);
586 queue.push("xyz", 12);
587 queue.push("ror", 22);
588
589 AssertThat(queue.size(), Equals(5u));
590 });
591
592 if (supportsDecrease) {
593 it("pops elements in the right order and decreases keys", [&]() {
594 Queue queue(100, levels);
595 queue.push("abc", 10);
596 queue.push("def", 31);
597 queue.push("ghi", 15);
598 queue.push("xyz", 12);
599 queue.push("ror", 22);
600
601 AssertThat(queue.top(), Equals("abc"));
602 queue.pop();
603 AssertThat(queue.top(), Equals("xyz"));
604 queue.pop();
605
606 queue.push("uvw", 17);
607 AssertThat(queue.top(), Equals("ghi"));
608 queue.pop();
609 AssertThat(queue.top(), Equals("uvw"));
610 queue.pop();
611
612 auto handle = queue.push("poiuyt", 35);
613 queue.decrease(handle, 28);
614 queue.push("qwerty", 32);
615
616 AssertThat(queue.top(), Equals("ror"));
617 queue.pop();
618 AssertThat(queue.top(), Equals("poiuyt"));
619 queue.pop();
620 AssertThat(queue.top(), Equals("def"));
621 queue.pop();
622 AssertThat(queue.top(), Equals("qwerty"));
623 queue.pop();
624
625 AssertThat(queue.empty(), IsTrue());
626 });
627 }
628}
629
630template<template<typename T, class C> class H>
631void hotQueueSimpleTest(std::size_t levels, bool supportsDecrease)
632{
633 std::string desc =
634 "simple scenario test using " + std::to_string(levels) + " levels";
635 describe(desc.data(), [&]() {
636 /*
637 * clang parser crashes from too many lambdas or something, so this
638 * additional function is needed to make it not crash. When the bug
639 * will be fixed, it may be copy-n-pasted here again.
640 */
641 hotQueueSimpleScenario<H>(levels, supportsDecrease);
642 });
643}
644
645template<template<typename T, class C> class H>
646void dijkstraTest(int n)
647{
648 std::string title =
649 "yields the same result as the PairingHeap for Dijkstra on a graph with " + to_string(n) + " nodes";
650 it(title.data(), [&]() {
651 Graph graph;
652 randomBiconnectedGraph(graph, n, randomNumber(n, n*(n-1)/2));
653 EdgeArray<int> costs(graph);
654
655 for(edge e : graph.edges) {
656 costs[e] = randomNumber(1, n);
657 }
658
659 Dijkstra<int, PairingHeap> dijkstra;
660 Dijkstra<int, H> dijkstraCustom;
661 node source = graph.chooseNode();
662 NodeArray<edge> preds(graph);
663 NodeArray<int> distances(graph);
664 NodeArray<int> distancesCustom(graph);
665
666 dijkstra.call(graph, costs, source, preds, distances);
667 dijkstraCustom.call(graph, costs, source, preds, distancesCustom);
668
669 for(node v : graph.nodes) {
670 AssertThat(distancesCustom[v], Equals(distances[v]));
671 }
672 });
673}
674
675template<template<typename T, class C> class H>
676void describeHeapBasic(bool supportsDecrease, bool supportsMerge) {
677 simpleScenarioTest<H>(supportsDecrease, supportsMerge);
678 destructorTest<H>();
679 sortingComparerTest<H>(100);
680 sortingRandomTest<H>(100);
681 sortingRandomTest<H>(10000);
682 sortingRandomTest<H>(1000000);
683 if(supportsMerge) {
684 mergingRandomTest<H>(100);
685 mergingRandomTest<H>(10000);
686 mergingRandomTest<H>(1000000);
687 }
688 if (supportsDecrease) {
689 priorityQueueWrapperTest<H>(100, supportsMerge);
690 priorityQueueWrapperTest<H>(10000, supportsMerge);
691 //priorityQueueWrapperTest<H>(1000000, supportsMerge);
692 prioritizedQueueWrapperTest<H>(10);
693 prioritizedQueueWrapperTest<H>(100);
694 prioritizedQueueWrapperTest<H>(10000);
695 dijkstraTest<H>(10);
696 dijkstraTest<H>(100);
697 dijkstraTest<H>(1000);
698 }
699}
700
701template<template<typename T, class C> class H>
702void describeHeap(const char *title, bool supportsDecrease = true, bool supportsMerge = true) {
703 describe(title, [&](){
704 describeHeapBasic<H>(supportsDecrease, supportsMerge);
705
706 describe("Heap-on-Top queue", [&]() {
707 hotQueueSimpleTest<H>(3, supportsDecrease);
708 hotQueueSimpleTest<H>(5, supportsDecrease);
709 hotQueueSimpleTest<H>(7, supportsDecrease);
710 hotQueueSimpleTest<H>(11, supportsDecrease);
711 });
712 });
713}
714
715go_bandit([]() {
716 describe("Heaps", [](){
717 describeHeap<BinaryHeap>("Binary heap", true, false);
718 describeHeap<PairingHeap>("Pairing heap");
719 describeHeap<BinomialHeap>("Binomial heap", false);
720 describeHeap<FibonacciHeap>("Fibonacci heap");
721 describeHeap<RMHeap>("Randomized mergable heap");
722
723 describe("Radix heap", [](){
724 radixHeapSortingTest(1000);
725 radixHeapSortingTest(10000);
726 radixHeapSortingTest(100000);
727 });
728 });
729});
730