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