1 | //======================================================================= |
2 | // Copyright (C) 2005 Jong Soo Park <jongsoo.park -at- gmail.com> |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See |
5 | // accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | //======================================================================= |
8 | #include <boost/core/lightweight_test.hpp> |
9 | #include <iostream> |
10 | #include <algorithm> |
11 | #include <boost/graph/adjacency_list.hpp> |
12 | #include <boost/graph/dominator_tree.hpp> |
13 | |
14 | using namespace std; |
15 | |
16 | struct DominatorCorrectnessTestSet |
17 | { |
18 | typedef pair< int, int > edge; |
19 | |
20 | int numOfVertices; |
21 | vector< edge > edges; |
22 | vector< int > correctIdoms; |
23 | }; |
24 | |
25 | using namespace boost; |
26 | |
27 | typedef adjacency_list< listS, listS, bidirectionalS, |
28 | property< vertex_index_t, std::size_t >, no_property > |
29 | G; |
30 | |
31 | int main(int, char*[]) |
32 | { |
33 | typedef DominatorCorrectnessTestSet::edge edge; |
34 | |
35 | DominatorCorrectnessTestSet testSet[7]; |
36 | |
37 | // Tarjan's paper |
38 | testSet[0].numOfVertices = 13; |
39 | testSet[0].edges.push_back(x: edge(0, 1)); |
40 | testSet[0].edges.push_back(x: edge(0, 2)); |
41 | testSet[0].edges.push_back(x: edge(0, 3)); |
42 | testSet[0].edges.push_back(x: edge(1, 4)); |
43 | testSet[0].edges.push_back(x: edge(2, 1)); |
44 | testSet[0].edges.push_back(x: edge(2, 4)); |
45 | testSet[0].edges.push_back(x: edge(2, 5)); |
46 | testSet[0].edges.push_back(x: edge(3, 6)); |
47 | testSet[0].edges.push_back(x: edge(3, 7)); |
48 | testSet[0].edges.push_back(x: edge(4, 12)); |
49 | testSet[0].edges.push_back(x: edge(5, 8)); |
50 | testSet[0].edges.push_back(x: edge(6, 9)); |
51 | testSet[0].edges.push_back(x: edge(7, 9)); |
52 | testSet[0].edges.push_back(x: edge(7, 10)); |
53 | testSet[0].edges.push_back(x: edge(8, 5)); |
54 | testSet[0].edges.push_back(x: edge(8, 11)); |
55 | testSet[0].edges.push_back(x: edge(9, 11)); |
56 | testSet[0].edges.push_back(x: edge(10, 9)); |
57 | testSet[0].edges.push_back(x: edge(11, 0)); |
58 | testSet[0].edges.push_back(x: edge(11, 9)); |
59 | testSet[0].edges.push_back(x: edge(12, 8)); |
60 | testSet[0].correctIdoms.push_back(x: (numeric_limits< int >::max)()); |
61 | testSet[0].correctIdoms.push_back(x: 0); |
62 | testSet[0].correctIdoms.push_back(x: 0); |
63 | testSet[0].correctIdoms.push_back(x: 0); |
64 | testSet[0].correctIdoms.push_back(x: 0); |
65 | testSet[0].correctIdoms.push_back(x: 0); |
66 | testSet[0].correctIdoms.push_back(x: 3); |
67 | testSet[0].correctIdoms.push_back(x: 3); |
68 | testSet[0].correctIdoms.push_back(x: 0); |
69 | testSet[0].correctIdoms.push_back(x: 0); |
70 | testSet[0].correctIdoms.push_back(x: 7); |
71 | testSet[0].correctIdoms.push_back(x: 0); |
72 | testSet[0].correctIdoms.push_back(x: 4); |
73 | |
74 | // Appel. p441. figure 19.4 |
75 | testSet[1].numOfVertices = 7; |
76 | testSet[1].edges.push_back(x: edge(0, 1)); |
77 | testSet[1].edges.push_back(x: edge(1, 2)); |
78 | testSet[1].edges.push_back(x: edge(1, 3)); |
79 | testSet[1].edges.push_back(x: edge(2, 4)); |
80 | testSet[1].edges.push_back(x: edge(2, 5)); |
81 | testSet[1].edges.push_back(x: edge(4, 6)); |
82 | testSet[1].edges.push_back(x: edge(5, 6)); |
83 | testSet[1].edges.push_back(x: edge(6, 1)); |
84 | testSet[1].correctIdoms.push_back(x: (numeric_limits< int >::max)()); |
85 | testSet[1].correctIdoms.push_back(x: 0); |
86 | testSet[1].correctIdoms.push_back(x: 1); |
87 | testSet[1].correctIdoms.push_back(x: 1); |
88 | testSet[1].correctIdoms.push_back(x: 2); |
89 | testSet[1].correctIdoms.push_back(x: 2); |
90 | testSet[1].correctIdoms.push_back(x: 2); |
91 | |
92 | // Appel. p449. figure 19.8 |
93 | testSet[2].numOfVertices = 13, testSet[2].edges.push_back(x: edge(0, 1)); |
94 | testSet[2].edges.push_back(x: edge(0, 2)); |
95 | testSet[2].edges.push_back(x: edge(1, 3)); |
96 | testSet[2].edges.push_back(x: edge(1, 6)); |
97 | testSet[2].edges.push_back(x: edge(2, 4)); |
98 | testSet[2].edges.push_back(x: edge(2, 7)); |
99 | testSet[2].edges.push_back(x: edge(3, 5)); |
100 | testSet[2].edges.push_back(x: edge(3, 6)); |
101 | testSet[2].edges.push_back(x: edge(4, 7)); |
102 | testSet[2].edges.push_back(x: edge(4, 2)); |
103 | testSet[2].edges.push_back(x: edge(5, 8)); |
104 | testSet[2].edges.push_back(x: edge(5, 10)); |
105 | testSet[2].edges.push_back(x: edge(6, 9)); |
106 | testSet[2].edges.push_back(x: edge(7, 12)); |
107 | testSet[2].edges.push_back(x: edge(8, 11)); |
108 | testSet[2].edges.push_back(x: edge(9, 8)); |
109 | testSet[2].edges.push_back(x: edge(10, 11)); |
110 | testSet[2].edges.push_back(x: edge(11, 1)); |
111 | testSet[2].edges.push_back(x: edge(11, 12)); |
112 | testSet[2].correctIdoms.push_back(x: (numeric_limits< int >::max)()); |
113 | testSet[2].correctIdoms.push_back(x: 0); |
114 | testSet[2].correctIdoms.push_back(x: 0); |
115 | testSet[2].correctIdoms.push_back(x: 1); |
116 | testSet[2].correctIdoms.push_back(x: 2); |
117 | testSet[2].correctIdoms.push_back(x: 3); |
118 | testSet[2].correctIdoms.push_back(x: 1); |
119 | testSet[2].correctIdoms.push_back(x: 2); |
120 | testSet[2].correctIdoms.push_back(x: 1); |
121 | testSet[2].correctIdoms.push_back(x: 6); |
122 | testSet[2].correctIdoms.push_back(x: 5); |
123 | testSet[2].correctIdoms.push_back(x: 1); |
124 | testSet[2].correctIdoms.push_back(x: 0); |
125 | |
126 | testSet[3].numOfVertices = 8, testSet[3].edges.push_back(x: edge(0, 1)); |
127 | testSet[3].edges.push_back(x: edge(1, 2)); |
128 | testSet[3].edges.push_back(x: edge(1, 3)); |
129 | testSet[3].edges.push_back(x: edge(2, 7)); |
130 | testSet[3].edges.push_back(x: edge(3, 4)); |
131 | testSet[3].edges.push_back(x: edge(4, 5)); |
132 | testSet[3].edges.push_back(x: edge(4, 6)); |
133 | testSet[3].edges.push_back(x: edge(5, 7)); |
134 | testSet[3].edges.push_back(x: edge(6, 4)); |
135 | testSet[3].correctIdoms.push_back(x: (numeric_limits< int >::max)()); |
136 | testSet[3].correctIdoms.push_back(x: 0); |
137 | testSet[3].correctIdoms.push_back(x: 1); |
138 | testSet[3].correctIdoms.push_back(x: 1); |
139 | testSet[3].correctIdoms.push_back(x: 3); |
140 | testSet[3].correctIdoms.push_back(x: 4); |
141 | testSet[3].correctIdoms.push_back(x: 4); |
142 | testSet[3].correctIdoms.push_back(x: 1); |
143 | |
144 | // Muchnick. p256. figure 8.21 |
145 | testSet[4].numOfVertices = 8, testSet[4].edges.push_back(x: edge(0, 1)); |
146 | testSet[4].edges.push_back(x: edge(1, 2)); |
147 | testSet[4].edges.push_back(x: edge(2, 3)); |
148 | testSet[4].edges.push_back(x: edge(2, 4)); |
149 | testSet[4].edges.push_back(x: edge(3, 2)); |
150 | testSet[4].edges.push_back(x: edge(4, 5)); |
151 | testSet[4].edges.push_back(x: edge(4, 6)); |
152 | testSet[4].edges.push_back(x: edge(5, 7)); |
153 | testSet[4].edges.push_back(x: edge(6, 7)); |
154 | testSet[4].correctIdoms.push_back(x: (numeric_limits< int >::max)()); |
155 | testSet[4].correctIdoms.push_back(x: 0); |
156 | testSet[4].correctIdoms.push_back(x: 1); |
157 | testSet[4].correctIdoms.push_back(x: 2); |
158 | testSet[4].correctIdoms.push_back(x: 2); |
159 | testSet[4].correctIdoms.push_back(x: 4); |
160 | testSet[4].correctIdoms.push_back(x: 4); |
161 | testSet[4].correctIdoms.push_back(x: 4); |
162 | |
163 | // Muchnick. p253. figure 8.18 |
164 | testSet[5].numOfVertices = 8, testSet[5].edges.push_back(x: edge(0, 1)); |
165 | testSet[5].edges.push_back(x: edge(0, 2)); |
166 | testSet[5].edges.push_back(x: edge(1, 6)); |
167 | testSet[5].edges.push_back(x: edge(2, 3)); |
168 | testSet[5].edges.push_back(x: edge(2, 4)); |
169 | testSet[5].edges.push_back(x: edge(3, 7)); |
170 | testSet[5].edges.push_back(x: edge(5, 7)); |
171 | testSet[5].edges.push_back(x: edge(6, 7)); |
172 | testSet[5].correctIdoms.push_back(x: (numeric_limits< int >::max)()); |
173 | testSet[5].correctIdoms.push_back(x: 0); |
174 | testSet[5].correctIdoms.push_back(x: 0); |
175 | testSet[5].correctIdoms.push_back(x: 2); |
176 | testSet[5].correctIdoms.push_back(x: 2); |
177 | testSet[5].correctIdoms.push_back(x: (numeric_limits< int >::max)()); |
178 | testSet[5].correctIdoms.push_back(x: 1); |
179 | testSet[5].correctIdoms.push_back(x: 0); |
180 | |
181 | // Cytron's paper, fig. 9 |
182 | testSet[6].numOfVertices = 14, testSet[6].edges.push_back(x: edge(0, 1)); |
183 | testSet[6].edges.push_back(x: edge(0, 13)); |
184 | testSet[6].edges.push_back(x: edge(1, 2)); |
185 | testSet[6].edges.push_back(x: edge(2, 3)); |
186 | testSet[6].edges.push_back(x: edge(2, 7)); |
187 | testSet[6].edges.push_back(x: edge(3, 4)); |
188 | testSet[6].edges.push_back(x: edge(3, 5)); |
189 | testSet[6].edges.push_back(x: edge(4, 6)); |
190 | testSet[6].edges.push_back(x: edge(5, 6)); |
191 | testSet[6].edges.push_back(x: edge(6, 8)); |
192 | testSet[6].edges.push_back(x: edge(7, 8)); |
193 | testSet[6].edges.push_back(x: edge(8, 9)); |
194 | testSet[6].edges.push_back(x: edge(9, 10)); |
195 | testSet[6].edges.push_back(x: edge(9, 11)); |
196 | testSet[6].edges.push_back(x: edge(10, 11)); |
197 | testSet[6].edges.push_back(x: edge(11, 9)); |
198 | testSet[6].edges.push_back(x: edge(11, 12)); |
199 | testSet[6].edges.push_back(x: edge(12, 2)); |
200 | testSet[6].edges.push_back(x: edge(12, 13)); |
201 | testSet[6].correctIdoms.push_back(x: (numeric_limits< int >::max)()); |
202 | testSet[6].correctIdoms.push_back(x: 0); |
203 | testSet[6].correctIdoms.push_back(x: 1); |
204 | testSet[6].correctIdoms.push_back(x: 2); |
205 | testSet[6].correctIdoms.push_back(x: 3); |
206 | testSet[6].correctIdoms.push_back(x: 3); |
207 | testSet[6].correctIdoms.push_back(x: 3); |
208 | testSet[6].correctIdoms.push_back(x: 2); |
209 | testSet[6].correctIdoms.push_back(x: 2); |
210 | testSet[6].correctIdoms.push_back(x: 8); |
211 | testSet[6].correctIdoms.push_back(x: 9); |
212 | testSet[6].correctIdoms.push_back(x: 9); |
213 | testSet[6].correctIdoms.push_back(x: 11); |
214 | testSet[6].correctIdoms.push_back(x: 0); |
215 | |
216 | for (size_t i = 0; i < sizeof(testSet) / sizeof(testSet[0]); ++i) |
217 | { |
218 | const int numOfVertices = testSet[i].numOfVertices; |
219 | |
220 | G g(testSet[i].edges.begin(), testSet[i].edges.end(), numOfVertices); |
221 | |
222 | typedef graph_traits< G >::vertex_descriptor Vertex; |
223 | typedef property_map< G, vertex_index_t >::type IndexMap; |
224 | typedef iterator_property_map< vector< Vertex >::iterator, IndexMap > |
225 | PredMap; |
226 | |
227 | vector< Vertex > domTreePredVector, domTreePredVector2; |
228 | IndexMap indexMap(get(p: vertex_index, g)); |
229 | graph_traits< G >::vertex_iterator uItr, uEnd; |
230 | int j = 0; |
231 | for (boost::tie(t0&: uItr, t1&: uEnd) = vertices(g_: g); uItr != uEnd; ++uItr, ++j) |
232 | { |
233 | put(pa: indexMap, k: *uItr, v: j); |
234 | } |
235 | |
236 | // Lengauer-Tarjan dominator tree algorithm |
237 | domTreePredVector = vector< Vertex >( |
238 | num_vertices(g_: g), graph_traits< G >::null_vertex()); |
239 | PredMap domTreePredMap |
240 | = make_iterator_property_map(iter: domTreePredVector.begin(), id: indexMap); |
241 | |
242 | lengauer_tarjan_dominator_tree(g, entry: vertex(n: 0, g_: g), domTreePredMap); |
243 | |
244 | vector< int > idom(num_vertices(g_: g)); |
245 | for (boost::tie(t0&: uItr, t1&: uEnd) = vertices(g_: g); uItr != uEnd; ++uItr) |
246 | { |
247 | if (get(pa: domTreePredMap, k: *uItr) != graph_traits< G >::null_vertex()) |
248 | idom[get(pa: indexMap, k: *uItr)] |
249 | = get(pa: indexMap, k: get(pa: domTreePredMap, k: *uItr)); |
250 | else |
251 | idom[get(pa: indexMap, k: *uItr)] = (numeric_limits< int >::max)(); |
252 | } |
253 | |
254 | copy(first: idom.begin(), last: idom.end(), result: ostream_iterator< int >(cout, " " )); |
255 | cout << endl; |
256 | |
257 | // dominator tree correctness test |
258 | BOOST_TEST(std::equal( |
259 | idom.begin(), idom.end(), testSet[i].correctIdoms.begin())); |
260 | |
261 | // compare results of fast version and slow version of dominator tree |
262 | domTreePredVector2 = vector< Vertex >( |
263 | num_vertices(g_: g), graph_traits< G >::null_vertex()); |
264 | domTreePredMap |
265 | = make_iterator_property_map(iter: domTreePredVector2.begin(), id: indexMap); |
266 | |
267 | iterative_bit_vector_dominator_tree(g, entry: vertex(n: 0, g_: g), domTreePredMap); |
268 | |
269 | vector< int > idom2(num_vertices(g_: g)); |
270 | for (boost::tie(t0&: uItr, t1&: uEnd) = vertices(g_: g); uItr != uEnd; ++uItr) |
271 | { |
272 | if (get(pa: domTreePredMap, k: *uItr) != graph_traits< G >::null_vertex()) |
273 | idom2[get(pa: indexMap, k: *uItr)] |
274 | = get(pa: indexMap, k: get(pa: domTreePredMap, k: *uItr)); |
275 | else |
276 | idom2[get(pa: indexMap, k: *uItr)] = (numeric_limits< int >::max)(); |
277 | } |
278 | |
279 | copy(first: idom2.begin(), last: idom2.end(), result: ostream_iterator< int >(cout, " " )); |
280 | cout << endl; |
281 | |
282 | size_t k; |
283 | for (k = 0; k < num_vertices(g_: g); ++k) |
284 | BOOST_TEST(domTreePredVector[k] == domTreePredVector2[k]); |
285 | } |
286 | |
287 | return boost::report_errors(); |
288 | } |
289 | |