test/heap_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 29 Sep 2009 13:32:01 +0200
changeset 929 65a0521e744e
parent 749 bdc7dfc8c054
child 1065 b522385b2a0d
permissions -rw-r--r--
Rename heap structures (#301)

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