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