lemon-0.x: src/test/heap_test.cc@7bce0ef61d6b

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

     3 #include <iostream>

     4 #include <fstream>

     5 #include <vector>

     7 #include <lemon/concept_check.h>

     9 #include <lemon/bin_heap.h>

    10 #include <lemon/fib_heap.h>

    11 #include <lemon/radix_heap.h>

    13 #include <lemon/dimacs.h>

    15 #include "test_tools.h"

    16 #include "heap_test.h"

    17 #include "map_test.h"

    20 using namespace lemon;

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

    23 class HeapConcept {

    24 public:

    26   template <typename _Heap>

    27   struct Constraints {

    28   public:

    30     void constraints() {

    31       Item item;

    32       Prio prio;

    34       typedef typename _Heap::state_enum state_enum;

    35       state_enum state;

    37       _Heap heap1 = _Heap(map);

    39       heap.push(item, prio);

    41       prio = heap.prio();

    42       item = heap.top();

    44       heap.pop();

    46       heap.set(item, prio);

    47       heap.decrease(item, prio);

    48       heap.increase(item, prio);

    49       prio = heap[item];

    51       heap.erase(item);

    53       state = heap.state(item);

    55       state = _Heap::PRE_HEAP;

    56       state = _Heap::IN_HEAP;

    57       state = _Heap::POST_HEAP;

    58     }

    60     _Heap& heap;

    61     ItemIntMap& map;

    62   };

    63 };

    65 int main() {

    67   typedef int Item;

    68   typedef int Prio;

    69   typedef IntIntMap ItemIntMap;

    71   typedef ListGraph Graph;

    73   typedef Graph::Edge Edge;

    74   typedef Graph::Node Node;

    75   typedef Graph::EdgeIt EdgeIt;

    76   typedef Graph::NodeIt NodeIt;

    77   typedef Graph::EdgeMap<int> LengthMap;

    79   Graph graph;

    80   LengthMap length(graph);

    81   Node start;

    83   std::ifstream input("preflow_graph.dim");

    84   readDimacs(input, graph, length, start);

    86   {

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

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

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

    91     heapSortTest<IntHeap>(20);

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

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

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

    96   }

    97   {

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

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

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

   102     heapSortTest<IntHeap>(20);

   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 Radix Heap" << std::endl;

   111     typedef RadixHeap<Item, ItemIntMap> IntHeap;

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

   113     heapSortTest<IntHeap>(20);

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

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

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

   118   }

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

   122   return 0;

   123 }

author	deba
	Fri, 04 Mar 2005 17:20:11 +0000
changeset 1194	7bce0ef61d6b
child 1206	9c398137c2cb
permissions	-rw-r--r--