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