Changeset 948:f9e3f73e17f1 in lemon-main

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:

• CMakeLists.txt (modified) (2 diffs)
• CMakeLists.txt (modified) (3 diffs)
• heap_test.cc (modified) (1 diff)
• heap_test.cc (modified) (10 diffs)

test/CMakeLists.txt

@@ -73 +73 @@
   TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
   ADD_TEST(lp_test lp_test)
+  ADD_DEPENDENCIES(check lp_test)
 
   IF(WIN32 AND LEMON_HAVE_GLPK)
@@ -114 +115 @@
   TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
   ADD_TEST(mip_test mip_test)
+  ADD_DEPENDENCIES(check mip_test)
 
   IF(WIN32 AND LEMON_HAVE_GLPK)

test/CMakeLists.txt

@@ -14 +14 @@
 SET(TESTS
   adaptors_test
+  bellman_ford_test
   bfs_test
   circulation_test
@@ -25 +26 @@
   error_test
   euler_test
+  fractional_matching_test
   gomory_hu_test
   graph_copy_test
@@ -34 +36 @@
   maps_test
   matching_test
+  max_cardinality_search_test
+  max_clique_test
   min_cost_arborescence_test
   min_cost_flow_test
+  min_mean_cycle_test
+  nagamochi_ibaraki_test
   path_test
+  planarity_test
   preflow_test
   radix_sort_test

test/heap_test.cc

@@ -273 +273 @@
   }
 
+  {
+    typedef FibHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  {
+    typedef RadixHeap<ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef RadixHeap<IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  {
+    typedef BucketHeap<ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef BucketHeap<IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+
   return 0;
 }

test/heap_test.cc

@@ -26 +26 @@
 
 #include <lemon/smart_graph.h>
-
 #include <lemon/lgf_reader.h>
 #include <lemon/dijkstra.h>
@@ -32 +31 @@
 
 #include <lemon/bin_heap.h>
+#include <lemon/quad_heap.h>
+#include <lemon/dheap.h>
 #include <lemon/fib_heap.h>
+#include <lemon/pairing_heap.h>
 #include <lemon/radix_heap.h>
+#include <lemon/binomial_heap.h>
 #include <lemon/bucket_heap.h>
 
@@ -90 +93 @@
 void heapSortTest() {
   RangeMap<int> map(test_len, -1);
-
   Heap heap(map);
 
   std::vector<int> v(test_len);
-
   for (int i = 0; i < test_len; ++i) {
     v[i] = test_seq[i];
@@ -101 +102 @@
   std::sort(v.begin(), v.end());
   for (int i = 0; i < test_len; ++i) {
-    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
+    check(v[i] == heap.prio(), "Wrong order in heap sort.");
     heap.pop();
   }
@@ -113 +114 @@
 
   std::vector<int> v(test_len);
-
   for (int i = 0; i < test_len; ++i) {
     v[i] = test_seq[i];
@@ -124 +124 @@
   std::sort(v.begin(), v.end());
   for (int i = 0; i < test_len; ++i) {
-    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
+    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
     heap.pop();
   }
 }
-
-
 
 template <typename Heap>
@@ -145 +143 @@
     if (dijkstra.reached(s)) {
       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
-             "Error in a shortest path tree!");
+             "Error in shortest path tree.");
     }
   }
@@ -154 +152 @@
       Node s = digraph.source(a);
       check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
-             "Error in a shortest path tree!");
+             "Error in shortest path tree.");
     }
   }
@@ -176 +174 @@
     run();
 
+  // BinHeap
   {
     typedef BinHeap<Prio, ItemIntMap> IntHeap;
@@ -185 +184 @@
     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // QuadHeap
+  {
+    typedef QuadHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // DHeap
+  {
+    typedef DHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef DHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // FibHeap
+  {
+    typedef FibHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // PairingHeap
+  {
+    typedef PairingHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // RadixHeap
+  {
+    typedef RadixHeap<ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef RadixHeap<IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // BinomialHeap
+  {
+    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+  }
+
+  // BucketHeap, SimpleBucketHeap
+  {
+    typedef BucketHeap<ItemIntMap> IntHeap;
+    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
+
+    typedef BucketHeap<IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+
+    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
+    heapSortTest<SimpleIntHeap>();
   }