1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/test/heap_test.cc Fri Mar 04 17:10:23 2005 +0000
1.3 @@ -0,0 +1,123 @@
1.4 +// -*- c++ -*-
1.5 +
1.6 +#include <iostream>
1.7 +#include <fstream>
1.8 +#include <vector>
1.9 +
1.10 +#include <lemon/concept_check.h>
1.11 +
1.12 +#include <lemon/bin_heap.h>
1.13 +#include <lemon/fib_heap.h>
1.14 +#include <lemon/radix_heap.h>
1.15 +
1.16 +#include <lemon/dimacs.h>
1.17 +
1.18 +#include "test_tools.h"
1.19 +#include "heap_test.h"
1.20 +#include "map_test.h"
1.21 +
1.22 +
1.23 +using namespace lemon;
1.24 +
1.25 +template <typename Item, typename Prio, typename ItemIntMap>
1.26 +class HeapConcept {
1.27 +public:
1.28 +
1.29 + template <typename _Heap>
1.30 + struct Constraints {
1.31 + public:
1.32 +
1.33 + void constraints() {
1.34 + Item item;
1.35 + Prio prio;
1.36 +
1.37 + typedef typename _Heap::state_enum state_enum;
1.38 + state_enum state;
1.39 +
1.40 + _Heap heap1 = _Heap(map);
1.41 +
1.42 + heap.push(item, prio);
1.43 +
1.44 + prio = heap.prio();
1.45 + item = heap.top();
1.46 +
1.47 + heap.pop();
1.48 +
1.49 + heap.set(item, prio);
1.50 + heap.decrease(item, prio);
1.51 + heap.increase(item, prio);
1.52 + prio = heap[item];
1.53 +
1.54 + heap.erase(item);
1.55 +
1.56 + state = heap.state(item);
1.57 +
1.58 + state = _Heap::PRE_HEAP;
1.59 + state = _Heap::IN_HEAP;
1.60 + state = _Heap::POST_HEAP;
1.61 + }
1.62 +
1.63 + _Heap& heap;
1.64 + ItemIntMap& map;
1.65 + };
1.66 +};
1.67 +
1.68 +int main() {
1.69 +
1.70 + typedef int Item;
1.71 + typedef int Prio;
1.72 + typedef IntIntMap ItemIntMap;
1.73 +
1.74 + typedef ListGraph Graph;
1.75 +
1.76 + typedef Graph::Edge Edge;
1.77 + typedef Graph::Node Node;
1.78 + typedef Graph::EdgeIt EdgeIt;
1.79 + typedef Graph::NodeIt NodeIt;
1.80 + typedef Graph::EdgeMap<int> LengthMap;
1.81 +
1.82 + Graph graph;
1.83 + LengthMap length(graph);
1.84 + Node start;
1.85 +
1.86 + std::ifstream input("preflow_graph.dim");
1.87 + readDimacs(input, graph, length, start);
1.88 +
1.89 + {
1.90 + std::cerr << "Checking Bin Heap" << std::endl;
1.91 +
1.92 + typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
1.93 + checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
1.94 + heapSortTest<IntHeap>(20);
1.95 +
1.96 + typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
1.97 + checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
1.98 + dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
1.99 + }
1.100 + {
1.101 + std::cerr << "Checking Fib Heap" << std::endl;
1.102 +
1.103 + typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
1.104 + checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
1.105 + heapSortTest<IntHeap>(20);
1.106 +
1.107 + typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
1.108 + checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
1.109 + dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
1.110 + }
1.111 + {
1.112 + std::cerr << "Checking Radix Heap" << std::endl;
1.113 +
1.114 + typedef RadixHeap<Item, ItemIntMap> IntHeap;
1.115 + checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
1.116 + heapSortTest<IntHeap>(20);
1.117 +
1.118 + typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
1.119 + checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
1.120 + dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
1.121 + }
1.122 +
1.123 + std::cout << __FILE__ ": All tests passed.\n";
1.124 +
1.125 + return 0;
1.126 +}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/test/heap_test.h Fri Mar 04 17:10:23 2005 +0000
2.3 @@ -0,0 +1,87 @@
2.4 +// -+- c++ -+-
2.5 +#include <vector>
2.6 +#include <algorithm>
2.7 +
2.8 +#include <lemon/bin_heap.h>
2.9 +#include <lemon/fib_heap.h>
2.10 +#include <lemon/radix_heap.h>
2.11 +
2.12 +#include <lemon/dijkstra.h>
2.13 +
2.14 +class IntIntMap : public std::vector<int> {
2.15 +public:
2.16 + typedef std::vector<int> Parent;
2.17 +
2.18 + IntIntMap() : Parent() {}
2.19 + IntIntMap(int n) : Parent(n) {}
2.20 + IntIntMap(int n, int v) : Parent(n, v) {}
2.21 +
2.22 + void set(int key, int value) {
2.23 + Parent::operator[](key) = value;
2.24 + }
2.25 +};
2.26 +
2.27 +
2.28 +template <typename _Heap>
2.29 +void heapSortTest(int n) {
2.30 + typedef _Heap Heap;
2.31 + IntIntMap map(n, -1);
2.32 +
2.33 + Heap heap(map);
2.34 +
2.35 + std::vector<int> v(n);
2.36 +
2.37 + for (int i = 0; i < n; ++i) {
2.38 + v[i] = rand() % 1000;
2.39 + heap.push(i, v[i]);
2.40 + }
2.41 + std::sort(v.begin(), v.end());
2.42 + for (int i = 0; i < n; ++i) {
2.43 + check(v[i] == heap.prio() ,"Wrong order in heap sort.");
2.44 + heap.pop();
2.45 + }
2.46 +}
2.47 +
2.48 +template <typename _Traits, typename _Heap>
2.49 +struct DefHeapTraits : public _Traits {
2.50 + typedef _Heap Heap;
2.51 +};
2.52 +
2.53 +template <typename _Graph, typename _LengthMap, typename _Heap>
2.54 +void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
2.55 + typename _Graph::Node& start) {
2.56 +
2.57 + typedef _Heap Heap;
2.58 + typedef _Graph Graph;
2.59 + typedef _LengthMap LengthMap;
2.60 +
2.61 + typedef typename Graph::Node Node;
2.62 + typedef typename Graph::Edge Edge;
2.63 + typedef typename Graph::NodeIt NodeIt;
2.64 + typedef typename Graph::EdgeIt EdgeIt;
2.65 +
2.66 + Dijkstra<Graph, LengthMap,
2.67 + DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> >
2.68 + dijkstra(graph, length);
2.69 +
2.70 + dijkstra.run(start);
2.71 +
2.72 + for(EdgeIt e(graph); e!=INVALID; ++e) {
2.73 + Node u=graph.source(e);
2.74 + Node v=graph.target(e);
2.75 + if (dijkstra.reached(u)) {
2.76 + check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
2.77 + "Error in a shortest path tree edge!");
2.78 + }
2.79 + }
2.80 +
2.81 + for(NodeIt v(graph); v!=INVALID; ++v) {
2.82 + if ( dijkstra.reached(v) ) {
2.83 + Edge e=dijkstra.pred(v);
2.84 + Node u=graph.source(e);
2.85 + check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
2.86 + "Error in a shortest path tree edge!");
2.87 + }
2.88 + }
2.89 +
2.90 +}