lemon-0.x: src/test/heap_test.h@477a0fe37552

     1 // -+- c++ -+-

     2 #include <vector>

     3 #include <algorithm>

     5 #include <lemon/bin_heap.h>

     6 #include <lemon/fib_heap.h>

     7 #include <lemon/radix_heap.h>

     9 #include <lemon/dijkstra.h>

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

    12 public:

    13   typedef std::vector<int> Parent;

    15   IntIntMap() : Parent() {}

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

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

    19   void set(int key, int value) {

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

    21   }

    22 };

    25 template <typename _Heap>

    26 void heapSortTest(int n) {

    27   typedef _Heap Heap;

    28   IntIntMap map(n, -1);

    30   Heap heap(map);

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

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

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

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

    37   }

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

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

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

    41     heap.pop();

    42   }

    43 }

    45 template <typename _Traits, typename _Heap>

    46 struct DefHeapTraits : public _Traits {

    47   typedef _Heap Heap;

    48 };

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

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

    52 		      typename _Graph::Node& start) {

    54   typedef _Heap Heap;

    55   typedef _Graph Graph;

    56   typedef _LengthMap LengthMap;

    58   typedef typename Graph::Node Node;

    59   typedef typename Graph::Edge Edge;

    60   typedef typename Graph::NodeIt NodeIt;

    61   typedef typename Graph::EdgeIt EdgeIt;

    63   Dijkstra<Graph, LengthMap,

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

    65     dijkstra(graph, length);

    67   dijkstra.run(start);

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

    70     Node u=graph.source(e);

    71     Node v=graph.target(e);

    72     if (dijkstra.reached(u)) {

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

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

    75     }

    76   }

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

    79     if ( dijkstra.reached(v) ) {

    80       Edge e=dijkstra.pred(v);

    81       Node u=graph.source(e);

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

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

    84     }

    85   }

    87 }

author	deba
	Fri, 04 Mar 2005 17:13:40 +0000
changeset 1190	477a0fe37552
child 1206	9c398137c2cb
permissions	-rw-r--r--