FCL/sf/os/ossrv: comparison ossrv_pub/boost_apis/boost/graph/dominator

equal deleted inserted replaced

--1:000000000000
+:e4d67989cc36
+//=======================================================================
+// Copyright (C) 2005 Jong Soo 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)
+//=======================================================================
+// Dominator tree computation
+#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>
+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),
+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 VerticesSizeType numOfVertices = num_vertices(g);
+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 (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_;
+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;
+function_requires< 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;
+function_requires< 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;
+function_requires<BidirectionalGraphConcept<Graph> >();
+// 1. Finding dominator
+// 1.1. Initialize
+const VerticesSizeType numOfVertices = num_vertices(g);
+if (numOfVertices == 0) return;
+vertexItr vi, viend;
+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 (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 (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 (tie(vi, viend) = vertices(g)
+} // end of while(change)
+// 2. Build dominator tree
+for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
+get(domMap, *vi).erase(*vi);
+Graph domTree(numOfVertices);
+for (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 (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