22 #include <vector> |
22 #include <vector> |
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/list_graph.h> |
27 #include <lemon/smart_graph.h> |
28 |
28 |
29 #include <lemon/digraph_reader.h> |
29 #include <lemon/lgf_reader.h> |
|
30 #include <lemon/dijkstra.h> |
|
31 #include <lemon/maps.h> |
30 |
32 |
31 #include <lemon/bin_heap.h> |
33 #include <lemon/bin_heap.h> |
32 #include <lemon/fib_heap.h> |
|
33 #include <lemon/radix_heap.h> |
|
34 #include <lemon/bucket_heap.h> |
|
35 |
34 |
36 #include "test_tools.h" |
35 #include "test_tools.h" |
37 |
36 |
38 #include "heap_test.h" |
|
39 |
|
40 #include <lemon/time_measure.h> |
|
41 |
|
42 using namespace lemon; |
37 using namespace lemon; |
43 using namespace lemon::concepts; |
38 using namespace lemon::concepts; |
|
39 |
|
40 typedef ListDigraph Digraph; |
|
41 DIGRAPH_TYPEDEFS(Digraph); |
|
42 |
|
43 char test_lgf[] = |
|
44 "@nodes\n" |
|
45 "label\n" |
|
46 "0\n" |
|
47 "1\n" |
|
48 "2\n" |
|
49 "3\n" |
|
50 "4\n" |
|
51 "5\n" |
|
52 "6\n" |
|
53 "7\n" |
|
54 "8\n" |
|
55 "9\n" |
|
56 "@arcs\n" |
|
57 " label capacity\n" |
|
58 "0 5 0 94\n" |
|
59 "3 9 1 11\n" |
|
60 "8 7 2 83\n" |
|
61 "1 2 3 94\n" |
|
62 "5 7 4 35\n" |
|
63 "7 4 5 84\n" |
|
64 "9 5 6 38\n" |
|
65 "0 4 7 96\n" |
|
66 "6 7 8 6\n" |
|
67 "3 1 9 27\n" |
|
68 "5 2 10 77\n" |
|
69 "5 6 11 69\n" |
|
70 "6 5 12 41\n" |
|
71 "4 6 13 70\n" |
|
72 "3 2 14 45\n" |
|
73 "7 9 15 93\n" |
|
74 "5 9 16 50\n" |
|
75 "9 0 17 94\n" |
|
76 "9 6 18 67\n" |
|
77 "0 9 19 86\n" |
|
78 "@attributes\n" |
|
79 "source 3\n"; |
|
80 |
|
81 int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34}; |
|
82 int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37}; |
|
83 |
|
84 int test_len = sizeof(test_seq) / sizeof(test_seq[0]); |
|
85 |
|
86 template <typename Heap> |
|
87 void heapSortTest() { |
|
88 RangeMap<int> map(test_len, -1); |
|
89 |
|
90 Heap heap(map); |
|
91 |
|
92 std::vector<int> v(test_len); |
|
93 |
|
94 for (int i = 0; i < test_len; ++i) { |
|
95 v[i] = test_seq[i]; |
|
96 heap.push(i, v[i]); |
|
97 } |
|
98 std::sort(v.begin(), v.end()); |
|
99 for (int i = 0; i < test_len; ++i) { |
|
100 check(v[i] == heap.prio() ,"Wrong order in heap sort."); |
|
101 heap.pop(); |
|
102 } |
|
103 } |
|
104 |
|
105 template <typename Heap> |
|
106 void heapIncreaseTest() { |
|
107 RangeMap<int> map(test_len, -1); |
|
108 |
|
109 Heap heap(map); |
|
110 |
|
111 std::vector<int> v(test_len); |
|
112 |
|
113 for (int i = 0; i < test_len; ++i) { |
|
114 v[i] = test_seq[i]; |
|
115 heap.push(i, v[i]); |
|
116 } |
|
117 for (int i = 0; i < test_len; ++i) { |
|
118 v[i] += test_inc[i]; |
|
119 heap.increase(i, v[i]); |
|
120 } |
|
121 std::sort(v.begin(), v.end()); |
|
122 for (int i = 0; i < test_len; ++i) { |
|
123 check(v[i] == heap.prio() ,"Wrong order in heap increase test."); |
|
124 heap.pop(); |
|
125 } |
|
126 } |
|
127 |
|
128 |
|
129 |
|
130 template <typename Heap> |
|
131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, |
|
132 Node source) { |
|
133 |
|
134 typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>:: |
|
135 Create dijkstra(digraph, length); |
|
136 |
|
137 dijkstra.run(source); |
|
138 |
|
139 for(ArcIt a(digraph); a != INVALID; ++a) { |
|
140 Node s = digraph.source(a); |
|
141 Node t = digraph.target(a); |
|
142 if (dijkstra.reached(s)) { |
|
143 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], |
|
144 "Error in a shortest path tree!"); |
|
145 } |
|
146 } |
|
147 |
|
148 for(NodeIt n(digraph); n != INVALID; ++n) { |
|
149 if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) { |
|
150 Arc a = dijkstra.predArc(n); |
|
151 Node s = digraph.source(a); |
|
152 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], |
|
153 "Error in a shortest path tree!"); |
|
154 } |
|
155 } |
|
156 |
|
157 } |
44 |
158 |
45 int main() { |
159 int main() { |
46 |
160 |
47 typedef int Item; |
161 typedef int Item; |
48 typedef int Prio; |
162 typedef int Prio; |
49 typedef IntIntMap ItemIntMap; |
163 typedef RangeMap<int> ItemIntMap; |
|
164 |
|
165 Digraph digraph; |
|
166 IntArcMap length(digraph); |
|
167 Node source; |
50 |
168 |
51 typedef ListDigraph Digraph; |
169 std::istringstream input(test_lgf); |
52 |
170 digraphReader(input, digraph). |
53 typedef Digraph::Arc Arc; |
171 arcMap("capacity", length). |
54 typedef Digraph::Node Node; |
172 node("source", source). |
55 typedef Digraph::ArcIt ArcIt; |
|
56 typedef Digraph::NodeIt NodeIt; |
|
57 typedef Digraph::ArcMap<int> LengthMap; |
|
58 |
|
59 Digraph digraph; |
|
60 LengthMap length(digraph); |
|
61 Node start; |
|
62 |
|
63 /// \todo create own test digraph |
|
64 |
|
65 std::string f_name; |
|
66 if( getenv("srcdir") ) |
|
67 f_name = std::string(getenv("srcdir")); |
|
68 else f_name = "."; |
|
69 f_name += "/test/dijkstra_test.lgf"; |
|
70 |
|
71 std::ifstream input(f_name.c_str()); |
|
72 check(input, "Input file '" << f_name << "' not found."); |
|
73 DigraphReader<Digraph>(input, digraph). |
|
74 readArcMap("capacity", length). |
|
75 readNode("source", start). |
|
76 run(); |
173 run(); |
77 |
174 |
78 { |
175 { |
79 std::cout << "Checking Bin Heap" << std::endl; |
|
80 |
|
81 typedef BinHeap<Prio, ItemIntMap> IntHeap; |
176 typedef BinHeap<Prio, ItemIntMap> IntHeap; |
82 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
177 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
83 heapSortTest<IntHeap>(100); |
178 heapSortTest<IntHeap>(); |
84 heapIncreaseTest<IntHeap>(100); |
179 heapIncreaseTest<IntHeap>(); |
85 |
180 |
86 typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap; |
181 typedef BinHeap<Prio, IntNodeMap > NodeHeap; |
87 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); |
182 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); |
88 Timer timer; |
183 dijkstraHeapTest<NodeHeap>(digraph, length, source); |
89 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); |
|
90 std::cout << timer << std::endl; |
|
91 } |
|
92 { |
|
93 std::cout << "Checking Fib Heap" << std::endl; |
|
94 |
|
95 typedef FibHeap<Prio, ItemIntMap> IntHeap; |
|
96 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
|
97 heapSortTest<IntHeap>(100); |
|
98 heapIncreaseTest<IntHeap>(100); |
|
99 |
|
100 typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap; |
|
101 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); |
|
102 Timer timer; |
|
103 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); |
|
104 std::cout << timer << std::endl; |
|
105 } |
|
106 { |
|
107 std::cout << "Checking Radix Heap" << std::endl; |
|
108 |
|
109 typedef RadixHeap<ItemIntMap> IntHeap; |
|
110 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
|
111 heapSortTest<IntHeap>(100); |
|
112 heapIncreaseTest<IntHeap>(100); |
|
113 |
|
114 typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap; |
|
115 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); |
|
116 Timer timer; |
|
117 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); |
|
118 std::cout << timer << std::endl; |
|
119 } |
|
120 |
|
121 { |
|
122 std::cout << "Checking Bucket Heap" << std::endl; |
|
123 |
|
124 typedef BucketHeap<ItemIntMap> IntHeap; |
|
125 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
|
126 heapSortTest<IntHeap>(100); |
|
127 heapIncreaseTest<IntHeap>(100); |
|
128 |
|
129 typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap; |
|
130 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); |
|
131 Timer timer; |
|
132 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); |
|
133 std::cout << timer << std::endl; |
|
134 } |
184 } |
135 |
185 |
136 return 0; |
186 return 0; |
137 } |
187 } |