1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/dominator_tree.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,488 @@
1.4 +//=======================================================================
1.5 +// Copyright (C) 2005 Jong Soo Park <jongsoo.park -at- gmail.com>
1.6 +//
1.7 +// Distributed under the Boost Software License, Version 1.0.
1.8 +// (See accompanying file LICENSE_1_0.txt or copy at
1.9 +// http://www.boost.org/LICENSE_1_0.txt)
1.10 +//=======================================================================
1.11 +// Dominator tree computation
1.12 +#ifndef BOOST_GRAPH_DOMINATOR_HPP
1.13 +#define BOOST_GRAPH_DOMINATOR_HPP
1.14 +
1.15 +#include <boost/config.hpp>
1.16 +#include <deque>
1.17 +#include <set>
1.18 +#include <boost/graph/depth_first_search.hpp>
1.19 +
1.20 +namespace boost {
1.21 + namespace detail {
1.22 + /**
1.23 + * An extended time_stamper which also records vertices for each dfs number
1.24 + */
1.25 + template<class TimeMap, class VertexVector, class TimeT, class Tag>
1.26 + class time_stamper_with_vertex_vector
1.27 + : public base_visitor<
1.28 + time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> >
1.29 + {
1.30 + public :
1.31 + typedef Tag event_filter;
1.32 + time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v,
1.33 + TimeT& t)
1.34 + : timeStamper_(timeMap, t), v_(v) { }
1.35 +
1.36 + template<class Graph>
1.37 + void
1.38 + operator()(const typename property_traits<TimeMap>::key_type& v,
1.39 + const Graph& g)
1.40 + {
1.41 + timeStamper_(v, g);
1.42 + v_[timeStamper_.m_time] = v;
1.43 + }
1.44 +
1.45 + private :
1.46 + time_stamper<TimeMap, TimeT, Tag> timeStamper_;
1.47 + VertexVector& v_;
1.48 + };
1.49 +
1.50 + /**
1.51 + * A convenient way to create a time_stamper_with_vertex_vector
1.52 + */
1.53 + template<class TimeMap, class VertexVector, class TimeT, class Tag>
1.54 + time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag>
1.55 + stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t,
1.56 + Tag)
1.57 + {
1.58 + return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT,
1.59 + Tag>(timeMap, v, t);
1.60 + }
1.61 +
1.62 + template<class Graph, class IndexMap, class TimeMap, class PredMap,
1.63 + class DomTreePredMap>
1.64 + class dominator_visitor
1.65 + {
1.66 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.67 + typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
1.68 +
1.69 + public :
1.70 + /**
1.71 + * @param g [in] the target graph of the dominator tree
1.72 + * @param entry [in] the entry node of g
1.73 + * @param domTreePredMap [out] the immediate dominator map
1.74 + * (parent map in dominator tree)
1.75 + */
1.76 + dominator_visitor(const Graph& g, const Vertex& entry,
1.77 + DomTreePredMap domTreePredMap)
1.78 + : semi_(num_vertices(g)),
1.79 + ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),
1.80 + samedom_(ancestor_),
1.81 + best_(semi_),
1.82 + semiMap_(make_iterator_property_map(semi_.begin(),
1.83 + get(vertex_index, g))),
1.84 + ancestorMap_(make_iterator_property_map(ancestor_.begin(),
1.85 + get(vertex_index, g))),
1.86 + bestMap_(make_iterator_property_map(best_.begin(),
1.87 + get(vertex_index, g))),
1.88 + buckets_(num_vertices(g)),
1.89 + bucketMap_(make_iterator_property_map(buckets_.begin(),
1.90 + get(vertex_index, g))),
1.91 + entry_(entry),
1.92 + domTreePredMap_(domTreePredMap),
1.93 + samedomMap(make_iterator_property_map(samedom_.begin(),
1.94 + get(vertex_index, g)))
1.95 + {
1.96 + }
1.97 +
1.98 + void
1.99 + operator()(const Vertex& n, const TimeMap& dfnumMap,
1.100 + const PredMap& parentMap, const Graph& g)
1.101 + {
1.102 + if (n == entry_) return;
1.103 +
1.104 + const VerticesSizeType numOfVertices = num_vertices(g);
1.105 + const Vertex p(get(parentMap, n));
1.106 + Vertex s(p);
1.107 +
1.108 + // 1. Calculate the semidominator of n,
1.109 + // based on the semidominator thm.
1.110 + // * Semidominator thm. : To find the semidominator of a node n,
1.111 + // consider all predecessors v of n in the CFG (Control Flow Graph).
1.112 + // - If v is a proper ancestor of n in the spanning tree
1.113 + // (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n)
1.114 + // - If v is a non-ancestor of n (so dfnum(v) > dfnum(n))
1.115 + // then for each u that is an ancestor of v (or u = v),
1.116 + // Let semi(u) be a candidate for semi(n)
1.117 + // of all these candidates, the one with lowest dfnum is
1.118 + // the semidominator of n.
1.119 +
1.120 + // For each predecessor of n
1.121 + typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
1.122 + for (tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr)
1.123 + {
1.124 + const Vertex v = source(*inItr, g);
1.125 + // To deal with unreachable nodes
1.126 + if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices)
1.127 + continue;
1.128 +
1.129 + Vertex s2;
1.130 + if (get(dfnumMap, v) <= get(dfnumMap, n))
1.131 + s2 = v;
1.132 + else
1.133 + s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap));
1.134 +
1.135 + if (get(dfnumMap, s2) < get(dfnumMap, s))
1.136 + s = s2;
1.137 + }
1.138 + put(semiMap_, n, s);
1.139 +
1.140 + // 2. Calculation of n's dominator is deferred until
1.141 + // the path from s to n has been linked into the forest
1.142 + get(bucketMap_, s).push_back(n);
1.143 + get(ancestorMap_, n) = p;
1.144 + get(bestMap_, n) = n;
1.145 +
1.146 + // 3. Now that the path from p to v has been linked into
1.147 + // the spanning forest, these lines calculate the dominator of v,
1.148 + // based on the dominator thm., or else defer the calculation
1.149 + // until y's dominator is known
1.150 + // * Dominator thm. : On the spanning-tree path below semi(n) and
1.151 + // above or including n, let y be the node
1.152 + // with the smallest-numbered semidominator. Then,
1.153 + //
1.154 + // idom(n) = semi(n) if semi(y)=semi(n) or
1.155 + // idom(y) if semi(y) != semi(n)
1.156 + typename std::deque<Vertex>::iterator buckItr;
1.157 + for (buckItr = get(bucketMap_, p).begin();
1.158 + buckItr != get(bucketMap_, p).end();
1.159 + ++buckItr)
1.160 + {
1.161 + const Vertex v(*buckItr);
1.162 + const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap));
1.163 + if (get(semiMap_, y) == get(semiMap_, v))
1.164 + put(domTreePredMap_, v, p);
1.165 + else
1.166 + put(samedomMap, v, y);
1.167 + }
1.168 +
1.169 + get(bucketMap_, p).clear();
1.170 + }
1.171 +
1.172 + protected :
1.173 +
1.174 + /**
1.175 + * Evaluate function in Tarjan's path compression
1.176 + */
1.177 + const Vertex
1.178 + ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap)
1.179 + {
1.180 + const Vertex a(get(ancestorMap_, v));
1.181 +
1.182 + if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex())
1.183 + {
1.184 + const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap));
1.185 +
1.186 + put(ancestorMap_, v, get(ancestorMap_, a));
1.187 +
1.188 + if (get(dfnumMap, get(semiMap_, b)) <
1.189 + get(dfnumMap, get(semiMap_, get(bestMap_, v))))
1.190 + put(bestMap_, v, b);
1.191 + }
1.192 +
1.193 + return get(bestMap_, v);
1.194 + }
1.195 +
1.196 + std::vector<Vertex> semi_, ancestor_, samedom_, best_;
1.197 + PredMap semiMap_, ancestorMap_, bestMap_;
1.198 + std::vector< std::deque<Vertex> > buckets_;
1.199 +
1.200 + iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator,
1.201 + IndexMap> bucketMap_;
1.202 +
1.203 + const Vertex& entry_;
1.204 + DomTreePredMap domTreePredMap_;
1.205 +
1.206 + public :
1.207 +
1.208 + PredMap samedomMap;
1.209 + };
1.210 +
1.211 + } // namespace detail
1.212 +
1.213 + /**
1.214 + * @brief Build dominator tree using Lengauer-Tarjan algorithm.
1.215 + * It takes O((V+E)log(V+E)) time.
1.216 + *
1.217 + * @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding
1.218 + * indexMap.
1.219 + * If dfs has already run before,
1.220 + * this function would be good for saving computations.
1.221 + * @pre Unreachable nodes must be masked as
1.222 + * graph_traits<Graph>::null_vertex in parentMap.
1.223 + * @pre Unreachable nodes must be masked as
1.224 + * (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap.
1.225 + *
1.226 + * @param domTreePredMap [out] : immediate dominator map (parent map
1.227 + * in dom. tree)
1.228 + *
1.229 + * @note reference Appel. p. 452~453. algorithm 19.9, 19.10.
1.230 + *
1.231 + * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis
1.232 + */
1.233 + template<class Graph, class IndexMap, class TimeMap, class PredMap,
1.234 + class VertexVector, class DomTreePredMap>
1.235 + void
1.236 + lengauer_tarjan_dominator_tree_without_dfs
1.237 + (const Graph& g,
1.238 + const typename graph_traits<Graph>::vertex_descriptor& entry,
1.239 + const IndexMap& indexMap,
1.240 + TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
1.241 + DomTreePredMap domTreePredMap)
1.242 + {
1.243 + // Typedefs and concept check
1.244 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.245 + typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
1.246 +
1.247 + function_requires< BidirectionalGraphConcept<Graph> >();
1.248 +
1.249 + const VerticesSizeType numOfVertices = num_vertices(g);
1.250 + if (numOfVertices == 0) return;
1.251 +
1.252 + // 1. Visit each vertex in reverse post order and calculate sdom.
1.253 + detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap>
1.254 + visitor(g, entry, domTreePredMap);
1.255 +
1.256 + VerticesSizeType i;
1.257 + for (i = 0; i < numOfVertices; ++i)
1.258 + {
1.259 + const Vertex u(verticesByDFNum[numOfVertices - 1 - i]);
1.260 + if (u != graph_traits<Graph>::null_vertex())
1.261 + visitor(u, dfnumMap, parentMap, g);
1.262 + }
1.263 +
1.264 + // 2. Now all the deferred dominator calculations,
1.265 + // based on the second clause of the dominator thm., are performed
1.266 + for (i = 0; i < numOfVertices; ++i)
1.267 + {
1.268 + const Vertex n(verticesByDFNum[i]);
1.269 +
1.270 + if (n == entry || n == graph_traits<Graph>::null_vertex())
1.271 + continue;
1.272 +
1.273 + Vertex u = get(visitor.samedomMap, n);
1.274 + if (u != graph_traits<Graph>::null_vertex())
1.275 + {
1.276 + put(domTreePredMap, n, get(domTreePredMap, u));
1.277 + }
1.278 + }
1.279 + }
1.280 +
1.281 + /**
1.282 + * Unlike lengauer_tarjan_dominator_tree_without_dfs,
1.283 + * dfs is run in this function and
1.284 + * the result is written to dfnumMap, parentMap, vertices.
1.285 + *
1.286 + * If the result of dfs required after this algorithm,
1.287 + * this function can eliminate the need of rerunning dfs.
1.288 + */
1.289 + template<class Graph, class IndexMap, class TimeMap, class PredMap,
1.290 + class VertexVector, class DomTreePredMap>
1.291 + void
1.292 + lengauer_tarjan_dominator_tree
1.293 + (const Graph& g,
1.294 + const typename graph_traits<Graph>::vertex_descriptor& entry,
1.295 + const IndexMap& indexMap,
1.296 + TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
1.297 + DomTreePredMap domTreePredMap)
1.298 + {
1.299 + // Typedefs and concept check
1.300 + typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
1.301 +
1.302 + function_requires< BidirectionalGraphConcept<Graph> >();
1.303 +
1.304 + // 1. Depth first visit
1.305 + const VerticesSizeType numOfVertices = num_vertices(g);
1.306 + if (numOfVertices == 0) return;
1.307 +
1.308 + VerticesSizeType time =
1.309 + (std::numeric_limits<VerticesSizeType>::max)();
1.310 + std::vector<default_color_type>
1.311 + colors(numOfVertices, color_traits<default_color_type>::white());
1.312 + depth_first_visit
1.313 + (g, entry,
1.314 + make_dfs_visitor
1.315 + (make_pair(record_predecessors(parentMap, on_tree_edge()),
1.316 + detail::stamp_times_with_vertex_vector
1.317 + (dfnumMap, verticesByDFNum, time, on_discover_vertex()))),
1.318 + make_iterator_property_map(colors.begin(), indexMap));
1.319 +
1.320 + // 2. Run main algorithm.
1.321 + lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap,
1.322 + parentMap, verticesByDFNum,
1.323 + domTreePredMap);
1.324 + }
1.325 +
1.326 + /**
1.327 + * Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum
1.328 + * internally.
1.329 + * If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum),
1.330 + * this function would be more convenient one.
1.331 + */
1.332 + template<class Graph, class DomTreePredMap>
1.333 + void
1.334 + lengauer_tarjan_dominator_tree
1.335 + (const Graph& g,
1.336 + const typename graph_traits<Graph>::vertex_descriptor& entry,
1.337 + DomTreePredMap domTreePredMap)
1.338 + {
1.339 + // typedefs
1.340 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.341 + typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
1.342 + typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
1.343 + typedef
1.344 + iterator_property_map<typename std::vector<VerticesSizeType>::iterator,
1.345 + IndexMap> TimeMap;
1.346 + typedef
1.347 + iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap>
1.348 + PredMap;
1.349 +
1.350 + // Make property maps
1.351 + const VerticesSizeType numOfVertices = num_vertices(g);
1.352 + if (numOfVertices == 0) return;
1.353 +
1.354 + const IndexMap indexMap = get(vertex_index, g);
1.355 +
1.356 + std::vector<VerticesSizeType> dfnum(numOfVertices, 0);
1.357 + TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));
1.358 +
1.359 + std::vector<Vertex> parent(numOfVertices,
1.360 + graph_traits<Graph>::null_vertex());
1.361 + PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));
1.362 +
1.363 + std::vector<Vertex> verticesByDFNum(parent);
1.364 +
1.365 + // Run main algorithm
1.366 + lengauer_tarjan_dominator_tree(g, entry,
1.367 + indexMap, dfnumMap, parentMap,
1.368 + verticesByDFNum, domTreePredMap);
1.369 + }
1.370 +
1.371 + /**
1.372 + * Muchnick. p. 182, 184
1.373 + *
1.374 + * using iterative bit vector analysis
1.375 + */
1.376 + template<class Graph, class IndexMap, class DomTreePredMap>
1.377 + void
1.378 + iterative_bit_vector_dominator_tree
1.379 + (const Graph& g,
1.380 + const typename graph_traits<Graph>::vertex_descriptor& entry,
1.381 + const IndexMap& indexMap,
1.382 + DomTreePredMap domTreePredMap)
1.383 + {
1.384 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.385 + typedef typename graph_traits<Graph>::vertex_iterator vertexItr;
1.386 + typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
1.387 + typedef
1.388 + iterator_property_map<typename std::vector< std::set<Vertex> >::iterator,
1.389 + IndexMap> vertexSetMap;
1.390 +
1.391 + function_requires<BidirectionalGraphConcept<Graph> >();
1.392 +
1.393 + // 1. Finding dominator
1.394 + // 1.1. Initialize
1.395 + const VerticesSizeType numOfVertices = num_vertices(g);
1.396 + if (numOfVertices == 0) return;
1.397 +
1.398 + vertexItr vi, viend;
1.399 + tie(vi, viend) = vertices(g);
1.400 + const std::set<Vertex> N(vi, viend);
1.401 +
1.402 + bool change = true;
1.403 +
1.404 + std::vector< std::set<Vertex> > dom(numOfVertices, N);
1.405 + vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap));
1.406 + get(domMap, entry).clear();
1.407 + get(domMap, entry).insert(entry);
1.408 +
1.409 + while (change)
1.410 + {
1.411 + change = false;
1.412 + for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
1.413 + {
1.414 + if (*vi == entry) continue;
1.415 +
1.416 + std::set<Vertex> T(N);
1.417 +
1.418 + typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
1.419 + for (tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr)
1.420 + {
1.421 + const Vertex p = source(*inItr, g);
1.422 +
1.423 + std::set<Vertex> tempSet;
1.424 + std::set_intersection(T.begin(), T.end(),
1.425 + get(domMap, p).begin(),
1.426 + get(domMap, p).end(),
1.427 + std::inserter(tempSet, tempSet.begin()));
1.428 + T.swap(tempSet);
1.429 + }
1.430 +
1.431 + T.insert(*vi);
1.432 + if (T != get(domMap, *vi))
1.433 + {
1.434 + change = true;
1.435 + get(domMap, *vi).swap(T);
1.436 + }
1.437 + } // end of for (tie(vi, viend) = vertices(g)
1.438 + } // end of while(change)
1.439 +
1.440 + // 2. Build dominator tree
1.441 + for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
1.442 + get(domMap, *vi).erase(*vi);
1.443 +
1.444 + Graph domTree(numOfVertices);
1.445 +
1.446 + for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
1.447 + {
1.448 + if (*vi == entry) continue;
1.449 +
1.450 + // We have to iterate through copied dominator set
1.451 + const std::set<Vertex> tempSet(get(domMap, *vi));
1.452 + typename std::set<Vertex>::const_iterator s;
1.453 + for (s = tempSet.begin(); s != tempSet.end(); ++s)
1.454 + {
1.455 + typename std::set<Vertex>::iterator t;
1.456 + for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); )
1.457 + {
1.458 + typename std::set<Vertex>::iterator old_t = t;
1.459 + ++t; // Done early because t may become invalid
1.460 + if (*old_t == *s) continue;
1.461 + if (get(domMap, *s).find(*old_t) != get(domMap, *s).end())
1.462 + get(domMap, *vi).erase(old_t);
1.463 + }
1.464 + }
1.465 + }
1.466 +
1.467 + for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
1.468 + {
1.469 + if (*vi != entry && get(domMap, *vi).size() == 1)
1.470 + {
1.471 + Vertex temp = *get(domMap, *vi).begin();
1.472 + put(domTreePredMap, *vi, temp);
1.473 + }
1.474 + }
1.475 + }
1.476 +
1.477 + template<class Graph, class DomTreePredMap>
1.478 + void
1.479 + iterative_bit_vector_dominator_tree
1.480 + (const Graph& g,
1.481 + const typename graph_traits<Graph>::vertex_descriptor& entry,
1.482 + DomTreePredMap domTreePredMap)
1.483 + {
1.484 + typename property_map<Graph, vertex_index_t>::const_type
1.485 + indexMap = get(vertex_index, g);
1.486 +
1.487 + iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap);
1.488 + }
1.489 +} // namespace boost
1.490 +
1.491 +#endif // BOOST_GRAPH_DOMINATOR_HPP