COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/heap_test.cc

    r440 r702  
    2626
    2727#include <lemon/smart_graph.h>
    28 
    2928#include <lemon/lgf_reader.h>
    3029#include <lemon/dijkstra.h>
     
    3231
    3332#include <lemon/bin_heap.h>
     33#include <lemon/fourary_heap.h>
     34#include <lemon/kary_heap.h>
     35#include <lemon/fib_heap.h>
     36#include <lemon/pairing_heap.h>
     37#include <lemon/radix_heap.h>
     38#include <lemon/binom_heap.h>
     39#include <lemon/bucket_heap.h>
    3440
    3541#include "test_tools.h"
     
    8793void heapSortTest() {
    8894  RangeMap<int> map(test_len, -1);
    89 
    9095  Heap heap(map);
    9196
    9297  std::vector<int> v(test_len);
    93 
    9498  for (int i = 0; i < test_len; ++i) {
    9599    v[i] = test_seq[i];
     
    98102  std::sort(v.begin(), v.end());
    99103  for (int i = 0; i < test_len; ++i) {
    100     check(v[i] == heap.prio() ,"Wrong order in heap sort.");
     104    check(v[i] == heap.prio(), "Wrong order in heap sort.");
    101105    heap.pop();
    102106  }
     
    110114
    111115  std::vector<int> v(test_len);
    112 
    113116  for (int i = 0; i < test_len; ++i) {
    114117    v[i] = test_seq[i];
     
    121124  std::sort(v.begin(), v.end());
    122125  for (int i = 0; i < test_len; ++i) {
    123     check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
     126    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
    124127    heap.pop();
    125128  }
    126129}
    127 
    128 
    129130
    130131template <typename Heap>
     
    142143    if (dijkstra.reached(s)) {
    143144      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
    144              "Error in a shortest path tree!");
     145             "Error in shortest path tree.");
    145146    }
    146147  }
     
    151152      Node s = digraph.source(a);
    152153      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
    153              "Error in a shortest path tree!");
     154             "Error in shortest path tree.");
    154155    }
    155156  }
     
    173174    run();
    174175
     176  // BinHeap
    175177  {
    176178    typedef BinHeap<Prio, ItemIntMap> IntHeap;
     
    184186  }
    185187
     188  // FouraryHeap
     189  {
     190    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
     191    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     192    heapSortTest<IntHeap>();
     193    heapIncreaseTest<IntHeap>();
     194
     195    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
     196    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     197    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     198  }
     199
     200  // KaryHeap
     201  {
     202    typedef KaryHeap<Prio, ItemIntMap> IntHeap;
     203    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     204    heapSortTest<IntHeap>();
     205    heapIncreaseTest<IntHeap>();
     206
     207    typedef KaryHeap<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  // BinomHeap
     249  {
     250    typedef BinomHeap<Prio, ItemIntMap> IntHeap;
     251    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     252    heapSortTest<IntHeap>();
     253    heapIncreaseTest<IntHeap>();
     254
     255    typedef BinomHeap<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
    186275  return 0;
    187276}
Note: See TracChangeset for help on using the changeset viewer.