COIN-OR::LEMON - Graph Library

Changeset 948:f9e3f73e17f1 in lemon-main


Ignore:
Timestamp:
07/13/11 15:04:03 (13 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
943:4f9e5801224e (diff), 947:0dba9b96550a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #419

Location:
test
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • test/CMakeLists.txt

    r939 r948  
    7373  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
    7474  ADD_TEST(lp_test lp_test)
     75  ADD_DEPENDENCIES(check lp_test)
    7576
    7677  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    114115  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
    115116  ADD_TEST(mip_test mip_test)
     117  ADD_DEPENDENCIES(check mip_test)
    116118
    117119  IF(WIN32 AND LEMON_HAVE_GLPK)
  • test/CMakeLists.txt

    r945 r948  
    1414SET(TESTS
    1515  adaptors_test
     16  bellman_ford_test
    1617  bfs_test
    1718  circulation_test
     
    2526  error_test
    2627  euler_test
     28  fractional_matching_test
    2729  gomory_hu_test
    2830  graph_copy_test
     
    3436  maps_test
    3537  matching_test
     38  max_cardinality_search_test
     39  max_clique_test
    3640  min_cost_arborescence_test
    3741  min_cost_flow_test
     42  min_mean_cycle_test
     43  nagamochi_ibaraki_test
    3844  path_test
     45  planarity_test
    3946  preflow_test
    4047  radix_sort_test
  • test/heap_test.cc

    r855 r948  
    273273  }
    274274
     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
    275309  return 0;
    276310}
  • test/heap_test.cc

    r681 r948  
    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/quad_heap.h>
     34#include <lemon/dheap.h>
    3435#include <lemon/fib_heap.h>
     36#include <lemon/pairing_heap.h>
    3537#include <lemon/radix_heap.h>
     38#include <lemon/binomial_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;
     
    185184    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    186185    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>();
    187273  }
    188274
Note: See TracChangeset for help on using the changeset viewer.