COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/heap_test.cc @ 1187:04e5825000c5

Last change on this file since 1187:04e5825000c5 was 1187:04e5825000c5, checked in by Balazs Dezso, 16 years ago

concept and checking functions for heaps

File size: 2.8 KB
Line 
1// -*- c++ -*-
2
3#include <iostream>
4#include <fstream>
5#include <vector>
6
7#include <lemon/concept_check.h>
8
9#include <lemon/bin_heap.h>
10#include <lemon/fib_heap.h>
11#include <lemon/radix_heap.h>
12
13#include <lemon/dimacs.h>
14
15#include "test_tools.h"
16#include "heap_test.h"
17#include "map_test.h"
18
19
20using namespace lemon;
21
22template <typename Item, typename Prio, typename ItemIntMap>
23class HeapConcept {
24public: 
25
26  template <typename _Heap>
27  struct Constraints {
28  public:
29   
30    void constraints() {
31      Item item;
32      Prio prio;
33
34      typedef typename _Heap::state_enum state_enum;
35      state_enum state;
36     
37      _Heap heap1 = _Heap(map);
38     
39      heap.push(item, prio);
40
41      prio = heap.prio();
42      item = heap.top();
43
44      heap.pop();
45
46      heap.set(item, prio);
47      heap.decrease(item, prio);
48      heap.increase(item, prio);
49      prio = heap[item];
50
51      heap.erase(item);
52
53      state = heap.state(item);
54
55      state = _Heap::PRE_HEAP;
56      state = _Heap::IN_HEAP;
57      state = _Heap::POST_HEAP;
58    }
59   
60    _Heap& heap;
61    ItemIntMap& map;
62  };
63};
64
65int main() {
66
67  typedef int Item;
68  typedef int Prio;
69  typedef IntIntMap ItemIntMap;
70
71  typedef ListGraph Graph;
72
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;
78
79  Graph graph;
80  LengthMap length(graph);
81  Node start;
82
83  std::ifstream input("preflow_graph.dim");
84  readDimacs(input, graph, length, start); 
85 
86  {
87    std::cerr << "Checking Bin Heap" << std::endl;
88
89    typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
90    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
91    heapSortTest<IntHeap>(20);
92   
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;
99
100    typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
101    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
102    heapSortTest<IntHeap>(20);
103
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;
110
111    typedef RadixHeap<Item, ItemIntMap> IntHeap;
112    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
113    heapSortTest<IntHeap>(20);
114
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  }
119
120  std::cout << __FILE__ ": All tests passed.\n";
121
122  return 0;
123}
Note: See TracBrowser for help on using the repository browser.