comparison DEPENDENCIES/generic/include/boost/graph/dominator_tree.hpp @ 16:2665513ce2d3

Add boost headers

+//=======================================================================
+// 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