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