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