|
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 |
|
20 using namespace lemon; |
|
21 |
|
22 template <typename Item, typename Prio, typename ItemIntMap> |
|
23 class HeapConcept { |
|
24 public: |
|
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 |
|
65 int 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 } |