1 | //======================================================================= |
2 | // Copyright (C) 2005-2009 Jongsoo Park <jongsoo.park -at- gmail.com> |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. |
5 | // (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | //======================================================================= |
8 | |
9 | #ifndef BOOST_GRAPH_DOMINATOR_HPP |
10 | #define BOOST_GRAPH_DOMINATOR_HPP |
11 | |
12 | #include <boost/config.hpp> |
13 | #include <deque> |
14 | #include <set> |
15 | #include <boost/graph/depth_first_search.hpp> |
16 | #include <boost/concept/assert.hpp> |
17 | |
18 | // Dominator tree computation |
19 | |
20 | // NOTE: This file contains modifications from the distributed Boost version to |
21 | // correctly support supplying a vertex index map to the algorithm. To |
22 | // differentiate it, it has been moved into the boost_ue2 namespace. |
23 | |
24 | namespace boost_ue2 { |
25 | |
26 | using namespace boost; |
27 | |
28 | namespace detail { |
29 | /** |
30 | * An extended time_stamper which also records vertices for each dfs number |
31 | */ |
32 | template<class TimeMap, class VertexVector, class TimeT, class Tag> |
33 | class time_stamper_with_vertex_vector |
34 | : public base_visitor< |
35 | time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> > |
36 | { |
37 | public : |
38 | typedef Tag event_filter; |
39 | time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v, |
40 | TimeT& t) |
41 | : timeStamper_(timeMap, t), v_(v) { } |
42 | |
43 | template<class Graph> |
44 | void |
45 | operator()(const typename property_traits<TimeMap>::key_type& v, |
46 | const Graph& g) |
47 | { |
48 | timeStamper_(v, g); |
49 | v_[timeStamper_.m_time] = v; |
50 | } |
51 | |
52 | private : |
53 | time_stamper<TimeMap, TimeT, Tag> timeStamper_; |
54 | VertexVector& v_; |
55 | }; |
56 | |
57 | /** |
58 | * A convenient way to create a time_stamper_with_vertex_vector |
59 | */ |
60 | template<class TimeMap, class VertexVector, class TimeT, class Tag> |
61 | time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> |
62 | stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t, |
63 | Tag) |
64 | { |
65 | return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, |
66 | Tag>(timeMap, v, t); |
67 | } |
68 | |
69 | template<class Graph, class IndexMap, class TimeMap, class PredMap, |
70 | class DomTreePredMap> |
71 | class dominator_visitor |
72 | { |
73 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
74 | typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; |
75 | |
76 | public : |
77 | /** |
78 | * @param g [in] the target graph of the dominator tree |
79 | * @param entry [in] the entry node of g |
80 | * @param indexMap [in] the vertex index map for g |
81 | * @param domTreePredMap [out] the immediate dominator map |
82 | * (parent map in dominator tree) |
83 | */ |
84 | dominator_visitor(const Graph& g, const Vertex& entry, |
85 | const IndexMap& indexMap, |
86 | DomTreePredMap domTreePredMap) |
87 | : semi_(num_vertices(g)), |
88 | ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()), |
89 | samedom_(ancestor_), |
90 | best_(semi_), |
91 | semiMap_(make_iterator_property_map(semi_.begin(), |
92 | indexMap)), |
93 | ancestorMap_(make_iterator_property_map(ancestor_.begin(), |
94 | indexMap)), |
95 | bestMap_(make_iterator_property_map(best_.begin(), |
96 | indexMap)), |
97 | buckets_(num_vertices(g)), |
98 | bucketMap_(make_iterator_property_map(buckets_.begin(), |
99 | indexMap)), |
100 | entry_(entry), |
101 | domTreePredMap_(domTreePredMap), |
102 | numOfVertices_(num_vertices(g)), |
103 | samedomMap(make_iterator_property_map(samedom_.begin(), |
104 | indexMap)) |
105 | { |
106 | } |
107 | |
108 | void |
109 | operator()(const Vertex& n, const TimeMap& dfnumMap, |
110 | const PredMap& parentMap, const Graph& g) |
111 | { |
112 | if (n == entry_) return; |
113 | |
114 | const Vertex p(get(parentMap, n)); |
115 | Vertex s(p); |
116 | |
117 | // 1. Calculate the semidominator of n, |
118 | // based on the semidominator thm. |
119 | // * Semidominator thm. : To find the semidominator of a node n, |
120 | // consider all predecessors v of n in the CFG (Control Flow Graph). |
121 | // - If v is a proper ancestor of n in the spanning tree |
122 | // (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n) |
123 | // - If v is a non-ancestor of n (so dfnum(v) > dfnum(n)) |
124 | // then for each u that is an ancestor of v (or u = v), |
125 | // Let semi(u) be a candidate for semi(n) |
126 | // of all these candidates, the one with lowest dfnum is |
127 | // the semidominator of n. |
128 | |
129 | // For each predecessor of n |
130 | typename graph_traits<Graph>::in_edge_iterator inItr, inEnd; |
131 | for (boost::tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr) |
132 | { |
133 | const Vertex v = source(*inItr, g); |
134 | // To deal with unreachable nodes |
135 | if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices_) |
136 | continue; |
137 | |
138 | Vertex s2; |
139 | if (get(dfnumMap, v) <= get(dfnumMap, n)) |
140 | s2 = v; |
141 | else |
142 | s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap)); |
143 | |
144 | if (get(dfnumMap, s2) < get(dfnumMap, s)) |
145 | s = s2; |
146 | } |
147 | put(semiMap_, n, s); |
148 | |
149 | // 2. Calculation of n's dominator is deferred until |
150 | // the path from s to n has been linked into the forest |
151 | get(bucketMap_, s).push_back(n); |
152 | get(ancestorMap_, n) = p; |
153 | get(bestMap_, n) = n; |
154 | |
155 | // 3. Now that the path from p to v has been linked into |
156 | // the spanning forest, these lines calculate the dominator of v, |
157 | // based on the dominator thm., or else defer the calculation |
158 | // until y's dominator is known |
159 | // * Dominator thm. : On the spanning-tree path below semi(n) and |
160 | // above or including n, let y be the node |
161 | // with the smallest-numbered semidominator. Then, |
162 | // |
163 | // idom(n) = semi(n) if semi(y)=semi(n) or |
164 | // idom(y) if semi(y) != semi(n) |
165 | typename std::deque<Vertex>::iterator buckItr; |
166 | for (buckItr = get(bucketMap_, p).begin(); |
167 | buckItr != get(bucketMap_, p).end(); |
168 | ++buckItr) |
169 | { |
170 | const Vertex v(*buckItr); |
171 | const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap)); |
172 | if (get(semiMap_, y) == get(semiMap_, v)) |
173 | put(domTreePredMap_, v, p); |
174 | else |
175 | put(samedomMap, v, y); |
176 | } |
177 | |
178 | get(bucketMap_, p).clear(); |
179 | } |
180 | |
181 | protected : |
182 | |
183 | /** |
184 | * Evaluate function in Tarjan's path compression |
185 | */ |
186 | const Vertex |
187 | ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap) |
188 | { |
189 | const Vertex a(get(ancestorMap_, v)); |
190 | |
191 | if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex()) |
192 | { |
193 | const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap)); |
194 | |
195 | put(ancestorMap_, v, get(ancestorMap_, a)); |
196 | |
197 | if (get(dfnumMap, get(semiMap_, b)) < |
198 | get(dfnumMap, get(semiMap_, get(bestMap_, v)))) |
199 | put(bestMap_, v, b); |
200 | } |
201 | |
202 | return get(bestMap_, v); |
203 | } |
204 | |
205 | std::vector<Vertex> semi_, ancestor_, samedom_, best_; |
206 | PredMap semiMap_, ancestorMap_, bestMap_; |
207 | std::vector< std::deque<Vertex> > buckets_; |
208 | |
209 | iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator, |
210 | IndexMap> bucketMap_; |
211 | |
212 | const Vertex& entry_; |
213 | DomTreePredMap domTreePredMap_; |
214 | const VerticesSizeType numOfVertices_; |
215 | |
216 | public : |
217 | |
218 | PredMap samedomMap; |
219 | }; |
220 | |
221 | } // namespace detail |
222 | |
223 | /** |
224 | * @brief Build dominator tree using Lengauer-Tarjan algorithm. |
225 | * It takes O((V+E)log(V+E)) time. |
226 | * |
227 | * @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding |
228 | * indexMap. |
229 | * If dfs has already run before, |
230 | * this function would be good for saving computations. |
231 | * @pre Unreachable nodes must be masked as |
232 | * graph_traits<Graph>::null_vertex in parentMap. |
233 | * @pre Unreachable nodes must be masked as |
234 | * (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap. |
235 | * |
236 | * @param domTreePredMap [out] : immediate dominator map (parent map |
237 | * in dom. tree) |
238 | * |
239 | * @note reference Appel. p. 452~453. algorithm 19.9, 19.10. |
240 | * |
241 | * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis |
242 | */ |
243 | template<class Graph, class IndexMap, class TimeMap, class PredMap, |
244 | class VertexVector, class DomTreePredMap> |
245 | void |
246 | lengauer_tarjan_dominator_tree_without_dfs |
247 | (const Graph& g, |
248 | const typename graph_traits<Graph>::vertex_descriptor& entry, |
249 | const IndexMap& indexMap, |
250 | TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, |
251 | DomTreePredMap domTreePredMap) |
252 | { |
253 | // Typedefs and concept check |
254 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
255 | typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; |
256 | |
257 | BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); |
258 | |
259 | const VerticesSizeType numOfVertices = num_vertices(g); |
260 | if (numOfVertices == 0) return; |
261 | |
262 | // 1. Visit each vertex in reverse post order and calculate sdom. |
263 | detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap> |
264 | visitor(g, entry, indexMap, domTreePredMap); |
265 | |
266 | VerticesSizeType i; |
267 | for (i = 0; i < numOfVertices; ++i) |
268 | { |
269 | const Vertex u(verticesByDFNum[numOfVertices - 1 - i]); |
270 | if (u != graph_traits<Graph>::null_vertex()) |
271 | visitor(u, dfnumMap, parentMap, g); |
272 | } |
273 | |
274 | // 2. Now all the deferred dominator calculations, |
275 | // based on the second clause of the dominator thm., are performed |
276 | for (i = 0; i < numOfVertices; ++i) |
277 | { |
278 | const Vertex n(verticesByDFNum[i]); |
279 | |
280 | if (n == entry || n == graph_traits<Graph>::null_vertex()) |
281 | continue; |
282 | |
283 | Vertex u = get(visitor.samedomMap, n); |
284 | if (u != graph_traits<Graph>::null_vertex()) |
285 | { |
286 | put(domTreePredMap, n, get(domTreePredMap, u)); |
287 | } |
288 | } |
289 | } |
290 | |
291 | /** |
292 | * Unlike lengauer_tarjan_dominator_tree_without_dfs, |
293 | * dfs is run in this function and |
294 | * the result is written to dfnumMap, parentMap, vertices. |
295 | * |
296 | * If the result of dfs required after this algorithm, |
297 | * this function can eliminate the need of rerunning dfs. |
298 | */ |
299 | template<class Graph, class IndexMap, class TimeMap, class PredMap, |
300 | class VertexVector, class DomTreePredMap> |
301 | void |
302 | lengauer_tarjan_dominator_tree |
303 | (const Graph& g, |
304 | const typename graph_traits<Graph>::vertex_descriptor& entry, |
305 | const IndexMap& indexMap, |
306 | TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, |
307 | DomTreePredMap domTreePredMap) |
308 | { |
309 | // Typedefs and concept check |
310 | typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; |
311 | |
312 | BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); |
313 | |
314 | // 1. Depth first visit |
315 | const VerticesSizeType numOfVertices = num_vertices(g); |
316 | if (numOfVertices == 0) return; |
317 | |
318 | VerticesSizeType time = |
319 | (std::numeric_limits<VerticesSizeType>::max)(); |
320 | std::vector<default_color_type> |
321 | colors(numOfVertices, color_traits<default_color_type>::white()); |
322 | depth_first_visit |
323 | (g, entry, |
324 | make_dfs_visitor |
325 | (make_pair(record_predecessors(parentMap, on_tree_edge()), |
326 | detail::stamp_times_with_vertex_vector |
327 | (dfnumMap, verticesByDFNum, time, on_discover_vertex()))), |
328 | make_iterator_property_map(colors.begin(), indexMap)); |
329 | |
330 | // 2. Run main algorithm. |
331 | lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap, |
332 | parentMap, verticesByDFNum, |
333 | domTreePredMap); |
334 | } |
335 | |
336 | /** |
337 | * Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum |
338 | * internally. |
339 | * If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum), |
340 | * this function would be more convenient one. |
341 | */ |
342 | template<class Graph, class DomTreePredMap> |
343 | void |
344 | lengauer_tarjan_dominator_tree |
345 | (const Graph& g, |
346 | const typename graph_traits<Graph>::vertex_descriptor& entry, |
347 | DomTreePredMap domTreePredMap) |
348 | { |
349 | // typedefs |
350 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
351 | typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; |
352 | typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap; |
353 | typedef |
354 | iterator_property_map<typename std::vector<VerticesSizeType>::iterator, |
355 | IndexMap> TimeMap; |
356 | typedef |
357 | iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap> |
358 | PredMap; |
359 | |
360 | // Make property maps |
361 | const VerticesSizeType numOfVertices = num_vertices(g); |
362 | if (numOfVertices == 0) return; |
363 | |
364 | const IndexMap indexMap = get(vertex_index, g); |
365 | |
366 | std::vector<VerticesSizeType> dfnum(numOfVertices, 0); |
367 | TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap)); |
368 | |
369 | std::vector<Vertex> parent(numOfVertices, |
370 | graph_traits<Graph>::null_vertex()); |
371 | PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap)); |
372 | |
373 | std::vector<Vertex> verticesByDFNum(parent); |
374 | |
375 | // Run main algorithm |
376 | lengauer_tarjan_dominator_tree(g, entry, |
377 | indexMap, dfnumMap, parentMap, |
378 | verticesByDFNum, domTreePredMap); |
379 | } |
380 | |
381 | /** |
382 | * Muchnick. p. 182, 184 |
383 | * |
384 | * using iterative bit vector analysis |
385 | */ |
386 | template<class Graph, class IndexMap, class DomTreePredMap> |
387 | void |
388 | iterative_bit_vector_dominator_tree |
389 | (const Graph& g, |
390 | const typename graph_traits<Graph>::vertex_descriptor& entry, |
391 | const IndexMap& indexMap, |
392 | DomTreePredMap domTreePredMap) |
393 | { |
394 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
395 | typedef typename graph_traits<Graph>::vertex_iterator vertexItr; |
396 | typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; |
397 | typedef |
398 | iterator_property_map<typename std::vector< std::set<Vertex> >::iterator, |
399 | IndexMap> vertexSetMap; |
400 | |
401 | BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); |
402 | |
403 | // 1. Finding dominator |
404 | // 1.1. Initialize |
405 | const VerticesSizeType numOfVertices = num_vertices(g); |
406 | if (numOfVertices == 0) return; |
407 | |
408 | vertexItr vi, viend; |
409 | boost::tie(vi, viend) = vertices(g); |
410 | const std::set<Vertex> N(vi, viend); |
411 | |
412 | bool change = true; |
413 | |
414 | std::vector< std::set<Vertex> > dom(numOfVertices, N); |
415 | vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap)); |
416 | get(domMap, entry).clear(); |
417 | get(domMap, entry).insert(entry); |
418 | |
419 | while (change) |
420 | { |
421 | change = false; |
422 | for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) |
423 | { |
424 | if (*vi == entry) continue; |
425 | |
426 | std::set<Vertex> T(N); |
427 | |
428 | typename graph_traits<Graph>::in_edge_iterator inItr, inEnd; |
429 | for (boost::tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr) |
430 | { |
431 | const Vertex p = source(*inItr, g); |
432 | |
433 | std::set<Vertex> tempSet; |
434 | std::set_intersection(T.begin(), T.end(), |
435 | get(domMap, p).begin(), |
436 | get(domMap, p).end(), |
437 | std::inserter(tempSet, tempSet.begin())); |
438 | T.swap(tempSet); |
439 | } |
440 | |
441 | T.insert(*vi); |
442 | if (T != get(domMap, *vi)) |
443 | { |
444 | change = true; |
445 | get(domMap, *vi).swap(T); |
446 | } |
447 | } // end of for (boost::tie(vi, viend) = vertices(g) |
448 | } // end of while(change) |
449 | |
450 | // 2. Build dominator tree |
451 | for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) |
452 | get(domMap, *vi).erase(*vi); |
453 | |
454 | Graph domTree(numOfVertices); |
455 | |
456 | for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) |
457 | { |
458 | if (*vi == entry) continue; |
459 | |
460 | // We have to iterate through copied dominator set |
461 | const std::set<Vertex> tempSet(get(domMap, *vi)); |
462 | typename std::set<Vertex>::const_iterator s; |
463 | for (s = tempSet.begin(); s != tempSet.end(); ++s) |
464 | { |
465 | typename std::set<Vertex>::iterator t; |
466 | for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); ) |
467 | { |
468 | typename std::set<Vertex>::iterator old_t = t; |
469 | ++t; // Done early because t may become invalid |
470 | if (*old_t == *s) continue; |
471 | if (get(domMap, *s).find(*old_t) != get(domMap, *s).end()) |
472 | get(domMap, *vi).erase(old_t); |
473 | } |
474 | } |
475 | } |
476 | |
477 | for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) |
478 | { |
479 | if (*vi != entry && get(domMap, *vi).size() == 1) |
480 | { |
481 | Vertex temp = *get(domMap, *vi).begin(); |
482 | put(domTreePredMap, *vi, temp); |
483 | } |
484 | } |
485 | } |
486 | |
487 | template<class Graph, class DomTreePredMap> |
488 | void |
489 | iterative_bit_vector_dominator_tree |
490 | (const Graph& g, |
491 | const typename graph_traits<Graph>::vertex_descriptor& entry, |
492 | DomTreePredMap domTreePredMap) |
493 | { |
494 | typename property_map<Graph, vertex_index_t>::const_type |
495 | indexMap = get(vertex_index, g); |
496 | |
497 | iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap); |
498 | } |
499 | } // namespace boost |
500 | |
501 | #endif // BOOST_GRAPH_DOMINATOR_HPP |
502 | |