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
24namespace 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