1.1 --- a/test/heap_test.h Thu Jul 10 16:13:50 2008 +0200
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,123 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2003-2008
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#include <vector>
1.23 -#include <algorithm>
1.24 -
1.25 -#include <lemon/dijkstra.h>
1.26 -
1.27 -class IntIntMap : public std::vector<int> {
1.28 -public:
1.29 - typedef std::vector<int> Parent;
1.30 -
1.31 - typedef int Key;
1.32 - typedef int Value;
1.33 -
1.34 - IntIntMap() : Parent() {}
1.35 - IntIntMap(int n) : Parent(n) {}
1.36 - IntIntMap(int n, int v) : Parent(n, v) {}
1.37 -
1.38 - void set(int key, int value) {
1.39 - Parent::operator[](key) = value;
1.40 - }
1.41 -};
1.42 -
1.43 -
1.44 -template <typename _Heap>
1.45 -void heapSortTest(int n) {
1.46 - typedef _Heap Heap;
1.47 - IntIntMap map(n, -1);
1.48 -
1.49 - Heap heap(map);
1.50 -
1.51 - std::vector<int> v(n);
1.52 -
1.53 - for (int i = 0; i < n; ++i) {
1.54 - v[i] = rnd[1000];
1.55 - heap.push(i, v[i]);
1.56 - }
1.57 - std::sort(v.begin(), v.end());
1.58 - for (int i = 0; i < n; ++i) {
1.59 - check(v[i] == heap.prio() ,"Wrong order in heap sort.");
1.60 - heap.pop();
1.61 - }
1.62 -}
1.63 -
1.64 -template <typename _Heap>
1.65 -void heapIncreaseTest(int n) {
1.66 - typedef _Heap Heap;
1.67 - IntIntMap map(n, -1);
1.68 -
1.69 - Heap heap(map);
1.70 -
1.71 - std::vector<int> v(n);
1.72 -
1.73 - for (int i = 0; i < n; ++i) {
1.74 - v[i] = rnd[1000];
1.75 - heap.push(i, v[i]);
1.76 - }
1.77 - for (int i = 0; i < n; ++i) {
1.78 - v[i] += rnd[1000];
1.79 - heap.increase(i, v[i]);
1.80 - }
1.81 - std::sort(v.begin(), v.end());
1.82 - for (int i = 0; i < n; ++i) {
1.83 - check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
1.84 - heap.pop();
1.85 - }
1.86 -}
1.87 -
1.88 -
1.89 -
1.90 -template <typename _Digraph, typename _LengthMap, typename _Heap>
1.91 -void dijkstraHeapTest(_Digraph& digraph, _LengthMap& length,
1.92 - typename _Digraph::Node& start) {
1.93 -
1.94 - typedef _Heap Heap;
1.95 - typedef _Digraph Digraph;
1.96 - typedef _LengthMap LengthMap;
1.97 -
1.98 - typedef typename Digraph::Node Node;
1.99 - typedef typename Digraph::Arc Arc;
1.100 - typedef typename Digraph::NodeIt NodeIt;
1.101 - typedef typename Digraph::ArcIt ArcIt;
1.102 -
1.103 - typename Dijkstra<Digraph, LengthMap>::template DefStandardHeap<Heap>::
1.104 - Create dijkstra(digraph, length);
1.105 -
1.106 - dijkstra.run(start);
1.107 -
1.108 - for(ArcIt e(digraph); e!=INVALID; ++e) {
1.109 - Node u=digraph.source(e);
1.110 - Node v=digraph.target(e);
1.111 - if (dijkstra.reached(u)) {
1.112 - check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
1.113 - "Error in a shortest path tree arc!");
1.114 - }
1.115 - }
1.116 -
1.117 - for(NodeIt v(digraph); v!=INVALID; ++v) {
1.118 - if ( dijkstra.reached(v) && dijkstra.predArc(v) != INVALID ) {
1.119 - Arc e=dijkstra.predArc(v);
1.120 - Node u=digraph.source(e);
1.121 - check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
1.122 - "Error in a shortest path tree arc!");
1.123 - }
1.124 - }
1.125 -
1.126 -}