Changes in / [747:6f7c1052d260:755:5d313b76f323] in lemon
- Files:
-
- 4 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r747 r755 61 61 lemon/bfs.h \ 62 62 lemon/bin_heap.h \ 63 lemon/binom_heap.h \ 63 64 lemon/bucket_heap.h \ 64 65 lemon/cbc.h \ … … 80 81 lemon/euler.h \ 81 82 lemon/fib_heap.h \ 83 lemon/fourary_heap.h \ 82 84 lemon/full_graph.h \ 83 85 lemon/glpk.h \ … … 86 88 lemon/grid_graph.h \ 87 89 lemon/hypercube_graph.h \ 90 lemon/kary_heap.h \ 88 91 lemon/kruskal.h \ 89 92 lemon/hao_orlin.h \ … … 100 103 lemon/nauty_reader.h \ 101 104 lemon/network_simplex.h \ 105 lemon/pairing_heap.h \ 102 106 lemon/path.h \ 103 107 lemon/preflow.h \ -
test/heap_test.cc
r728 r749 26 26 27 27 #include <lemon/smart_graph.h> 28 29 28 #include <lemon/lgf_reader.h> 30 29 #include <lemon/dijkstra.h> … … 32 31 33 32 #include <lemon/bin_heap.h> 33 #include <lemon/fourary_heap.h> 34 #include <lemon/kary_heap.h> 34 35 #include <lemon/fib_heap.h> 36 #include <lemon/pairing_heap.h> 35 37 #include <lemon/radix_heap.h> 38 #include <lemon/binom_heap.h> 36 39 #include <lemon/bucket_heap.h> 37 40 … … 90 93 void heapSortTest() { 91 94 RangeMap<int> map(test_len, -1); 92 93 95 Heap heap(map); 94 96 95 97 std::vector<int> v(test_len); 96 97 98 for (int i = 0; i < test_len; ++i) { 98 99 v[i] = test_seq[i]; … … 101 102 std::sort(v.begin(), v.end()); 102 103 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."); 104 105 heap.pop(); 105 106 } … … 113 114 114 115 std::vector<int> v(test_len); 115 116 116 for (int i = 0; i < test_len; ++i) { 117 117 v[i] = test_seq[i]; … … 124 124 std::sort(v.begin(), v.end()); 125 125 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."); 127 127 heap.pop(); 128 128 } 129 129 } 130 131 132 130 133 131 template <typename Heap> … … 145 143 if (dijkstra.reached(s)) { 146 144 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], 147 "Error in a shortest path tree!");145 "Error in shortest path tree."); 148 146 } 149 147 } … … 154 152 Node s = digraph.source(a); 155 153 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], 156 "Error in a shortest path tree!");154 "Error in shortest path tree."); 157 155 } 158 156 } … … 176 174 run(); 177 175 176 // BinHeap 178 177 { 179 178 typedef BinHeap<Prio, ItemIntMap> IntHeap; … … 187 186 } 188 187 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 189 213 { 190 214 typedef FibHeap<Prio, ItemIntMap> IntHeap; … … 198 222 } 199 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 200 237 { 201 238 typedef RadixHeap<ItemIntMap> IntHeap; … … 209 246 } 210 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 211 261 { 212 262 typedef BucketHeap<ItemIntMap> IntHeap; … … 218 268 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 219 269 dijkstraHeapTest<NodeHeap>(digraph, length, source); 220 } 221 270 271 typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap; 272 heapSortTest<SimpleIntHeap>(); 273 } 222 274 223 275 return 0;
Note: See TracChangeset
for help on using the changeset viewer.