# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 1215781309 -7200
# Node ID 215bfc30b14fb8defcf1c0e00acde84abc1b3a28
# Parent a5ee729dc1e10eb45f0925d2956766671f1c3d63
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
diff -r a5ee729dc1e1 -r 215bfc30b14f lemon/concepts/heap.h
--- a/lemon/concepts/heap.h Thu Jul 10 16:13:50 2008 +0200
+++ b/lemon/concepts/heap.h Fri Jul 11 15:01:49 2008 +0200
@@ -181,12 +181,10 @@
Item item;
Prio prio;
- State state;
item=Item();
prio=Prio();
ignore_unused_variable_warning(item);
ignore_unused_variable_warning(prio);
- ignore_unused_variable_warning(state);
OwnItem own_item;
OwnPrio own_prio;
@@ -203,7 +201,9 @@
ignore_unused_variable_warning(heap2);
int s = heap.size();
+ ignore_unused_variable_warning(s);
bool e = heap.empty();
+ ignore_unused_variable_warning(e);
prio = heap.prio();
item = heap.top();
@@ -227,14 +227,9 @@
heap.erase(own_item);
heap.clear();
- state = heap.state(item);
- heap.state(item, state);
- state = heap.state(own_item);
+ own_state = heap.state(own_item);
heap.state(own_item, own_state);
- state = _Heap::PRE_HEAP;
- state = _Heap::IN_HEAP;
- state = _Heap::POST_HEAP;
own_state = _Heap::PRE_HEAP;
own_state = _Heap::IN_HEAP;
own_state = _Heap::POST_HEAP;
diff -r a5ee729dc1e1 -r 215bfc30b14f test/CMakeLists.txt
--- a/test/CMakeLists.txt Thu Jul 10 16:13:50 2008 +0200
+++ b/test/CMakeLists.txt Fri Jul 11 15:01:49 2008 +0200
@@ -13,6 +13,7 @@
graph_copy_test
graph_test
graph_utils_test
+ heap_test
kruskal_test
maps_test
path_test
diff -r a5ee729dc1e1 -r 215bfc30b14f test/Makefile.am
--- a/test/Makefile.am Thu Jul 10 16:13:50 2008 +0200
+++ b/test/Makefile.am Fri Jul 11 15:01:49 2008 +0200
@@ -3,7 +3,6 @@
noinst_HEADERS += \
test/graph_test.h \
- test/heap_test.h \
test/graph_maps_test.h \
test/test_tools.h
@@ -18,6 +17,7 @@
test/graph_copy_test \
test/graph_test \
test/graph_utils_test \
+ test/heap_test \
test/kruskal_test \
test/maps_test \
test/random_test \
@@ -40,7 +40,7 @@
test_graph_copy_test_SOURCES = test/graph_copy_test.cc
test_graph_test_SOURCES = test/graph_test.cc
test_graph_utils_test_SOURCES = test/graph_utils_test.cc
-# test_heap_test_SOURCES = test/heap_test.cc
+test_heap_test_SOURCES = test/heap_test.cc
test_kruskal_test_SOURCES = test/kruskal_test.cc
test_maps_test_SOURCES = test/maps_test.cc
test_path_test_SOURCES = test/path_test.cc
diff -r a5ee729dc1e1 -r 215bfc30b14f test/heap_test.cc
--- a/test/heap_test.cc Thu Jul 10 16:13:50 2008 +0200
+++ b/test/heap_test.cc Fri Jul 11 15:01:49 2008 +0200
@@ -24,113 +24,163 @@
#include <lemon/concept_check.h>
#include <lemon/concepts/heap.h>
-#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
-#include <lemon/digraph_reader.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/dijkstra.h>
+#include <lemon/maps.h>
#include <lemon/bin_heap.h>
-#include <lemon/fib_heap.h>
-#include <lemon/radix_heap.h>
-#include <lemon/bucket_heap.h>
#include "test_tools.h"
-#include "heap_test.h"
-
-#include <lemon/time_measure.h>
-
using namespace lemon;
using namespace lemon::concepts;
+typedef ListDigraph Digraph;
+DIGRAPH_TYPEDEFS(Digraph);
+
+char test_lgf[] =
+ "@nodes\n"
+ "label\n"
+ "0\n"
+ "1\n"
+ "2\n"
+ "3\n"
+ "4\n"
+ "5\n"
+ "6\n"
+ "7\n"
+ "8\n"
+ "9\n"
+ "@arcs\n"
+ " label capacity\n"
+ "0 5 0 94\n"
+ "3 9 1 11\n"
+ "8 7 2 83\n"
+ "1 2 3 94\n"
+ "5 7 4 35\n"
+ "7 4 5 84\n"
+ "9 5 6 38\n"
+ "0 4 7 96\n"
+ "6 7 8 6\n"
+ "3 1 9 27\n"
+ "5 2 10 77\n"
+ "5 6 11 69\n"
+ "6 5 12 41\n"
+ "4 6 13 70\n"
+ "3 2 14 45\n"
+ "7 9 15 93\n"
+ "5 9 16 50\n"
+ "9 0 17 94\n"
+ "9 6 18 67\n"
+ "0 9 19 86\n"
+ "@attributes\n"
+ "source 3\n";
+
+int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34};
+int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37};
+
+int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
+
+template <typename Heap>
+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];
+ heap.push(i, v[i]);
+ }
+ std::sort(v.begin(), v.end());
+ for (int i = 0; i < test_len; ++i) {
+ check(v[i] == heap.prio() ,"Wrong order in heap sort.");
+ heap.pop();
+ }
+}
+
+template <typename Heap>
+void heapIncreaseTest() {
+ 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];
+ heap.push(i, v[i]);
+ }
+ for (int i = 0; i < test_len; ++i) {
+ v[i] += test_inc[i];
+ heap.increase(i, v[i]);
+ }
+ 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.");
+ heap.pop();
+ }
+}
+
+
+
+template <typename Heap>
+void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
+ Node source) {
+
+ typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
+ Create dijkstra(digraph, length);
+
+ dijkstra.run(source);
+
+ for(ArcIt a(digraph); a != INVALID; ++a) {
+ Node s = digraph.source(a);
+ Node t = digraph.target(a);
+ if (dijkstra.reached(s)) {
+ check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
+ "Error in a shortest path tree!");
+ }
+ }
+
+ for(NodeIt n(digraph); n != INVALID; ++n) {
+ if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
+ Arc a = dijkstra.predArc(n);
+ Node s = digraph.source(a);
+ check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
+ "Error in a shortest path tree!");
+ }
+ }
+
+}
+
int main() {
typedef int Item;
typedef int Prio;
- typedef IntIntMap ItemIntMap;
+ typedef RangeMap<int> ItemIntMap;
+
+ Digraph digraph;
+ IntArcMap length(digraph);
+ Node source;
- typedef ListDigraph Digraph;
-
- typedef Digraph::Arc Arc;
- typedef Digraph::Node Node;
- typedef Digraph::ArcIt ArcIt;
- typedef Digraph::NodeIt NodeIt;
- typedef Digraph::ArcMap<int> LengthMap;
-
- Digraph digraph;
- LengthMap length(digraph);
- Node start;
-
- /// \todo create own test digraph
-
- std::string f_name;
- if( getenv("srcdir") )
- f_name = std::string(getenv("srcdir"));
- else f_name = ".";
- f_name += "/test/dijkstra_test.lgf";
-
- std::ifstream input(f_name.c_str());
- check(input, "Input file '" << f_name << "' not found.");
- DigraphReader<Digraph>(input, digraph).
- readArcMap("capacity", length).
- readNode("source", start).
+ std::istringstream input(test_lgf);
+ digraphReader(input, digraph).
+ arcMap("capacity", length).
+ node("source", source).
run();
{
- std::cout << "Checking Bin Heap" << std::endl;
-
typedef BinHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
- heapSortTest<IntHeap>(100);
- heapIncreaseTest<IntHeap>(100);
+ heapSortTest<IntHeap>();
+ heapIncreaseTest<IntHeap>();
- typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
- checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
- Timer timer;
- dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
- std::cout << timer << std::endl;
- }
- {
- std::cout << "Checking Fib Heap" << std::endl;
-
- typedef FibHeap<Prio, ItemIntMap> IntHeap;
- checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
- heapSortTest<IntHeap>(100);
- heapIncreaseTest<IntHeap>(100);
-
- typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
- checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
- Timer timer;
- dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
- std::cout << timer << std::endl;
- }
- {
- std::cout << "Checking Radix Heap" << std::endl;
-
- typedef RadixHeap<ItemIntMap> IntHeap;
- checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
- heapSortTest<IntHeap>(100);
- heapIncreaseTest<IntHeap>(100);
-
- typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
- checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
- Timer timer;
- dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
- std::cout << timer << std::endl;
- }
-
- {
- std::cout << "Checking Bucket Heap" << std::endl;
-
- typedef BucketHeap<ItemIntMap> IntHeap;
- checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
- heapSortTest<IntHeap>(100);
- heapIncreaseTest<IntHeap>(100);
-
- typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
- checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
- Timer timer;
- dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
- std::cout << timer << std::endl;
+ typedef BinHeap<Prio, IntNodeMap > NodeHeap;
+ checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+ dijkstraHeapTest<NodeHeap>(digraph, length, source);
}
return 0;
diff -r a5ee729dc1e1 -r 215bfc30b14f test/heap_test.h
--- a/test/heap_test.h Thu Jul 10 16:13:50 2008 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,123 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2008
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#include <vector>
-#include <algorithm>
-
-#include <lemon/dijkstra.h>
-
-class IntIntMap : public std::vector<int> {
-public:
- typedef std::vector<int> Parent;
-
- typedef int Key;
- typedef int Value;
-
- IntIntMap() : Parent() {}
- IntIntMap(int n) : Parent(n) {}
- IntIntMap(int n, int v) : Parent(n, v) {}
-
- void set(int key, int value) {
- Parent::operator[](key) = value;
- }
-};
-
-
-template <typename _Heap>
-void heapSortTest(int n) {
- typedef _Heap Heap;
- IntIntMap map(n, -1);
-
- Heap heap(map);
-
- std::vector<int> v(n);
-
- for (int i = 0; i < n; ++i) {
- v[i] = rnd[1000];
- heap.push(i, v[i]);
- }
- std::sort(v.begin(), v.end());
- for (int i = 0; i < n; ++i) {
- check(v[i] == heap.prio() ,"Wrong order in heap sort.");
- heap.pop();
- }
-}
-
-template <typename _Heap>
-void heapIncreaseTest(int n) {
- typedef _Heap Heap;
- IntIntMap map(n, -1);
-
- Heap heap(map);
-
- std::vector<int> v(n);
-
- for (int i = 0; i < n; ++i) {
- v[i] = rnd[1000];
- heap.push(i, v[i]);
- }
- for (int i = 0; i < n; ++i) {
- v[i] += rnd[1000];
- heap.increase(i, v[i]);
- }
- std::sort(v.begin(), v.end());
- for (int i = 0; i < n; ++i) {
- check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
- heap.pop();
- }
-}
-
-
-
-template <typename _Digraph, typename _LengthMap, typename _Heap>
-void dijkstraHeapTest(_Digraph& digraph, _LengthMap& length,
- typename _Digraph::Node& start) {
-
- typedef _Heap Heap;
- typedef _Digraph Digraph;
- typedef _LengthMap LengthMap;
-
- typedef typename Digraph::Node Node;
- typedef typename Digraph::Arc Arc;
- typedef typename Digraph::NodeIt NodeIt;
- typedef typename Digraph::ArcIt ArcIt;
-
- typename Dijkstra<Digraph, LengthMap>::template DefStandardHeap<Heap>::
- Create dijkstra(digraph, length);
-
- dijkstra.run(start);
-
- for(ArcIt e(digraph); e!=INVALID; ++e) {
- Node u=digraph.source(e);
- Node v=digraph.target(e);
- if (dijkstra.reached(u)) {
- check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
- "Error in a shortest path tree arc!");
- }
- }
-
- for(NodeIt v(digraph); v!=INVALID; ++v) {
- if ( dijkstra.reached(v) && dijkstra.predArc(v) != INVALID ) {
- Arc e=dijkstra.predArc(v);
- Node u=digraph.source(e);
- check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
- "Error in a shortest path tree arc!");
- }
- }
-
-}