COIN-OR::LEMON - Graph Library

Changeset 942:2b6bffe0e7e8 in lemon-1.2 for test


Ignore:
Timestamp:
12/20/11 18:15:14 (8 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
941:7c4ba7daaf5f (diff), 915:633956ca9421 (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

Location:
test
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • test/CMakeLists.txt

    r874 r942  
    77  ${PROJECT_BINARY_DIR}/lemon
    88)
     9
     10SET(TEST_WITH_VALGRIND "NO" CACHE STRING
     11  "Run the test with valgrind (YES/NO).")
     12SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
    913
    1014SET(TESTS
     
    3034  heap_test
    3135  kruskal_test
     36  lgf_test
    3237  maps_test
    3338  matching_test
     
    4651
    4752IF(LEMON_HAVE_LP)
    48   ADD_EXECUTABLE(lp_test lp_test.cc)
     53  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     54    ADD_EXECUTABLE(lp_test lp_test.cc)
     55  ELSE()
     56    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
     57  ENDIF()
     58
    4959  SET(LP_TEST_LIBS lemon)
    5060
     
    6171  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
    6272  ADD_TEST(lp_test lp_test)
     73  ADD_DEPENDENCIES(check lp_test)
    6374
    6475  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    8293
    8394IF(LEMON_HAVE_MIP)
    84   ADD_EXECUTABLE(mip_test mip_test.cc)
     95  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     96    ADD_EXECUTABLE(mip_test mip_test.cc)
     97  ELSE()
     98    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
     99  ENDIF()
     100
    85101  SET(MIP_TEST_LIBS lemon)
    86102
     
    97113  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
    98114  ADD_TEST(mip_test mip_test)
     115  ADD_DEPENDENCIES(check mip_test)
    99116
    100117  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    118135
    119136FOREACH(TEST_NAME ${TESTS})
    120   ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     137  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     138    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     139  ELSE()
     140    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
     141  ENDIF()
    121142  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
    122   ADD_TEST(${TEST_NAME} ${TEST_NAME})
     143    IF(TEST_WITH_VALGRIND)
     144      ADD_TEST(${TEST_NAME}
     145        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
     146        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
     147    ELSE()
     148      ADD_TEST(${TEST_NAME} ${TEST_NAME})
     149    ENDIF()
     150  ADD_DEPENDENCIES(check ${TEST_NAME})
    123151ENDFOREACH()
  • test/CMakeLists.txt

    r937 r942  
    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
     
    3739  min_cost_arborescence_test
    3840  min_cost_flow_test
     41  min_mean_cycle_test
    3942  path_test
     43  planarity_test
    4044  preflow_test
    4145  radix_sort_test
  • test/Makefile.am

    r874 r942  
    3232        test/heap_test \
    3333        test/kruskal_test \
     34        test/lgf_test \
    3435        test/maps_test \
    3536        test/matching_test \
     
    8182test_kruskal_test_SOURCES = test/kruskal_test.cc
    8283test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
     84test_lgf_test_SOURCES = test/lgf_test.cc
    8385test_lp_test_SOURCES = test/lp_test.cc
    8486test_maps_test_SOURCES = test/maps_test.cc
  • test/Makefile.am

    r937 r942  
     1if USE_VALGRIND
     2TESTS_ENVIRONMENT=$(top_srcdir)/scripts/valgrind-wrapper.sh
     3endif
     4
    15EXTRA_DIST += \
    26        test/CMakeLists.txt
     
    812check_PROGRAMS += \
    913        test/adaptors_test \
     14        test/bellman_ford_test \
    1015        test/bfs_test \
    1116        test/circulation_test \
     
    1924        test/error_test \
    2025        test/euler_test \
     26        test/fractional_matching_test \
    2127        test/gomory_hu_test \
    2228        test/graph_copy_test \
     
    3137        test/min_cost_arborescence_test \
    3238        test/min_cost_flow_test \
     39        test/min_mean_cycle_test \
    3340        test/path_test \
     41        test/planarity_test \
    3442        test/preflow_test \
    3543        test/radix_sort_test \
     
    5462
    5563test_adaptors_test_SOURCES = test/adaptors_test.cc
     64test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    5665test_bfs_test_SOURCES = test/bfs_test.cc
    5766test_circulation_test_SOURCES = test/circulation_test.cc
     
    6574test_error_test_SOURCES = test/error_test.cc
    6675test_euler_test_SOURCES = test/euler_test.cc
     76test_fractional_matching_test_SOURCES = test/fractional_matching_test.cc
    6777test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
    6878test_graph_copy_test_SOURCES = test/graph_copy_test.cc
     
    7989test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    8090test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
     91test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
    8192test_path_test_SOURCES = test/path_test.cc
     93test_planarity_test_SOURCES = test/planarity_test.cc
    8294test_preflow_test_SOURCES = test/preflow_test.cc
    8395test_radix_sort_test_SOURCES = test/radix_sort_test.cc
  • test/dfs_test.cc

    r877 r942  
    5151  "@attributes\n"
    5252  "source 0\n"
    53   "target 5\n";
     53  "target 5\n"
     54  "source1 6\n"
     55  "target1 3\n";
     56
    5457
    5558void checkDfsCompile()
     
    180183  Digraph G;
    181184  Node s, t;
     185  Node s1, t1;
    182186
    183187  std::istringstream input(test_lgf);
     
    185189    node("source", s).
    186190    node("target", t).
     191    node("source1", s1).
     192    node("target1", t1).
    187193    run();
    188194
     
    211217
    212218  {
     219  Dfs<Digraph> dfs(G);
     220  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
     221  }
     222 
     223  {
    213224    NullMap<Node,Arc> myPredMap;
    214225    dfs(G).predMap(myPredMap).run(s);
  • test/dfs_test.cc

    r937 r942  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8787    b = const_dfs_test.emptyQueue();
    8888    i = const_dfs_test.queueSize();
    89    
     89
    9090    dfs_test.start();
    9191    dfs_test.start(t);
     
    113113    concepts::ReadWriteMap<Node,bool> reached_map;
    114114    concepts::WriteMap<Node,bool> processed_map;
    115    
     115
    116116    dfs_test
    117117      .predMap(pred_map)
     
    130130    b = dfs_test.emptyQueue();
    131131    i = dfs_test.queueSize();
    132    
     132
    133133    dfs_test.start();
    134134    dfs_test.start(t);
  • test/heap_test.cc

    r855 r921  
    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 r921  
    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
  • test/preflow_test.cc

    r877 r902  
    157157}
    158158
     159void initFlowTest()
     160{
     161  DIGRAPH_TYPEDEFS(SmartDigraph);
     162 
     163  SmartDigraph g;
     164  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     165  Node s=g.addNode(); Node t=g.addNode();
     166  Node n1=g.addNode(); Node n2=g.addNode();
     167  Arc a;
     168  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
     169  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
     170  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
     171
     172  Preflow<SmartDigraph> pre(g,cap,s,t);
     173  pre.init(iflow);
     174  pre.startFirstPhase();
     175  check(pre.flowValue() == 10, "The incorrect max flow value.");
     176  check(pre.minCut(s), "Wrong min cut (Node s).");
     177  check(pre.minCut(n1), "Wrong min cut (Node n1).");
     178  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
     179  check(!pre.minCut(t), "Wrong min cut (Node t).");
     180}
     181
     182
    159183int main() {
    160184
     
    247271        "The max flow value or the three min cut values are incorrect.");
    248272
     273  initFlowTest();
     274 
    249275  return 0;
    250276}
  • test/preflow_test.cc

    r901 r902  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9696  const PreflowType& const_preflow_test = preflow_test;
    9797
     98  const PreflowType::Elevator& elev = const_preflow_test.elevator();
     99  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
     100  PreflowType::Tolerance tol = const_preflow_test.tolerance();
     101  preflow_test.tolerance(tol);
     102
    98103  preflow_test
    99104    .capacityMap(cap)
     
    114119  b = const_preflow_test.minCut(n);
    115120  const_preflow_test.minCutMap(cut);
    116  
     121
    117122  ignore_unused_variable_warning(fm);
    118123}
Note: See TracChangeset for help on using the changeset viewer.