1.1 --- a/lemon/concepts/heap.h Thu Jul 10 16:13:50 2008 +0200
1.2 +++ b/lemon/concepts/heap.h Fri Jul 11 15:01:49 2008 +0200
1.3 @@ -181,12 +181,10 @@
1.4
1.5 Item item;
1.6 Prio prio;
1.7 - State state;
1.8 item=Item();
1.9 prio=Prio();
1.10 ignore_unused_variable_warning(item);
1.11 ignore_unused_variable_warning(prio);
1.12 - ignore_unused_variable_warning(state);
1.13
1.14 OwnItem own_item;
1.15 OwnPrio own_prio;
1.16 @@ -203,7 +201,9 @@
1.17 ignore_unused_variable_warning(heap2);
1.18
1.19 int s = heap.size();
1.20 + ignore_unused_variable_warning(s);
1.21 bool e = heap.empty();
1.22 + ignore_unused_variable_warning(e);
1.23
1.24 prio = heap.prio();
1.25 item = heap.top();
1.26 @@ -227,14 +227,9 @@
1.27 heap.erase(own_item);
1.28 heap.clear();
1.29
1.30 - state = heap.state(item);
1.31 - heap.state(item, state);
1.32 - state = heap.state(own_item);
1.33 + own_state = heap.state(own_item);
1.34 heap.state(own_item, own_state);
1.35
1.36 - state = _Heap::PRE_HEAP;
1.37 - state = _Heap::IN_HEAP;
1.38 - state = _Heap::POST_HEAP;
1.39 own_state = _Heap::PRE_HEAP;
1.40 own_state = _Heap::IN_HEAP;
1.41 own_state = _Heap::POST_HEAP;
2.1 --- a/test/CMakeLists.txt Thu Jul 10 16:13:50 2008 +0200
2.2 +++ b/test/CMakeLists.txt Fri Jul 11 15:01:49 2008 +0200
2.3 @@ -13,6 +13,7 @@
2.4 graph_copy_test
2.5 graph_test
2.6 graph_utils_test
2.7 + heap_test
2.8 kruskal_test
2.9 maps_test
2.10 path_test
3.1 --- a/test/Makefile.am Thu Jul 10 16:13:50 2008 +0200
3.2 +++ b/test/Makefile.am Fri Jul 11 15:01:49 2008 +0200
3.3 @@ -3,7 +3,6 @@
3.4
3.5 noinst_HEADERS += \
3.6 test/graph_test.h \
3.7 - test/heap_test.h \
3.8 test/graph_maps_test.h \
3.9 test/test_tools.h
3.10
3.11 @@ -18,6 +17,7 @@
3.12 test/graph_copy_test \
3.13 test/graph_test \
3.14 test/graph_utils_test \
3.15 + test/heap_test \
3.16 test/kruskal_test \
3.17 test/maps_test \
3.18 test/random_test \
3.19 @@ -40,7 +40,7 @@
3.20 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
3.21 test_graph_test_SOURCES = test/graph_test.cc
3.22 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
3.23 -# test_heap_test_SOURCES = test/heap_test.cc
3.24 +test_heap_test_SOURCES = test/heap_test.cc
3.25 test_kruskal_test_SOURCES = test/kruskal_test.cc
3.26 test_maps_test_SOURCES = test/maps_test.cc
3.27 test_path_test_SOURCES = test/path_test.cc
4.1 --- a/test/heap_test.cc Thu Jul 10 16:13:50 2008 +0200
4.2 +++ b/test/heap_test.cc Fri Jul 11 15:01:49 2008 +0200
4.3 @@ -24,113 +24,163 @@
4.4 #include <lemon/concept_check.h>
4.5 #include <lemon/concepts/heap.h>
4.6
4.7 -#include <lemon/list_graph.h>
4.8 +#include <lemon/smart_graph.h>
4.9
4.10 -#include <lemon/digraph_reader.h>
4.11 +#include <lemon/lgf_reader.h>
4.12 +#include <lemon/dijkstra.h>
4.13 +#include <lemon/maps.h>
4.14
4.15 #include <lemon/bin_heap.h>
4.16 -#include <lemon/fib_heap.h>
4.17 -#include <lemon/radix_heap.h>
4.18 -#include <lemon/bucket_heap.h>
4.19
4.20 #include "test_tools.h"
4.21
4.22 -#include "heap_test.h"
4.23 -
4.24 -#include <lemon/time_measure.h>
4.25 -
4.26 using namespace lemon;
4.27 using namespace lemon::concepts;
4.28
4.29 +typedef ListDigraph Digraph;
4.30 +DIGRAPH_TYPEDEFS(Digraph);
4.31 +
4.32 +char test_lgf[] =
4.33 + "@nodes\n"
4.34 + "label\n"
4.35 + "0\n"
4.36 + "1\n"
4.37 + "2\n"
4.38 + "3\n"
4.39 + "4\n"
4.40 + "5\n"
4.41 + "6\n"
4.42 + "7\n"
4.43 + "8\n"
4.44 + "9\n"
4.45 + "@arcs\n"
4.46 + " label capacity\n"
4.47 + "0 5 0 94\n"
4.48 + "3 9 1 11\n"
4.49 + "8 7 2 83\n"
4.50 + "1 2 3 94\n"
4.51 + "5 7 4 35\n"
4.52 + "7 4 5 84\n"
4.53 + "9 5 6 38\n"
4.54 + "0 4 7 96\n"
4.55 + "6 7 8 6\n"
4.56 + "3 1 9 27\n"
4.57 + "5 2 10 77\n"
4.58 + "5 6 11 69\n"
4.59 + "6 5 12 41\n"
4.60 + "4 6 13 70\n"
4.61 + "3 2 14 45\n"
4.62 + "7 9 15 93\n"
4.63 + "5 9 16 50\n"
4.64 + "9 0 17 94\n"
4.65 + "9 6 18 67\n"
4.66 + "0 9 19 86\n"
4.67 + "@attributes\n"
4.68 + "source 3\n";
4.69 +
4.70 +int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34};
4.71 +int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37};
4.72 +
4.73 +int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
4.74 +
4.75 +template <typename Heap>
4.76 +void heapSortTest() {
4.77 + RangeMap<int> map(test_len, -1);
4.78 +
4.79 + Heap heap(map);
4.80 +
4.81 + std::vector<int> v(test_len);
4.82 +
4.83 + for (int i = 0; i < test_len; ++i) {
4.84 + v[i] = test_seq[i];
4.85 + heap.push(i, v[i]);
4.86 + }
4.87 + std::sort(v.begin(), v.end());
4.88 + for (int i = 0; i < test_len; ++i) {
4.89 + check(v[i] == heap.prio() ,"Wrong order in heap sort.");
4.90 + heap.pop();
4.91 + }
4.92 +}
4.93 +
4.94 +template <typename Heap>
4.95 +void heapIncreaseTest() {
4.96 + RangeMap<int> map(test_len, -1);
4.97 +
4.98 + Heap heap(map);
4.99 +
4.100 + std::vector<int> v(test_len);
4.101 +
4.102 + for (int i = 0; i < test_len; ++i) {
4.103 + v[i] = test_seq[i];
4.104 + heap.push(i, v[i]);
4.105 + }
4.106 + for (int i = 0; i < test_len; ++i) {
4.107 + v[i] += test_inc[i];
4.108 + heap.increase(i, v[i]);
4.109 + }
4.110 + std::sort(v.begin(), v.end());
4.111 + for (int i = 0; i < test_len; ++i) {
4.112 + check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
4.113 + heap.pop();
4.114 + }
4.115 +}
4.116 +
4.117 +
4.118 +
4.119 +template <typename Heap>
4.120 +void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
4.121 + Node source) {
4.122 +
4.123 + typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
4.124 + Create dijkstra(digraph, length);
4.125 +
4.126 + dijkstra.run(source);
4.127 +
4.128 + for(ArcIt a(digraph); a != INVALID; ++a) {
4.129 + Node s = digraph.source(a);
4.130 + Node t = digraph.target(a);
4.131 + if (dijkstra.reached(s)) {
4.132 + check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
4.133 + "Error in a shortest path tree!");
4.134 + }
4.135 + }
4.136 +
4.137 + for(NodeIt n(digraph); n != INVALID; ++n) {
4.138 + if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
4.139 + Arc a = dijkstra.predArc(n);
4.140 + Node s = digraph.source(a);
4.141 + check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
4.142 + "Error in a shortest path tree!");
4.143 + }
4.144 + }
4.145 +
4.146 +}
4.147 +
4.148 int main() {
4.149
4.150 typedef int Item;
4.151 typedef int Prio;
4.152 - typedef IntIntMap ItemIntMap;
4.153 + typedef RangeMap<int> ItemIntMap;
4.154 +
4.155 + Digraph digraph;
4.156 + IntArcMap length(digraph);
4.157 + Node source;
4.158
4.159 - typedef ListDigraph Digraph;
4.160 -
4.161 - typedef Digraph::Arc Arc;
4.162 - typedef Digraph::Node Node;
4.163 - typedef Digraph::ArcIt ArcIt;
4.164 - typedef Digraph::NodeIt NodeIt;
4.165 - typedef Digraph::ArcMap<int> LengthMap;
4.166 -
4.167 - Digraph digraph;
4.168 - LengthMap length(digraph);
4.169 - Node start;
4.170 -
4.171 - /// \todo create own test digraph
4.172 -
4.173 - std::string f_name;
4.174 - if( getenv("srcdir") )
4.175 - f_name = std::string(getenv("srcdir"));
4.176 - else f_name = ".";
4.177 - f_name += "/test/dijkstra_test.lgf";
4.178 -
4.179 - std::ifstream input(f_name.c_str());
4.180 - check(input, "Input file '" << f_name << "' not found.");
4.181 - DigraphReader<Digraph>(input, digraph).
4.182 - readArcMap("capacity", length).
4.183 - readNode("source", start).
4.184 + std::istringstream input(test_lgf);
4.185 + digraphReader(input, digraph).
4.186 + arcMap("capacity", length).
4.187 + node("source", source).
4.188 run();
4.189
4.190 {
4.191 - std::cout << "Checking Bin Heap" << std::endl;
4.192 -
4.193 typedef BinHeap<Prio, ItemIntMap> IntHeap;
4.194 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
4.195 - heapSortTest<IntHeap>(100);
4.196 - heapIncreaseTest<IntHeap>(100);
4.197 + heapSortTest<IntHeap>();
4.198 + heapIncreaseTest<IntHeap>();
4.199
4.200 - typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
4.201 - checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
4.202 - Timer timer;
4.203 - dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
4.204 - std::cout << timer << std::endl;
4.205 - }
4.206 - {
4.207 - std::cout << "Checking Fib Heap" << std::endl;
4.208 -
4.209 - typedef FibHeap<Prio, ItemIntMap> IntHeap;
4.210 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
4.211 - heapSortTest<IntHeap>(100);
4.212 - heapIncreaseTest<IntHeap>(100);
4.213 -
4.214 - typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
4.215 - checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
4.216 - Timer timer;
4.217 - dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
4.218 - std::cout << timer << std::endl;
4.219 - }
4.220 - {
4.221 - std::cout << "Checking Radix Heap" << std::endl;
4.222 -
4.223 - typedef RadixHeap<ItemIntMap> IntHeap;
4.224 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
4.225 - heapSortTest<IntHeap>(100);
4.226 - heapIncreaseTest<IntHeap>(100);
4.227 -
4.228 - typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
4.229 - checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
4.230 - Timer timer;
4.231 - dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
4.232 - std::cout << timer << std::endl;
4.233 - }
4.234 -
4.235 - {
4.236 - std::cout << "Checking Bucket Heap" << std::endl;
4.237 -
4.238 - typedef BucketHeap<ItemIntMap> IntHeap;
4.239 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
4.240 - heapSortTest<IntHeap>(100);
4.241 - heapIncreaseTest<IntHeap>(100);
4.242 -
4.243 - typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
4.244 - checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
4.245 - Timer timer;
4.246 - dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
4.247 - std::cout << timer << std::endl;
4.248 + typedef BinHeap<Prio, IntNodeMap > NodeHeap;
4.249 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
4.250 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
4.251 }
4.252
4.253 return 0;
5.1 --- a/test/heap_test.h Thu Jul 10 16:13:50 2008 +0200
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,123 +0,0 @@
5.4 -/* -*- C++ -*-
5.5 - *
5.6 - * This file is a part of LEMON, a generic C++ optimization library
5.7 - *
5.8 - * Copyright (C) 2003-2008
5.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 - *
5.12 - * Permission to use, modify and distribute this software is granted
5.13 - * provided that this copyright notice appears in all copies. For
5.14 - * precise terms see the accompanying LICENSE file.
5.15 - *
5.16 - * This software is provided "AS IS" with no warranty of any kind,
5.17 - * express or implied, and with no claim as to its suitability for any
5.18 - * purpose.
5.19 - *
5.20 - */
5.21 -
5.22 -#include <vector>
5.23 -#include <algorithm>
5.24 -
5.25 -#include <lemon/dijkstra.h>
5.26 -
5.27 -class IntIntMap : public std::vector<int> {
5.28 -public:
5.29 - typedef std::vector<int> Parent;
5.30 -
5.31 - typedef int Key;
5.32 - typedef int Value;
5.33 -
5.34 - IntIntMap() : Parent() {}
5.35 - IntIntMap(int n) : Parent(n) {}
5.36 - IntIntMap(int n, int v) : Parent(n, v) {}
5.37 -
5.38 - void set(int key, int value) {
5.39 - Parent::operator[](key) = value;
5.40 - }
5.41 -};
5.42 -
5.43 -
5.44 -template <typename _Heap>
5.45 -void heapSortTest(int n) {
5.46 - typedef _Heap Heap;
5.47 - IntIntMap map(n, -1);
5.48 -
5.49 - Heap heap(map);
5.50 -
5.51 - std::vector<int> v(n);
5.52 -
5.53 - for (int i = 0; i < n; ++i) {
5.54 - v[i] = rnd[1000];
5.55 - heap.push(i, v[i]);
5.56 - }
5.57 - std::sort(v.begin(), v.end());
5.58 - for (int i = 0; i < n; ++i) {
5.59 - check(v[i] == heap.prio() ,"Wrong order in heap sort.");
5.60 - heap.pop();
5.61 - }
5.62 -}
5.63 -
5.64 -template <typename _Heap>
5.65 -void heapIncreaseTest(int n) {
5.66 - typedef _Heap Heap;
5.67 - IntIntMap map(n, -1);
5.68 -
5.69 - Heap heap(map);
5.70 -
5.71 - std::vector<int> v(n);
5.72 -
5.73 - for (int i = 0; i < n; ++i) {
5.74 - v[i] = rnd[1000];
5.75 - heap.push(i, v[i]);
5.76 - }
5.77 - for (int i = 0; i < n; ++i) {
5.78 - v[i] += rnd[1000];
5.79 - heap.increase(i, v[i]);
5.80 - }
5.81 - std::sort(v.begin(), v.end());
5.82 - for (int i = 0; i < n; ++i) {
5.83 - check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
5.84 - heap.pop();
5.85 - }
5.86 -}
5.87 -
5.88 -
5.89 -
5.90 -template <typename _Digraph, typename _LengthMap, typename _Heap>
5.91 -void dijkstraHeapTest(_Digraph& digraph, _LengthMap& length,
5.92 - typename _Digraph::Node& start) {
5.93 -
5.94 - typedef _Heap Heap;
5.95 - typedef _Digraph Digraph;
5.96 - typedef _LengthMap LengthMap;
5.97 -
5.98 - typedef typename Digraph::Node Node;
5.99 - typedef typename Digraph::Arc Arc;
5.100 - typedef typename Digraph::NodeIt NodeIt;
5.101 - typedef typename Digraph::ArcIt ArcIt;
5.102 -
5.103 - typename Dijkstra<Digraph, LengthMap>::template DefStandardHeap<Heap>::
5.104 - Create dijkstra(digraph, length);
5.105 -
5.106 - dijkstra.run(start);
5.107 -
5.108 - for(ArcIt e(digraph); e!=INVALID; ++e) {
5.109 - Node u=digraph.source(e);
5.110 - Node v=digraph.target(e);
5.111 - if (dijkstra.reached(u)) {
5.112 - check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
5.113 - "Error in a shortest path tree arc!");
5.114 - }
5.115 - }
5.116 -
5.117 - for(NodeIt v(digraph); v!=INVALID; ++v) {
5.118 - if ( dijkstra.reached(v) && dijkstra.predArc(v) != INVALID ) {
5.119 - Arc e=dijkstra.predArc(v);
5.120 - Node u=digraph.source(e);
5.121 - check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
5.122 - "Error in a shortest path tree arc!");
5.123 - }
5.124 - }
5.125 -
5.126 -}