boost/graph/dominator_tree.hpp
//======================================================================= // Copyright (C) 2005-2009 Jongsoo Park <jongsoo.park -at- gmail.com> // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #ifndef BOOST_GRAPH_DOMINATOR_HPP #define BOOST_GRAPH_DOMINATOR_HPP #include <boost/config.hpp> #include <deque> #include <set> #include <boost/graph/depth_first_search.hpp> #include <boost/concept/assert.hpp> // Dominator tree computation namespace boost { namespace detail { /** * An extended time_stamper which also records vertices for each dfs number */ template<class TimeMap, class VertexVector, class TimeT, class Tag> class time_stamper_with_vertex_vector : public base_visitor< time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> > { public : typedef Tag event_filter; time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t) : timeStamper_(timeMap, t), v_(v) { } template<class Graph> void operator()(const typename property_traits<TimeMap>::key_type& v, const Graph& g) { timeStamper_(v, g); v_[timeStamper_.m_time] = v; } private : time_stamper<TimeMap, TimeT, Tag> timeStamper_; VertexVector& v_; }; /** * A convenient way to create a time_stamper_with_vertex_vector */ template<class TimeMap, class VertexVector, class TimeT, class Tag> time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t, Tag) { return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag>(timeMap, v, t); } template<class Graph, class IndexMap, class TimeMap, class PredMap, class DomTreePredMap> class dominator_visitor { typedef typename graph_traits<Graph>::vertex_descriptor Vertex; typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; public : /** * @param g [in] the target graph of the dominator tree * @param entry [in] the entry node of g * @param domTreePredMap [out] the immediate dominator map * (parent map in dominator tree) */ dominator_visitor(const Graph& g, const Vertex& entry, DomTreePredMap domTreePredMap) : semi_(num_vertices(g)), ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()), samedom_(ancestor_), best_(semi_), semiMap_(make_iterator_property_map(semi_.begin(), get(vertex_index, g))), ancestorMap_(make_iterator_property_map(ancestor_.begin(), get(vertex_index, g))), bestMap_(make_iterator_property_map(best_.begin(), get(vertex_index, g))), buckets_(num_vertices(g)), bucketMap_(make_iterator_property_map(buckets_.begin(), get(vertex_index, g))), entry_(entry), domTreePredMap_(domTreePredMap), numOfVertices_(num_vertices(g)), samedomMap(make_iterator_property_map(samedom_.begin(), get(vertex_index, g))) { } void operator()(const Vertex& n, const TimeMap& dfnumMap, const PredMap& parentMap, const Graph& g) { if (n == entry_) return; const Vertex p(get(parentMap, n)); Vertex s(p); // 1. Calculate the semidominator of n, // based on the semidominator thm. // * Semidominator thm. : To find the semidominator of a node n, // consider all predecessors v of n in the CFG (Control Flow Graph). // - If v is a proper ancestor of n in the spanning tree // (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n) // - If v is a non-ancestor of n (so dfnum(v) > dfnum(n)) // then for each u that is an ancestor of v (or u = v), // Let semi(u) be a candidate for semi(n) // of all these candidates, the one with lowest dfnum is // the semidominator of n. // For each predecessor of n typename graph_traits<Graph>::in_edge_iterator inItr, inEnd; for (boost::tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr) { const Vertex v = source(*inItr, g); // To deal with unreachable nodes if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices_) continue; Vertex s2; if (get(dfnumMap, v) <= get(dfnumMap, n)) s2 = v; else s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap)); if (get(dfnumMap, s2) < get(dfnumMap, s)) s = s2; } put(semiMap_, n, s); // 2. Calculation of n's dominator is deferred until // the path from s to n has been linked into the forest get(bucketMap_, s).push_back(n); get(ancestorMap_, n) = p; get(bestMap_, n) = n; // 3. Now that the path from p to v has been linked into // the spanning forest, these lines calculate the dominator of v, // based on the dominator thm., or else defer the calculation // until y's dominator is known // * Dominator thm. : On the spanning-tree path below semi(n) and // above or including n, let y be the node // with the smallest-numbered semidominator. Then, // // idom(n) = semi(n) if semi(y)=semi(n) or // idom(y) if semi(y) != semi(n) typename std::deque<Vertex>::iterator buckItr; for (buckItr = get(bucketMap_, p).begin(); buckItr != get(bucketMap_, p).end(); ++buckItr) { const Vertex v(*buckItr); const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap)); if (get(semiMap_, y) == get(semiMap_, v)) put(domTreePredMap_, v, p); else put(samedomMap, v, y); } get(bucketMap_, p).clear(); } protected : /** * Evaluate function in Tarjan's path compression */ const Vertex ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap) { const Vertex a(get(ancestorMap_, v)); if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex()) { const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap)); put(ancestorMap_, v, get(ancestorMap_, a)); if (get(dfnumMap, get(semiMap_, b)) < get(dfnumMap, get(semiMap_, get(bestMap_, v)))) put(bestMap_, v, b); } return get(bestMap_, v); } std::vector<Vertex> semi_, ancestor_, samedom_, best_; PredMap semiMap_, ancestorMap_, bestMap_; std::vector< std::deque<Vertex> > buckets_; iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator, IndexMap> bucketMap_; const Vertex& entry_; DomTreePredMap domTreePredMap_; const VerticesSizeType numOfVertices_; public : PredMap samedomMap; }; } // namespace detail /** * @brief Build dominator tree using Lengauer-Tarjan algorithm. * It takes O((V+E)log(V+E)) time. * * @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding * indexMap. * If dfs has already run before, * this function would be good for saving computations. * @pre Unreachable nodes must be masked as * graph_traits<Graph>::null_vertex in parentMap. * @pre Unreachable nodes must be masked as * (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap. * * @param domTreePredMap [out] : immediate dominator map (parent map * in dom. tree) * * @note reference Appel. p. 452~453. algorithm 19.9, 19.10. * * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis */ template<class Graph, class IndexMap, class TimeMap, class PredMap, class VertexVector, class DomTreePredMap> void lengauer_tarjan_dominator_tree_without_dfs (const Graph& g, const typename graph_traits<Graph>::vertex_descriptor& entry, const IndexMap& /*indexMap*/, TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, DomTreePredMap domTreePredMap) { // Typedefs and concept check typedef typename graph_traits<Graph>::vertex_descriptor Vertex; typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); const VerticesSizeType numOfVertices = num_vertices(g); if (numOfVertices == 0) return; // 1. Visit each vertex in reverse post order and calculate sdom. detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap> visitor(g, entry, domTreePredMap); VerticesSizeType i; for (i = 0; i < numOfVertices; ++i) { const Vertex u(verticesByDFNum[numOfVertices - 1 - i]); if (u != graph_traits<Graph>::null_vertex()) visitor(u, dfnumMap, parentMap, g); } // 2. Now all the deferred dominator calculations, // based on the second clause of the dominator thm., are performed for (i = 0; i < numOfVertices; ++i) { const Vertex n(verticesByDFNum[i]); if (n == entry || n == graph_traits<Graph>::null_vertex()) continue; Vertex u = get(visitor.samedomMap, n); if (u != graph_traits<Graph>::null_vertex()) { put(domTreePredMap, n, get(domTreePredMap, u)); } } } /** * Unlike lengauer_tarjan_dominator_tree_without_dfs, * dfs is run in this function and * the result is written to dfnumMap, parentMap, vertices. * * If the result of dfs required after this algorithm, * this function can eliminate the need of rerunning dfs. */ template<class Graph, class IndexMap, class TimeMap, class PredMap, class VertexVector, class DomTreePredMap> void lengauer_tarjan_dominator_tree (const Graph& g, const typename graph_traits<Graph>::vertex_descriptor& entry, const IndexMap& indexMap, TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, DomTreePredMap domTreePredMap) { // Typedefs and concept check typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); // 1. Depth first visit const VerticesSizeType numOfVertices = num_vertices(g); if (numOfVertices == 0) return; VerticesSizeType time = (std::numeric_limits<VerticesSizeType>::max)(); std::vector<default_color_type> colors(numOfVertices, color_traits<default_color_type>::white()); depth_first_visit (g, entry, make_dfs_visitor (make_pair(record_predecessors(parentMap, on_tree_edge()), detail::stamp_times_with_vertex_vector (dfnumMap, verticesByDFNum, time, on_discover_vertex()))), make_iterator_property_map(colors.begin(), indexMap)); // 2. Run main algorithm. lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap, parentMap, verticesByDFNum, domTreePredMap); } /** * Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum * internally. * If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum), * this function would be more convenient one. */ template<class Graph, class DomTreePredMap> void lengauer_tarjan_dominator_tree (const Graph& g, const typename graph_traits<Graph>::vertex_descriptor& entry, DomTreePredMap domTreePredMap) { // typedefs typedef typename graph_traits<Graph>::vertex_descriptor Vertex; typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap; typedef iterator_property_map<typename std::vector<VerticesSizeType>::iterator, IndexMap> TimeMap; typedef iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap> PredMap; // Make property maps const VerticesSizeType numOfVertices = num_vertices(g); if (numOfVertices == 0) return; const IndexMap indexMap = get(vertex_index, g); std::vector<VerticesSizeType> dfnum(numOfVertices, 0); TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap)); std::vector<Vertex> parent(numOfVertices, graph_traits<Graph>::null_vertex()); PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap)); std::vector<Vertex> verticesByDFNum(parent); // Run main algorithm lengauer_tarjan_dominator_tree(g, entry, indexMap, dfnumMap, parentMap, verticesByDFNum, domTreePredMap); } /** * Muchnick. p. 182, 184 * * using iterative bit vector analysis */ template<class Graph, class IndexMap, class DomTreePredMap> void iterative_bit_vector_dominator_tree (const Graph& g, const typename graph_traits<Graph>::vertex_descriptor& entry, const IndexMap& indexMap, DomTreePredMap domTreePredMap) { typedef typename graph_traits<Graph>::vertex_descriptor Vertex; typedef typename graph_traits<Graph>::vertex_iterator vertexItr; typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; typedef iterator_property_map<typename std::vector< std::set<Vertex> >::iterator, IndexMap> vertexSetMap; BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); // 1. Finding dominator // 1.1. Initialize const VerticesSizeType numOfVertices = num_vertices(g); if (numOfVertices == 0) return; vertexItr vi, viend; boost::tie(vi, viend) = vertices(g); const std::set<Vertex> N(vi, viend); bool change = true; std::vector< std::set<Vertex> > dom(numOfVertices, N); vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap)); get(domMap, entry).clear(); get(domMap, entry).insert(entry); while (change) { change = false; for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) { if (*vi == entry) continue; std::set<Vertex> T(N); typename graph_traits<Graph>::in_edge_iterator inItr, inEnd; for (boost::tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr) { const Vertex p = source(*inItr, g); std::set<Vertex> tempSet; std::set_intersection(T.begin(), T.end(), get(domMap, p).begin(), get(domMap, p).end(), std::inserter(tempSet, tempSet.begin())); T.swap(tempSet); } T.insert(*vi); if (T != get(domMap, *vi)) { change = true; get(domMap, *vi).swap(T); } } // end of for (boost::tie(vi, viend) = vertices(g) } // end of while(change) // 2. Build dominator tree for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) get(domMap, *vi).erase(*vi); Graph domTree(numOfVertices); for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) { if (*vi == entry) continue; // We have to iterate through copied dominator set const std::set<Vertex> tempSet(get(domMap, *vi)); typename std::set<Vertex>::const_iterator s; for (s = tempSet.begin(); s != tempSet.end(); ++s) { typename std::set<Vertex>::iterator t; for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); ) { typename std::set<Vertex>::iterator old_t = t; ++t; // Done early because t may become invalid if (*old_t == *s) continue; if (get(domMap, *s).find(*old_t) != get(domMap, *s).end()) get(domMap, *vi).erase(old_t); } } } for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) { if (*vi != entry && get(domMap, *vi).size() == 1) { Vertex temp = *get(domMap, *vi).begin(); put(domTreePredMap, *vi, temp); } } } template<class Graph, class DomTreePredMap> void iterative_bit_vector_dominator_tree (const Graph& g, const typename graph_traits<Graph>::vertex_descriptor& entry, DomTreePredMap domTreePredMap) { typename property_map<Graph, vertex_index_t>::const_type indexMap = get(vertex_index, g); iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap); } } // namespace boost #endif // BOOST_GRAPH_DOMINATOR_HPP