Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/heap_test.h
author hegyi
Thu, 05 Jan 2006 12:30:09 +0000
changeset 1878 409a31271efd
parent 1745 d356e54bdafc
child 1956 a055123339d5
permissions -rw-r--r--
Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox. 
     1 // -*- c++ -*-

     2 

     3 #include <vector>

     4 #include <algorithm>

     5 

     6 #include <lemon/dijkstra.h>

     7 

     8 class IntIntMap : public std::vector<int> {

     9 public:

    10   typedef std::vector<int> Parent;

    11 

    12   IntIntMap() : Parent() {}

    13   IntIntMap(int n) : Parent(n) {}

    14   IntIntMap(int n, int v) : Parent(n, v) {}

    15 

    16   void set(int key, int value) {

    17     Parent::operator[](key) = value;

    18   }

    19 };

    20 

    21 

    22 template <typename _Heap>

    23 void heapSortTest(int n) {

    24   typedef _Heap Heap;

    25   IntIntMap map(n, -1);

    26 

    27   Heap heap(map);

    28   

    29   std::vector<int> v(n);

    30 

    31   for (int i = 0; i < n; ++i) {

    32     v[i] = rand() % 1000;

    33     heap.push(i, v[i]);

    34   }

    35   std::sort(v.begin(), v.end());

    36   for (int i = 0; i < n; ++i) {

    37     check(v[i] == heap.prio() ,"Wrong order in heap sort.");

    38     heap.pop();

    39   }

    40 }

    41 

    42 template <typename _Heap>

    43 void heapIncreaseTest(int n) {

    44   typedef _Heap Heap;

    45   IntIntMap map(n, -1);

    46 

    47   Heap heap(map);

    48   

    49   std::vector<int> v(n);

    50 

    51   for (int i = 0; i < n; ++i) {

    52     v[i] = rand() % 1000;

    53     heap.push(i, v[i]);

    54   }

    55   for (int i = 0; i < n; ++i) {

    56     v[i] += rand() % 1000;

    57     heap.increase(i, v[i]);

    58   }

    59   std::sort(v.begin(), v.end());

    60   for (int i = 0; i < n; ++i) {

    61     check(v[i] == heap.prio() ,"Wrong order in heap increase test.");

    62     heap.pop();

    63   }

    64 }

    65 

    66 

    67 

    68 template <typename _Graph, typename _LengthMap, typename _Heap>

    69 void dijkstraHeapTest(_Graph& graph, _LengthMap& length,

    70 		      typename _Graph::Node& start) {

    71 

    72   typedef _Heap Heap;

    73   typedef _Graph Graph;

    74   typedef _LengthMap LengthMap;

    75 

    76   typedef typename Graph::Node Node;

    77   typedef typename Graph::Edge Edge;

    78   typedef typename Graph::NodeIt NodeIt;

    79   typedef typename Graph::EdgeIt EdgeIt;

    80 

    81   typename Dijkstra<Graph, LengthMap>::template DefStandardHeap<Heap>::

    82     Create dijkstra(graph, length);

    83 

    84   dijkstra.run(start);

    85 

    86   for(EdgeIt e(graph); e!=INVALID; ++e) {

    87     Node u=graph.source(e); 

    88     Node v=graph.target(e);

    89     if (dijkstra.reached(u)) {

    90       check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],

    91       	     "Error in a shortest path tree edge!");

    92     }

    93   }

    94 

    95   for(NodeIt v(graph); v!=INVALID; ++v) {

    96     if ( dijkstra.reached(v) && dijkstra.predEdge(v) != INVALID ) {

    97       Edge e=dijkstra.predEdge(v);

    98       Node u=graph.source(e);

    99       check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],

   100 	     "Error in a shortest path tree edge!");

   101     }

   102   }

   103 

   104 }
lemon-0.x