dominator_tree.hpp

support vector clustering for vc++

//=======================================================================
// 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> >();