Line data Source code
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 0 : time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v,
33 : TimeT& t)
34 0 : : timeStamper_(timeMap, t), v_(v) { }
35 :
36 : template<class Graph>
37 : void
38 0 : operator()(const typename property_traits<TimeMap>::key_type& v,
39 : const Graph& g)
40 : {
41 0 : timeStamper_(v, g);
42 0 : 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 0 : 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 0 : 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 0 : dominator_visitor(const Graph& g, const Vertex& entry,
78 : const IndexMap& indexMap,
79 : DomTreePredMap domTreePredMap)
80 : : semi_(num_vertices(g)),
81 0 : ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),
82 : samedom_(ancestor_),
83 : best_(semi_),
84 0 : semiMap_(make_iterator_property_map(semi_.begin(),
85 : indexMap)),
86 0 : ancestorMap_(make_iterator_property_map(ancestor_.begin(),
87 : indexMap)),
88 0 : bestMap_(make_iterator_property_map(best_.begin(),
89 : indexMap)),
90 : buckets_(num_vertices(g)),
91 0 : bucketMap_(make_iterator_property_map(buckets_.begin(),
92 : indexMap)),
93 : entry_(entry),
94 : domTreePredMap_(domTreePredMap),
95 0 : numOfVertices_(num_vertices(g)),
96 0 : samedomMap(make_iterator_property_map(samedom_.begin(),
97 0 : indexMap))
98 : {
99 0 : }
100 :
101 : void
102 0 : operator()(const Vertex& n, const TimeMap& dfnumMap,
103 : const PredMap& parentMap, const Graph& g)
104 : {
105 0 : if (n == entry_) return;
106 :
107 0 : const Vertex p(get(parentMap, n));
108 0 : 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 0 : typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
124 0 : for (boost::tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr)
125 : {
126 0 : const Vertex v = source(*inItr, g);
127 : // To deal with unreachable nodes
128 0 : if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices_)
129 0 : continue;
130 :
131 : Vertex s2;
132 0 : if (get(dfnumMap, v) <= get(dfnumMap, n))
133 : s2 = v;
134 : else
135 0 : s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap));
136 :
137 0 : if (get(dfnumMap, s2) < get(dfnumMap, s))
138 0 : s = s2;
139 : }
140 0 : 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 0 : get(bucketMap_, s).push_back(n);
145 0 : get(ancestorMap_, n) = p;
146 0 : 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 0 : typename std::deque<Vertex>::iterator buckItr;
159 0 : for (buckItr = get(bucketMap_, p).begin();
160 0 : buckItr != get(bucketMap_, p).end();
161 0 : ++buckItr)
162 : {
163 0 : const Vertex v(*buckItr);
164 0 : const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap));
165 0 : if (get(semiMap_, y) == get(semiMap_, v))
166 0 : put(domTreePredMap_, v, p);
167 : else
168 0 : put(samedomMap, v, y);
169 : }
170 :
171 0 : get(bucketMap_, p).clear();
172 : }
173 :
174 : protected :
175 :
176 : /**
177 : * Evaluate function in Tarjan's path compression
178 : */
179 : const Vertex
180 0 : ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap)
181 : {
182 0 : const Vertex a(get(ancestorMap_, v));
183 :
184 0 : if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex())
185 : {
186 0 : const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap));
187 :
188 0 : put(ancestorMap_, v, get(ancestorMap_, a));
189 :
190 0 : if (get(dfnumMap, get(semiMap_, b)) <
191 0 : get(dfnumMap, get(semiMap_, get(bestMap_, v))))
192 0 : put(bestMap_, v, b);
193 : }
194 :
195 0 : 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 0 : 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 0 : const VerticesSizeType numOfVertices = num_vertices(g);
253 0 : 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 0 : visitor(g, entry, indexMap, domTreePredMap);
258 :
259 : VerticesSizeType i;
260 0 : for (i = 0; i < numOfVertices; ++i)
261 : {
262 0 : const Vertex u(verticesByDFNum[numOfVertices - 1 - i]);
263 0 : if (u != graph_traits<Graph>::null_vertex())
264 0 : 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 0 : for (i = 0; i < numOfVertices; ++i)
270 : {
271 0 : const Vertex n(verticesByDFNum[i]);
272 :
273 0 : if (n == entry || n == graph_traits<Graph>::null_vertex())
274 0 : continue;
275 :
276 0 : Vertex u = get(visitor.samedomMap, n);
277 0 : if (u != graph_traits<Graph>::null_vertex())
278 : {
279 0 : 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 0 : 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 0 : const VerticesSizeType numOfVertices = num_vertices(g);
309 0 : if (numOfVertices == 0) return;
310 :
311 0 : VerticesSizeType time =
312 : (std::numeric_limits<VerticesSizeType>::max)();
313 : std::vector<default_color_type>
314 0 : colors(numOfVertices, color_traits<default_color_type>::white());
315 : depth_first_visit
316 0 : (g, entry,
317 : make_dfs_visitor
318 0 : (make_pair(record_predecessors(parentMap, on_tree_edge()),
319 : detail::stamp_times_with_vertex_vector
320 0 : (dfnumMap, verticesByDFNum, time, on_discover_vertex()))),
321 : make_iterator_property_map(colors.begin(), indexMap));
322 :
323 : // 2. Run main algorithm.
324 0 : 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 0 : 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 0 : const VerticesSizeType numOfVertices = num_vertices(g);
355 0 : if (numOfVertices == 0) return;
356 :
357 0 : const IndexMap indexMap = get(vertex_index, g);
358 :
359 0 : std::vector<VerticesSizeType> dfnum(numOfVertices, 0);
360 0 : TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));
361 :
362 0 : std::vector<Vertex> parent(numOfVertices,
363 0 : graph_traits<Graph>::null_vertex());
364 0 : PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));
365 :
366 0 : std::vector<Vertex> verticesByDFNum(parent);
367 :
368 : // Run main algorithm
369 0 : 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
|
