/* -*- mode: C++; indent-tabs-mode: nil; -*-
* This file is a part of LEMON, a generic C++ optimization library.
* Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
#include <lemon/concept_check.h>
#include <lemon/concepts/heap.h>
#include <lemon/smart_graph.h>
#include <lemon/lgf_reader.h>
#include <lemon/dijkstra.h>
#include <lemon/bin_heap.h>
#include <lemon/quad_heap.h>
#include <lemon/fib_heap.h>
#include <lemon/pairing_heap.h>
#include <lemon/radix_heap.h>
#include <lemon/binomial_heap.h>
#include <lemon/bucket_heap.h>
using namespace lemon::concepts;
typedef ListDigraph Digraph;
DIGRAPH_TYPEDEFS(Digraph);
int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34};
int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37};
int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
RangeMap<int> map(test_len, -1);
std::vector<int> v(test_len);
for (int i = 0; i < test_len; ++i) {
std::sort(v.begin(), v.end());
for (int i = 0; i < test_len; ++i) {
check(v[i] == heap.prio(), "Wrong order in heap sort.");
void heapIncreaseTest() {
RangeMap<int> map(test_len, -1);
std::vector<int> v(test_len);
for (int i = 0; i < test_len; ++i) {
for (int i = 0; i < test_len; ++i) {
std::sort(v.begin(), v.end());
for (int i = 0; i < test_len; ++i) {
check(v[i] == heap.prio(), "Wrong order in heap increase test.");
void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
Create dijkstra(digraph, length);
for(ArcIt a(digraph); a != INVALID; ++a) {
Node s = digraph.source(a);
Node t = digraph.target(a);
if (dijkstra.reached(s)) {
check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
"Error in shortest path tree.");
for(NodeIt n(digraph); n != INVALID; ++n) {
if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
Arc a = dijkstra.predArc(n);
Node s = digraph.source(a);
check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
"Error in shortest path tree.");
typedef RangeMap<int> ItemIntMap;
IntArcMap length(digraph);
std::istringstream input(test_lgf);
digraphReader(digraph, input).
arcMap("capacity", length).
typedef BinHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef BinHeap<Prio, IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef QuadHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef DHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef DHeap<Prio, IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef FibHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef FibHeap<Prio, IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef PairingHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef RadixHeap<ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef RadixHeap<IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
// BucketHeap, SimpleBucketHeap
typedef BucketHeap<ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef BucketHeap<IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
heapSortTest<SimpleIntHeap>();
typedef FibHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef FibHeap<Prio, IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef RadixHeap<ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef RadixHeap<IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
typedef BucketHeap<ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
heapIncreaseTest<IntHeap>();
typedef BucketHeap<IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);