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 athos
Thu, 07 Jul 2005 09:04:39 +0000
changeset 1541 305ce06287c9
parent 1206 9c398137c2cb
child 1728 eb8bb91ba9e2
permissions -rw-r--r--
Decided not to \include the sample.lgf in the quicktour: so it can be bigger. 
     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 _Traits, typename _Heap>

    69 struct DefHeapTraits : public _Traits {

    70   typedef _Heap Heap;

    71 };

    72 

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

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

    75 		      typename _Graph::Node& start) {

    76 

    77   typedef _Heap Heap;

    78   typedef _Graph Graph;

    79   typedef _LengthMap LengthMap;

    80 

    81   typedef typename Graph::Node Node;

    82   typedef typename Graph::Edge Edge;

    83   typedef typename Graph::NodeIt NodeIt;

    84   typedef typename Graph::EdgeIt EdgeIt;

    85 

    86   Dijkstra<Graph, LengthMap, 

    87     DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> > 

    88     dijkstra(graph, length);

    89 

    90   dijkstra.run(start);

    91 

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

    93     Node u=graph.source(e); 

    94     Node v=graph.target(e);

    95     if (dijkstra.reached(u)) {

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

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

    98     }

    99   }

   100 

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

   102     if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) {

   103       Edge e=dijkstra.pred(v);

   104       Node u=graph.source(e);

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

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

   107     }

   108   }

   109 

   110 }
lemon-0.x