test/heap_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 11 Aug 2013 21:56:21 +0200
changeset 1098 cf6084618b1b
parent 948 f9e3f73e17f1
permissions -rw-r--r--
Merge headmerge to the default branch
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     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 
    27 #include <lemon/smart_graph.h>
    28 #include <lemon/lgf_reader.h>
    29 #include <lemon/dijkstra.h>
    30 #include <lemon/maps.h>
    31 
    32 #include <lemon/bin_heap.h>
    33 #include <lemon/quad_heap.h>
    34 #include <lemon/dheap.h>
    35 #include <lemon/fib_heap.h>
    36 #include <lemon/pairing_heap.h>
    37 #include <lemon/radix_heap.h>
    38 #include <lemon/binomial_heap.h>
    39 #include <lemon/bucket_heap.h>
    40 
    41 #include "test_tools.h"
    42 
    43 using namespace lemon;
    44 using namespace lemon::concepts;
    45 
    46 typedef ListDigraph Digraph;
    47 DIGRAPH_TYPEDEFS(Digraph);
    48 
    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"
    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"
    84   "@attributes\n"
    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);
    96 
    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) {
   104     check(v[i] == heap.prio(), "Wrong order in heap sort.");
   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);
   114 
   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) {
   126     check(v[i] == heap.prio(), "Wrong order in heap increase test.");
   127     heap.pop();
   128   }
   129 }
   130 
   131 template <typename Heap>
   132 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
   133                       Node source) {
   134 
   135   typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
   136     Create dijkstra(digraph, length);
   137 
   138   dijkstra.run(source);
   139 
   140   for(ArcIt a(digraph); a != INVALID; ++a) {
   141     Node s = digraph.source(a);
   142     Node t = digraph.target(a);
   143     if (dijkstra.reached(s)) {
   144       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
   145              "Error in shortest path tree.");
   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],
   154              "Error in shortest path tree.");
   155     }
   156   }
   157 
   158 }
   159 
   160 int main() {
   161 
   162   typedef int Item;
   163   typedef int Prio;
   164   typedef RangeMap<int> ItemIntMap;
   165 
   166   Digraph digraph;
   167   IntArcMap length(digraph);
   168   Node source;
   169 
   170   std::istringstream input(test_lgf);
   171   digraphReader(digraph, input).
   172     arcMap("capacity", length).
   173     node("source", source).
   174     run();
   175 
   176   // BinHeap
   177   {
   178     typedef BinHeap<Prio, ItemIntMap> IntHeap;
   179     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   180     heapSortTest<IntHeap>();
   181     heapIncreaseTest<IntHeap>();
   182 
   183     typedef BinHeap<Prio, IntNodeMap > NodeHeap;
   184     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   185     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   186   }
   187 
   188   // QuadHeap
   189   {
   190     typedef QuadHeap<Prio, ItemIntMap> IntHeap;
   191     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   192     heapSortTest<IntHeap>();
   193     heapIncreaseTest<IntHeap>();
   194 
   195     typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
   196     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   197     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   198   }
   199 
   200   // DHeap
   201   {
   202     typedef DHeap<Prio, ItemIntMap> IntHeap;
   203     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   204     heapSortTest<IntHeap>();
   205     heapIncreaseTest<IntHeap>();
   206 
   207     typedef DHeap<Prio, IntNodeMap > NodeHeap;
   208     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   209     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   210   }
   211 
   212   // FibHeap
   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 
   224   // PairingHeap
   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   }
   235 
   236   // RadixHeap
   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 
   248   // BinomialHeap
   249   {
   250     typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
   251     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   252     heapSortTest<IntHeap>();
   253     heapIncreaseTest<IntHeap>();
   254 
   255     typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
   256     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   257     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   258   }
   259 
   260   // BucketHeap, SimpleBucketHeap
   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);
   270 
   271     typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
   272     heapSortTest<SimpleIntHeap>();
   273   }
   274 
   275   {
   276     typedef FibHeap<Prio, ItemIntMap> IntHeap;
   277     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   278     heapSortTest<IntHeap>();
   279     heapIncreaseTest<IntHeap>();
   280 
   281     typedef FibHeap<Prio, IntNodeMap > NodeHeap;
   282     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   283     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   284   }
   285 
   286   {
   287     typedef RadixHeap<ItemIntMap> IntHeap;
   288     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   289     heapSortTest<IntHeap>();
   290     heapIncreaseTest<IntHeap>();
   291 
   292     typedef RadixHeap<IntNodeMap > NodeHeap;
   293     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   294     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   295   }
   296 
   297   {
   298     typedef BucketHeap<ItemIntMap> IntHeap;
   299     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   300     heapSortTest<IntHeap>();
   301     heapIncreaseTest<IntHeap>();
   302 
   303     typedef BucketHeap<IntNodeMap > NodeHeap;
   304     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   305     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   306   }
   307 
   308 
   309   return 0;
   310 }