Cleaning of heap test and bug fix in heap concept check (ticket #100)
authorBalazs Dezso <deba@inf.elte.hu>
Fri, 11 Jul 2008 15:01:49 +0200
changeset 203215bfc30b14f
parent 202 a5ee729dc1e1
child 205 436fe75092b7
Cleaning of heap test and bug fix in heap concept check (ticket #100)

* The dijkstra heap test's digraph is inlined into the source file
* The random sequences are fixed
* The content of the header is moved to the source file
* Only the binary heap is checked
lemon/concepts/heap.h
test/CMakeLists.txt
test/Makefile.am
test/heap_test.cc
test/heap_test.h
     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 -}