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