// Dominator tree computation
-namespace boost {
- namespace detail {
+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>
+ 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 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_;
+ 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)
+ 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);
+ return time_stamper_with_vertex_vector< TimeMap, VertexVector, TimeT,
+ Tag >(timeMap, v, t);
}
- template<class Graph, class IndexMap, class TimeMap, class PredMap,
- class DomTreePredMap>
+ 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 indexMap [in] the vertex index map for g
- * @param domTreePredMap [out] the immediate dominator map
- * (parent map in dominator tree)
- */
- dominator_visitor(const Graph& g, const Vertex& entry,
- const IndexMap& indexMap,
- 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(),
- indexMap)),
- ancestorMap_(make_iterator_property_map(ancestor_.begin(),
- indexMap)),
- bestMap_(make_iterator_property_map(best_.begin(),
- indexMap)),
- buckets_(num_vertices(g)),
- bucketMap_(make_iterator_property_map(buckets_.begin(),
- indexMap)),
- entry_(entry),
- domTreePredMap_(domTreePredMap),
- numOfVertices_(num_vertices(g)),
- samedomMap(make_iterator_property_map(samedom_.begin(),
- indexMap))
- {
- }
-
- 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;
+ 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 indexMap [in] the vertex index map for g
+ * @param domTreePredMap [out] the immediate dominator map
+ * (parent map in dominator tree)
+ */
+ dominator_visitor(const Graph& g, const Vertex& entry,
+ const IndexMap& indexMap, 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(), indexMap))
+ , ancestorMap_(make_iterator_property_map(ancestor_.begin(), indexMap))
+ , bestMap_(make_iterator_property_map(best_.begin(), indexMap))
+ , buckets_(num_vertices(g))
+ , bucketMap_(make_iterator_property_map(buckets_.begin(), indexMap))
+ , entry_(entry)
+ , domTreePredMap_(domTreePredMap)
+ , numOfVertices_(num_vertices(g))
+ , samedomMap(make_iterator_property_map(samedom_.begin(), indexMap))
+ {
+ }
+
+ 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)
- {
+} // 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;
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
+ typedef typename graph_traits< Graph >::vertices_size_type VerticesSizeType;
- BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
+ BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept< Graph >));
const VerticesSizeType numOfVertices = num_vertices(g);
- if (numOfVertices == 0) return;
+ 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, indexMap, domTreePredMap);
+ detail::dominator_visitor< Graph, IndexMap, TimeMap, PredMap,
+ DomTreePredMap >
+ visitor(g, entry, indexMap, 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);
- }
+ 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;
+ if (n == entry || n == graph_traits< Graph >::null_vertex())
+ continue;
Vertex u = get(visitor.samedomMap, n);
- if (u != graph_traits<Graph>::null_vertex())
- {
+ 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)
- {
+ }
+ }
+}
+
+/**
+ * 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;
+ typedef typename graph_traits< Graph >::vertices_size_type VerticesSizeType;
- BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
+ 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));
+ 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)
- {
+ 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;
+ 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;
+ if (numOfVertices == 0)
+ return;
const IndexMap indexMap = get(vertex_index, g);
- std::vector<VerticesSizeType> dfnum(numOfVertices, 0);
+ 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());
+ std::vector< Vertex > parent(
+ numOfVertices, graph_traits< Graph >::null_vertex());
PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));
- std::vector<Vertex> verticesByDFNum(parent);
+ 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> ));
+ 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;
+ if (numOfVertices == 0)
+ return;
vertexItr vi, viend;
boost::tie(vi, viend) = vertices(g);
- const std::set<Vertex> N(vi, viend);
+ const std::set< Vertex > N(vi, viend);
bool change = true;
- std::vector< std::set<Vertex> > dom(numOfVertices, N);
+ 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;
+ {
+ if (*vi == entry)
+ continue;
- std::set<Vertex> T(N);
+ 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)
- {
+ 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< Vertex > tempSet;
std::set_intersection(T.begin(), T.end(),
- get(domMap, p).begin(),
- get(domMap, p).end(),
- std::inserter(tempSet, tempSet.begin()));
+ 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)
+ }
+ } // 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);
+ get(domMap, *vi).erase(*vi);
Graph domTree(numOfVertices);
for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
- {
- if (*vi == entry) continue;
+ {
+ 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;
+ 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;
+ {
+ 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);
- }
- }
- }
+ 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);
+ }
+ }
+}
+
+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
projects / ceph.git / blobdiff