23 |
23 |
24 #include <lemon/concept_check.h> |
24 #include <lemon/concept_check.h> |
25 #include <lemon/concepts/heap.h> |
25 #include <lemon/concepts/heap.h> |
26 |
26 |
27 #include <lemon/smart_graph.h> |
27 #include <lemon/smart_graph.h> |
28 |
|
29 #include <lemon/lgf_reader.h> |
28 #include <lemon/lgf_reader.h> |
30 #include <lemon/dijkstra.h> |
29 #include <lemon/dijkstra.h> |
31 #include <lemon/maps.h> |
30 #include <lemon/maps.h> |
32 |
31 |
33 #include <lemon/bin_heap.h> |
32 #include <lemon/bin_heap.h> |
|
33 #include <lemon/fourary_heap.h> |
|
34 #include <lemon/kary_heap.h> |
34 #include <lemon/fib_heap.h> |
35 #include <lemon/fib_heap.h> |
|
36 #include <lemon/pairing_heap.h> |
35 #include <lemon/radix_heap.h> |
37 #include <lemon/radix_heap.h> |
|
38 #include <lemon/binom_heap.h> |
36 #include <lemon/bucket_heap.h> |
39 #include <lemon/bucket_heap.h> |
37 |
40 |
38 #include "test_tools.h" |
41 #include "test_tools.h" |
39 |
42 |
40 using namespace lemon; |
43 using namespace lemon; |
87 int test_len = sizeof(test_seq) / sizeof(test_seq[0]); |
90 int test_len = sizeof(test_seq) / sizeof(test_seq[0]); |
88 |
91 |
89 template <typename Heap> |
92 template <typename Heap> |
90 void heapSortTest() { |
93 void heapSortTest() { |
91 RangeMap<int> map(test_len, -1); |
94 RangeMap<int> map(test_len, -1); |
92 |
|
93 Heap heap(map); |
95 Heap heap(map); |
94 |
96 |
95 std::vector<int> v(test_len); |
97 std::vector<int> v(test_len); |
96 |
|
97 for (int i = 0; i < test_len; ++i) { |
98 for (int i = 0; i < test_len; ++i) { |
98 v[i] = test_seq[i]; |
99 v[i] = test_seq[i]; |
99 heap.push(i, v[i]); |
100 heap.push(i, v[i]); |
100 } |
101 } |
101 std::sort(v.begin(), v.end()); |
102 std::sort(v.begin(), v.end()); |
102 for (int i = 0; i < test_len; ++i) { |
103 for (int i = 0; i < test_len; ++i) { |
103 check(v[i] == heap.prio() ,"Wrong order in heap sort."); |
104 check(v[i] == heap.prio(), "Wrong order in heap sort."); |
104 heap.pop(); |
105 heap.pop(); |
105 } |
106 } |
106 } |
107 } |
107 |
108 |
108 template <typename Heap> |
109 template <typename Heap> |
110 RangeMap<int> map(test_len, -1); |
111 RangeMap<int> map(test_len, -1); |
111 |
112 |
112 Heap heap(map); |
113 Heap heap(map); |
113 |
114 |
114 std::vector<int> v(test_len); |
115 std::vector<int> v(test_len); |
115 |
|
116 for (int i = 0; i < test_len; ++i) { |
116 for (int i = 0; i < test_len; ++i) { |
117 v[i] = test_seq[i]; |
117 v[i] = test_seq[i]; |
118 heap.push(i, v[i]); |
118 heap.push(i, v[i]); |
119 } |
119 } |
120 for (int i = 0; i < test_len; ++i) { |
120 for (int i = 0; i < test_len; ++i) { |
121 v[i] += test_inc[i]; |
121 v[i] += test_inc[i]; |
122 heap.increase(i, v[i]); |
122 heap.increase(i, v[i]); |
123 } |
123 } |
124 std::sort(v.begin(), v.end()); |
124 std::sort(v.begin(), v.end()); |
125 for (int i = 0; i < test_len; ++i) { |
125 for (int i = 0; i < test_len; ++i) { |
126 check(v[i] == heap.prio() ,"Wrong order in heap increase test."); |
126 check(v[i] == heap.prio(), "Wrong order in heap increase test."); |
127 heap.pop(); |
127 heap.pop(); |
128 } |
128 } |
129 } |
129 } |
130 |
|
131 |
|
132 |
130 |
133 template <typename Heap> |
131 template <typename Heap> |
134 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, |
132 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, |
135 Node source) { |
133 Node source) { |
136 |
134 |
142 for(ArcIt a(digraph); a != INVALID; ++a) { |
140 for(ArcIt a(digraph); a != INVALID; ++a) { |
143 Node s = digraph.source(a); |
141 Node s = digraph.source(a); |
144 Node t = digraph.target(a); |
142 Node t = digraph.target(a); |
145 if (dijkstra.reached(s)) { |
143 if (dijkstra.reached(s)) { |
146 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], |
144 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], |
147 "Error in a shortest path tree!"); |
145 "Error in shortest path tree."); |
148 } |
146 } |
149 } |
147 } |
150 |
148 |
151 for(NodeIt n(digraph); n != INVALID; ++n) { |
149 for(NodeIt n(digraph); n != INVALID; ++n) { |
152 if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) { |
150 if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) { |
153 Arc a = dijkstra.predArc(n); |
151 Arc a = dijkstra.predArc(n); |
154 Node s = digraph.source(a); |
152 Node s = digraph.source(a); |
155 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], |
153 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], |
156 "Error in a shortest path tree!"); |
154 "Error in shortest path tree."); |
157 } |
155 } |
158 } |
156 } |
159 |
157 |
160 } |
158 } |
161 |
159 |
173 digraphReader(digraph, input). |
171 digraphReader(digraph, input). |
174 arcMap("capacity", length). |
172 arcMap("capacity", length). |
175 node("source", source). |
173 node("source", source). |
176 run(); |
174 run(); |
177 |
175 |
|
176 // BinHeap |
178 { |
177 { |
179 typedef BinHeap<Prio, ItemIntMap> IntHeap; |
178 typedef BinHeap<Prio, ItemIntMap> IntHeap; |
180 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
179 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
181 heapSortTest<IntHeap>(); |
180 heapSortTest<IntHeap>(); |
182 heapIncreaseTest<IntHeap>(); |
181 heapIncreaseTest<IntHeap>(); |
184 typedef BinHeap<Prio, IntNodeMap > NodeHeap; |
183 typedef BinHeap<Prio, IntNodeMap > NodeHeap; |
185 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
184 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
186 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
185 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
187 } |
186 } |
188 |
187 |
|
188 // FouraryHeap |
|
189 { |
|
190 typedef FouraryHeap<Prio, ItemIntMap> IntHeap; |
|
191 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
|
192 heapSortTest<IntHeap>(); |
|
193 heapIncreaseTest<IntHeap>(); |
|
194 |
|
195 typedef FouraryHeap<Prio, IntNodeMap > NodeHeap; |
|
196 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
|
197 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
|
198 } |
|
199 |
|
200 // KaryHeap |
|
201 { |
|
202 typedef KaryHeap<Prio, ItemIntMap> IntHeap; |
|
203 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
|
204 heapSortTest<IntHeap>(); |
|
205 heapIncreaseTest<IntHeap>(); |
|
206 |
|
207 typedef KaryHeap<Prio, IntNodeMap > NodeHeap; |
|
208 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
|
209 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
|
210 } |
|
211 |
|
212 // FibHeap |
189 { |
213 { |
190 typedef FibHeap<Prio, ItemIntMap> IntHeap; |
214 typedef FibHeap<Prio, ItemIntMap> IntHeap; |
191 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
215 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
192 heapSortTest<IntHeap>(); |
216 heapSortTest<IntHeap>(); |
193 heapIncreaseTest<IntHeap>(); |
217 heapIncreaseTest<IntHeap>(); |
195 typedef FibHeap<Prio, IntNodeMap > NodeHeap; |
219 typedef FibHeap<Prio, IntNodeMap > NodeHeap; |
196 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
220 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
197 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
221 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
198 } |
222 } |
199 |
223 |
|
224 // PairingHeap |
|
225 // { |
|
226 // typedef PairingHeap<Prio, ItemIntMap> IntHeap; |
|
227 // checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
|
228 // heapSortTest<IntHeap>(); |
|
229 // heapIncreaseTest<IntHeap>(); |
|
230 // |
|
231 // typedef PairingHeap<Prio, IntNodeMap > NodeHeap; |
|
232 // checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
|
233 // dijkstraHeapTest<NodeHeap>(digraph, length, source); |
|
234 // } |
|
235 |
|
236 // RadixHeap |
200 { |
237 { |
201 typedef RadixHeap<ItemIntMap> IntHeap; |
238 typedef RadixHeap<ItemIntMap> IntHeap; |
202 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
239 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
203 heapSortTest<IntHeap>(); |
240 heapSortTest<IntHeap>(); |
204 heapIncreaseTest<IntHeap>(); |
241 heapIncreaseTest<IntHeap>(); |
206 typedef RadixHeap<IntNodeMap > NodeHeap; |
243 typedef RadixHeap<IntNodeMap > NodeHeap; |
207 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
244 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
208 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
245 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
209 } |
246 } |
210 |
247 |
|
248 // BinomHeap |
|
249 { |
|
250 typedef BinomHeap<Prio, ItemIntMap> IntHeap; |
|
251 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
|
252 heapSortTest<IntHeap>(); |
|
253 heapIncreaseTest<IntHeap>(); |
|
254 |
|
255 typedef BinomHeap<Prio, IntNodeMap > NodeHeap; |
|
256 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
|
257 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
|
258 } |
|
259 |
|
260 // BucketHeap, SimpleBucketHeap |
211 { |
261 { |
212 typedef BucketHeap<ItemIntMap> IntHeap; |
262 typedef BucketHeap<ItemIntMap> IntHeap; |
213 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
263 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
214 heapSortTest<IntHeap>(); |
264 heapSortTest<IntHeap>(); |
215 heapIncreaseTest<IntHeap>(); |
265 heapIncreaseTest<IntHeap>(); |
216 |
266 |
217 typedef BucketHeap<IntNodeMap > NodeHeap; |
267 typedef BucketHeap<IntNodeMap > NodeHeap; |
218 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
268 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
219 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
269 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
220 } |
270 |
221 |
271 typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap; |
|
272 heapSortTest<SimpleIntHeap>(); |
|
273 } |
222 |
274 |
223 return 0; |
275 return 0; |
224 } |
276 } |