1.1 --- a/test/heap_test.cc Thu Jul 10 16:13:50 2008 +0200
1.2 +++ b/test/heap_test.cc Fri Jul 11 15:01:49 2008 +0200
1.3 @@ -24,113 +24,163 @@
1.4 #include <lemon/concept_check.h>
1.5 #include <lemon/concepts/heap.h>
1.6
1.7 -#include <lemon/list_graph.h>
1.8 +#include <lemon/smart_graph.h>
1.9
1.10 -#include <lemon/digraph_reader.h>
1.11 +#include <lemon/lgf_reader.h>
1.12 +#include <lemon/dijkstra.h>
1.13 +#include <lemon/maps.h>
1.14
1.15 #include <lemon/bin_heap.h>
1.16 -#include <lemon/fib_heap.h>
1.17 -#include <lemon/radix_heap.h>
1.18 -#include <lemon/bucket_heap.h>
1.19
1.20 #include "test_tools.h"
1.21
1.22 -#include "heap_test.h"
1.23 -
1.24 -#include <lemon/time_measure.h>
1.25 -
1.26 using namespace lemon;
1.27 using namespace lemon::concepts;
1.28
1.29 +typedef ListDigraph Digraph;
1.30 +DIGRAPH_TYPEDEFS(Digraph);
1.31 +
1.32 +char test_lgf[] =
1.33 + "@nodes\n"
1.34 + "label\n"
1.35 + "0\n"
1.36 + "1\n"
1.37 + "2\n"
1.38 + "3\n"
1.39 + "4\n"
1.40 + "5\n"
1.41 + "6\n"
1.42 + "7\n"
1.43 + "8\n"
1.44 + "9\n"
1.45 + "@arcs\n"
1.46 + " label capacity\n"
1.47 + "0 5 0 94\n"
1.48 + "3 9 1 11\n"
1.49 + "8 7 2 83\n"
1.50 + "1 2 3 94\n"
1.51 + "5 7 4 35\n"
1.52 + "7 4 5 84\n"
1.53 + "9 5 6 38\n"
1.54 + "0 4 7 96\n"
1.55 + "6 7 8 6\n"
1.56 + "3 1 9 27\n"
1.57 + "5 2 10 77\n"
1.58 + "5 6 11 69\n"
1.59 + "6 5 12 41\n"
1.60 + "4 6 13 70\n"
1.61 + "3 2 14 45\n"
1.62 + "7 9 15 93\n"
1.63 + "5 9 16 50\n"
1.64 + "9 0 17 94\n"
1.65 + "9 6 18 67\n"
1.66 + "0 9 19 86\n"
1.67 + "@attributes\n"
1.68 + "source 3\n";
1.69 +
1.70 +int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34};
1.71 +int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37};
1.72 +
1.73 +int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
1.74 +
1.75 +template <typename Heap>
1.76 +void heapSortTest() {
1.77 + RangeMap<int> map(test_len, -1);
1.78 +
1.79 + Heap heap(map);
1.80 +
1.81 + std::vector<int> v(test_len);
1.82 +
1.83 + for (int i = 0; i < test_len; ++i) {
1.84 + v[i] = test_seq[i];
1.85 + heap.push(i, v[i]);
1.86 + }
1.87 + std::sort(v.begin(), v.end());
1.88 + for (int i = 0; i < test_len; ++i) {
1.89 + check(v[i] == heap.prio() ,"Wrong order in heap sort.");
1.90 + heap.pop();
1.91 + }
1.92 +}
1.93 +
1.94 +template <typename Heap>
1.95 +void heapIncreaseTest() {
1.96 + RangeMap<int> map(test_len, -1);
1.97 +
1.98 + Heap heap(map);
1.99 +
1.100 + std::vector<int> v(test_len);
1.101 +
1.102 + for (int i = 0; i < test_len; ++i) {
1.103 + v[i] = test_seq[i];
1.104 + heap.push(i, v[i]);
1.105 + }
1.106 + for (int i = 0; i < test_len; ++i) {
1.107 + v[i] += test_inc[i];
1.108 + heap.increase(i, v[i]);
1.109 + }
1.110 + std::sort(v.begin(), v.end());
1.111 + for (int i = 0; i < test_len; ++i) {
1.112 + check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
1.113 + heap.pop();
1.114 + }
1.115 +}
1.116 +
1.117 +
1.118 +
1.119 +template <typename Heap>
1.120 +void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
1.121 + Node source) {
1.122 +
1.123 + typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
1.124 + Create dijkstra(digraph, length);
1.125 +
1.126 + dijkstra.run(source);
1.127 +
1.128 + for(ArcIt a(digraph); a != INVALID; ++a) {
1.129 + Node s = digraph.source(a);
1.130 + Node t = digraph.target(a);
1.131 + if (dijkstra.reached(s)) {
1.132 + check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
1.133 + "Error in a shortest path tree!");
1.134 + }
1.135 + }
1.136 +
1.137 + for(NodeIt n(digraph); n != INVALID; ++n) {
1.138 + if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
1.139 + Arc a = dijkstra.predArc(n);
1.140 + Node s = digraph.source(a);
1.141 + check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
1.142 + "Error in a shortest path tree!");
1.143 + }
1.144 + }
1.145 +
1.146 +}
1.147 +
1.148 int main() {
1.149
1.150 typedef int Item;
1.151 typedef int Prio;
1.152 - typedef IntIntMap ItemIntMap;
1.153 + typedef RangeMap<int> ItemIntMap;
1.154 +
1.155 + Digraph digraph;
1.156 + IntArcMap length(digraph);
1.157 + Node source;
1.158
1.159 - typedef ListDigraph Digraph;
1.160 -
1.161 - typedef Digraph::Arc Arc;
1.162 - typedef Digraph::Node Node;
1.163 - typedef Digraph::ArcIt ArcIt;
1.164 - typedef Digraph::NodeIt NodeIt;
1.165 - typedef Digraph::ArcMap<int> LengthMap;
1.166 -
1.167 - Digraph digraph;
1.168 - LengthMap length(digraph);
1.169 - Node start;
1.170 -
1.171 - /// \todo create own test digraph
1.172 -
1.173 - std::string f_name;
1.174 - if( getenv("srcdir") )
1.175 - f_name = std::string(getenv("srcdir"));
1.176 - else f_name = ".";
1.177 - f_name += "/test/dijkstra_test.lgf";
1.178 -
1.179 - std::ifstream input(f_name.c_str());
1.180 - check(input, "Input file '" << f_name << "' not found.");
1.181 - DigraphReader<Digraph>(input, digraph).
1.182 - readArcMap("capacity", length).
1.183 - readNode("source", start).
1.184 + std::istringstream input(test_lgf);
1.185 + digraphReader(input, digraph).
1.186 + arcMap("capacity", length).
1.187 + node("source", source).
1.188 run();
1.189
1.190 {
1.191 - std::cout << "Checking Bin Heap" << std::endl;
1.192 -
1.193 typedef BinHeap<Prio, ItemIntMap> IntHeap;
1.194 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.195 - heapSortTest<IntHeap>(100);
1.196 - heapIncreaseTest<IntHeap>(100);
1.197 + heapSortTest<IntHeap>();
1.198 + heapIncreaseTest<IntHeap>();
1.199
1.200 - typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
1.201 - checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
1.202 - Timer timer;
1.203 - dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
1.204 - std::cout << timer << std::endl;
1.205 - }
1.206 - {
1.207 - std::cout << "Checking Fib Heap" << std::endl;
1.208 -
1.209 - typedef FibHeap<Prio, ItemIntMap> IntHeap;
1.210 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.211 - heapSortTest<IntHeap>(100);
1.212 - heapIncreaseTest<IntHeap>(100);
1.213 -
1.214 - typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
1.215 - checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
1.216 - Timer timer;
1.217 - dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
1.218 - std::cout << timer << std::endl;
1.219 - }
1.220 - {
1.221 - std::cout << "Checking Radix Heap" << std::endl;
1.222 -
1.223 - typedef RadixHeap<ItemIntMap> IntHeap;
1.224 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.225 - heapSortTest<IntHeap>(100);
1.226 - heapIncreaseTest<IntHeap>(100);
1.227 -
1.228 - typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
1.229 - checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
1.230 - Timer timer;
1.231 - dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
1.232 - std::cout << timer << std::endl;
1.233 - }
1.234 -
1.235 - {
1.236 - std::cout << "Checking Bucket Heap" << std::endl;
1.237 -
1.238 - typedef BucketHeap<ItemIntMap> IntHeap;
1.239 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.240 - heapSortTest<IntHeap>(100);
1.241 - heapIncreaseTest<IntHeap>(100);
1.242 -
1.243 - typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
1.244 - checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
1.245 - Timer timer;
1.246 - dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
1.247 - std::cout << timer << std::endl;
1.248 + typedef BinHeap<Prio, IntNodeMap > NodeHeap;
1.249 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.250 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.251 }
1.252
1.253 return 0;