13 #include <lemon/graph_reader.h> |
13 #include <lemon/graph_reader.h> |
14 |
14 |
15 #include <lemon/bin_heap.h> |
15 #include <lemon/bin_heap.h> |
16 #include <lemon/fib_heap.h> |
16 #include <lemon/fib_heap.h> |
17 #include <lemon/radix_heap.h> |
17 #include <lemon/radix_heap.h> |
|
18 #include <lemon/linear_heap.h> |
18 |
19 |
19 #include "test_tools.h" |
20 #include "test_tools.h" |
20 |
21 |
21 #include "heap_test.h" |
22 #include "heap_test.h" |
22 |
23 |
|
24 #include <lemon/time_measure.h> |
23 |
25 |
24 using namespace lemon; |
26 using namespace lemon; |
25 using namespace lemon::concept; |
27 using namespace lemon::concept; |
26 |
28 |
27 |
29 |
63 heapSortTest<IntHeap>(100); |
65 heapSortTest<IntHeap>(100); |
64 heapIncreaseTest<IntHeap>(100); |
66 heapIncreaseTest<IntHeap>(100); |
65 |
67 |
66 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
68 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
67 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
69 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
|
70 Timer timer; |
68 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
71 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
|
72 std::cout << timer << std::endl; |
69 } |
73 } |
70 { |
74 { |
71 std::cerr << "Checking Fib Heap" << std::endl; |
75 std::cerr << "Checking Fib Heap" << std::endl; |
72 |
76 |
73 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap; |
77 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap; |
75 heapSortTest<IntHeap>(100); |
79 heapSortTest<IntHeap>(100); |
76 heapIncreaseTest<IntHeap>(100); |
80 heapIncreaseTest<IntHeap>(100); |
77 |
81 |
78 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
82 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
79 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
83 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
|
84 Timer timer; |
80 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
85 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
|
86 std::cout << timer << std::endl; |
81 } |
87 } |
82 { |
88 { |
83 std::cerr << "Checking Radix Heap" << std::endl; |
89 std::cerr << "Checking Radix Heap" << std::endl; |
84 |
90 |
85 typedef RadixHeap<Item, ItemIntMap> IntHeap; |
91 typedef RadixHeap<Item, ItemIntMap> IntHeap; |
87 heapSortTest<IntHeap>(100); |
93 heapSortTest<IntHeap>(100); |
88 heapIncreaseTest<IntHeap>(100); |
94 heapIncreaseTest<IntHeap>(100); |
89 |
95 |
90 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap; |
96 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap; |
91 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
97 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
|
98 Timer timer; |
92 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
99 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
|
100 std::cout << timer << std::endl; |
|
101 } |
|
102 |
|
103 { |
|
104 std::cerr << "Checking Linear Heap" << std::endl; |
|
105 |
|
106 typedef LinearHeap<Item, ItemIntMap> IntHeap; |
|
107 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>(); |
|
108 heapSortTest<IntHeap>(100); |
|
109 heapIncreaseTest<IntHeap>(100); |
|
110 |
|
111 typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap; |
|
112 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
|
113 Timer timer; |
|
114 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
|
115 std::cout << timer << std::endl; |
93 } |
116 } |
94 |
117 |
95 std::cout << __FILE__ ": All tests passed.\n"; |
118 std::cout << __FILE__ ": All tests passed.\n"; |
96 |
119 |
97 return 0; |
120 return 0; |