lemon-0.x: src/test/heap_test.cc@9c398137c2cb

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

     3 #include <iostream>

     4 #include <fstream>

     5 #include <vector>

     7 #include <lemon/concept_check.h>

     9 #include <lemon/smart_graph.h>

    11 #include <lemon/graph_reader.h>

    13 #include <lemon/bin_heap.h>

    14 #include <lemon/fib_heap.h>

    15 #include <lemon/radix_heap.h>

    17 #include "test_tools.h"

    19 #include "heap_test.h"

    22 using namespace lemon;

    24 template <typename Item, typename Prio, typename ItemIntMap>

    25 class HeapConcept {

    26 public:

    28   template <typename _Heap>

    29   struct Constraints {

    30   public:

    32     void constraints() {

    33       Item item;

    34       Prio prio;

    36       ignore_unused_variable_warning(item);

    37       ignore_unused_variable_warning(prio);

    39       typedef typename _Heap::state_enum state_enum;

    40       state_enum state;

    42       ignore_unused_variable_warning(state);

    44       _Heap heap1 = _Heap(map);

    46       ignore_unused_variable_warning(heap1);

    48       heap.push(item, prio);

    50       prio = heap.prio();

    51       item = heap.top();

    53       heap.pop();

    55       heap.set(item, prio);

    56       heap.decrease(item, prio);

    57       heap.increase(item, prio);

    58       prio = heap[item];

    60       heap.erase(item);

    62       state = heap.state(item);

    64       state = _Heap::PRE_HEAP;

    65       state = _Heap::IN_HEAP;

    66       state = _Heap::POST_HEAP;

    67     }

    69     _Heap& heap;

    70     ItemIntMap& map;

    71   };

    72 };

    74 int main() {

    76   typedef int Item;

    77   typedef int Prio;

    78   typedef IntIntMap ItemIntMap;

    80   typedef ListGraph Graph;

    82   typedef Graph::Edge Edge;

    83   typedef Graph::Node Node;

    84   typedef Graph::EdgeIt EdgeIt;

    85   typedef Graph::NodeIt NodeIt;

    86   typedef Graph::EdgeMap<int> LengthMap;

    88   Graph graph;

    89   LengthMap length(graph);

    90   Node start;

    92   /// \todo create own test graph

    93   std::ifstream input("dijkstra_test.lemon");

    94   readGraph(input, graph, length, start);

    96   {

    97     std::cerr << "Checking Bin Heap" << std::endl;

    99     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;

   100     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();

   101     heapSortTest<IntHeap>(100);

   102     heapIncreaseTest<IntHeap>(100);

   104     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;

   105     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

   106     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

   107   }

   108   {

   109     std::cerr << "Checking Fib Heap" << std::endl;

   111     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;

   112     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();

   113     heapSortTest<IntHeap>(100);

   114     heapIncreaseTest<IntHeap>(100);

   116     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;

   117     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

   118     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

   119   }

   120   {

   121     std::cerr << "Checking Radix Heap" << std::endl;

   123     typedef RadixHeap<Item, ItemIntMap> IntHeap;

   124     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();

   125     heapSortTest<IntHeap>(100);

   126     heapIncreaseTest<IntHeap>(100);

   128     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;

   129     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

   130     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

   131   }

   133   std::cout << __FILE__ ": All tests passed.\n";

   135   return 0;

   136 }

author	deba
	Wed, 09 Mar 2005 14:10:21 +0000
changeset 1206	9c398137c2cb
parent 1187	04e5825000c5
child 1215	81b4731f8a6b
permissions	-rw-r--r--