]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | //======================================================================= | |
f67539c2 | 8 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
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 | { | |
f67539c2 | 18 | typedef pair< int, int > edge; |
7c673cae | 19 | |
f67539c2 TL |
20 | int numOfVertices; |
21 | vector< edge > edges; | |
22 | vector< int > correctIdoms; | |
7c673cae FG |
23 | }; |
24 | ||
25 | using namespace boost; | |
26 | ||
f67539c2 TL |
27 | typedef adjacency_list< listS, listS, bidirectionalS, |
28 | property< vertex_index_t, std::size_t >, no_property > | |
29 | G; | |
7c673cae | 30 | |
f67539c2 | 31 | int main(int, char*[]) |
7c673cae | 32 | { |
f67539c2 | 33 | typedef DominatorCorrectnessTestSet::edge edge; |
7c673cae | 34 | |
f67539c2 | 35 | DominatorCorrectnessTestSet testSet[7]; |
7c673cae | 36 | |
f67539c2 TL |
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); | |
7c673cae | 73 | |
f67539c2 TL |
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); | |
7c673cae | 91 | |
f67539c2 TL |
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); | |
7c673cae | 125 | |
f67539c2 TL |
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); | |
7c673cae | 143 | |
f67539c2 TL |
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); | |
7c673cae | 162 | |
f67539c2 TL |
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); | |
7c673cae | 180 | |
f67539c2 TL |
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); | |
7c673cae | 215 | |
f67539c2 TL |
216 | for (size_t i = 0; i < sizeof(testSet) / sizeof(testSet[0]); ++i) |
217 | { | |
218 | const int numOfVertices = testSet[i].numOfVertices; | |
7c673cae | 219 | |
f67539c2 | 220 | G g(testSet[i].edges.begin(), testSet[i].edges.end(), numOfVertices); |
7c673cae | 221 | |
f67539c2 TL |
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; | |
7c673cae | 226 | |
f67539c2 TL |
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 | } | |
7c673cae | 235 | |
f67539c2 TL |
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); | |
7c673cae | 241 | |
f67539c2 | 242 | lengauer_tarjan_dominator_tree(g, vertex(0, g), domTreePredMap); |
7c673cae | 243 | |
f67539c2 TL |
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 | } | |
7c673cae | 253 | |
f67539c2 TL |
254 | copy(idom.begin(), idom.end(), ostream_iterator< int >(cout, " ")); |
255 | cout << endl; | |
7c673cae | 256 | |
f67539c2 TL |
257 | // dominator tree correctness test |
258 | BOOST_TEST(std::equal( | |
259 | idom.begin(), idom.end(), testSet[i].correctIdoms.begin())); | |
7c673cae | 260 | |
f67539c2 TL |
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); | |
7c673cae | 266 | |
f67539c2 | 267 | iterative_bit_vector_dominator_tree(g, vertex(0, g), domTreePredMap); |
7c673cae | 268 | |
f67539c2 TL |
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 | } | |
7c673cae | 278 | |
f67539c2 TL |
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 | } | |
7c673cae | 286 | |
f67539c2 | 287 | return boost::report_errors(); |
7c673cae | 288 | } |