boost/graph/dominator_tree.hpp

//=======================================================================
// 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 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)
{
    // 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, 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);
    }

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