COIN-OR::LEMON - Graph Library

Changeset 701:d1a9224f1e30 in lemon-main


Ignore:
Timestamp:
07/09/09 02:38:01 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Add fourary, k-ary, pairing and binomial heaps (#301)
These structures were implemented by Dorian Batha.

Files:
4 added
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r681 r701  
    6060        lemon/bfs.h \
    6161        lemon/bin_heap.h \
     62        lemon/binom_heap.h \
    6263        lemon/bucket_heap.h \
    6364        lemon/cbc.h \
     
    7980        lemon/euler.h \
    8081        lemon/fib_heap.h \
     82        lemon/fourary_heap.h \
    8183        lemon/full_graph.h \
    8284        lemon/glpk.h \
     
    8587        lemon/grid_graph.h \
    8688        lemon/hypercube_graph.h \
     89        lemon/kary_heap.h \
    8790        lemon/kruskal.h \
    8891        lemon/hao_orlin.h \
     
    100103        lemon/nauty_reader.h \
    101104        lemon/network_simplex.h \
     105        lemon/pairing_heap.h \
    102106        lemon/path.h \
    103107        lemon/preflow.h \
  • test/heap_test.cc

    r681 r701  
    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>
    3435#include <lemon/fib_heap.h>
     36#include <lemon/pairing_heap.h>
    3537#include <lemon/radix_heap.h>
     38#include <lemon/binom_heap.h>
    3639#include <lemon/bucket_heap.h>
    3740
     
    9093void heapSortTest() {
    9194  RangeMap<int> map(test_len, -1);
    92 
    9395  Heap heap(map);
    9496
    9597  std::vector<int> v(test_len);
    96 
    9798  for (int i = 0; i < test_len; ++i) {
    9899    v[i] = test_seq[i];
     
    101102  std::sort(v.begin(), v.end());
    102103  for (int i = 0; i < test_len; ++i) {
    103     check(v[i] == heap.prio() ,"Wrong order in heap sort.");
     104    check(v[i] == heap.prio(), "Wrong order in heap sort.");
    104105    heap.pop();
    105106  }
     
    113114
    114115  std::vector<int> v(test_len);
    115 
    116116  for (int i = 0; i < test_len; ++i) {
    117117    v[i] = test_seq[i];
     
    124124  std::sort(v.begin(), v.end());
    125125  for (int i = 0; i < test_len; ++i) {
    126     check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
     126    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
    127127    heap.pop();
    128128  }
    129129}
    130 
    131 
    132130
    133131template <typename Heap>
     
    145143    if (dijkstra.reached(s)) {
    146144      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
    147              "Error in a shortest path tree!");
     145             "Error in shortest path tree.");
    148146    }
    149147  }
     
    154152      Node s = digraph.source(a);
    155153      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
    156              "Error in a shortest path tree!");
     154             "Error in shortest path tree.");
    157155    }
    158156  }
     
    176174    run();
    177175
     176  // BinHeap
    178177  {
    179178    typedef BinHeap<Prio, ItemIntMap> IntHeap;
     
    187186  }
    188187
     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
    189213  {
    190214    typedef FibHeap<Prio, ItemIntMap> IntHeap;
     
    198222  }
    199223
     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
    200237  {
    201238    typedef RadixHeap<ItemIntMap> IntHeap;
     
    209246  }
    210247
     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
    211261  {
    212262    typedef BucketHeap<ItemIntMap> IntHeap;
     
    218268    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    219269    dijkstraHeapTest<NodeHeap>(digraph, length, source);
    220   }
    221 
     270
     271    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
     272    heapSortTest<SimpleIntHeap>();
     273  }
    222274
    223275  return 0;
Note: See TracChangeset for help on using the changeset viewer.