dominator_tree.hpp

support vector clustering for vc++

    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