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