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

source code of boost/boost/graph/dominator_tree.hpp