Boost C++ Libraries

boost/graph/transitive_closure.hpp

// Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
// Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
// 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)

// NOTE: this final is generated by libs/graph/doc/transitive_closure.w

#ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
#define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP

#include <vector>
#include <algorithm> // for std::min and std::max
#include <functional>
#include <boost/config.hpp>
#include <boost/bind/bind.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/concept/assert.hpp>

namespace boost
{

namespace detail
{
    inline void union_successor_sets(const std::vector< std::size_t >& s1,
        const std::vector< std::size_t >& s2, std::vector< std::size_t >& s3)
    {
        BOOST_USING_STD_MIN();
        for (std::size_t k = 0; k < s1.size(); ++k)
            s3[k] = min BOOST_PREVENT_MACRO_SUBSTITUTION(s1[k], s2[k]);
    }
} // namespace detail

namespace detail
{
    template < typename TheContainer, typename ST = std::size_t,
        typename VT = typename TheContainer::value_type >
    struct subscript_t
    {
        typedef ST argument_type;
        typedef VT& result_type;

        subscript_t(TheContainer& c) : container(&c) {}
        VT& operator()(const ST& i) const { return (*container)[i]; }

    protected:
        TheContainer* container;
    };
    template < typename TheContainer >
    subscript_t< TheContainer > subscript(TheContainer& c)
    {
        return subscript_t< TheContainer >(c);
    }
} // namespace detail

template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap,
    typename VertexIndexMap >
void transitive_closure(const Graph& g, GraphTC& tc,
    G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
{
    if (num_vertices(g) == 0)
        return;
    typedef typename graph_traits< Graph >::vertex_descriptor vertex;
    typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator;
    typedef typename property_traits< VertexIndexMap >::value_type size_type;
    typedef
        typename graph_traits< Graph >::adjacency_iterator adjacency_iterator;

    BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
    BOOST_CONCEPT_ASSERT((AdjacencyGraphConcept< Graph >));
    BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept< GraphTC >));
    BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< GraphTC >));
    BOOST_CONCEPT_ASSERT(
        (ReadablePropertyMapConcept< VertexIndexMap, vertex >));

    typedef size_type cg_vertex;
    std::vector< cg_vertex > component_number_vec(num_vertices(g));
    iterator_property_map< cg_vertex*, VertexIndexMap, cg_vertex, cg_vertex& >
        component_number(&component_number_vec[0], index_map);

    const cg_vertex num_scc
        = strong_components(g, component_number, vertex_index_map(index_map));

    std::vector< std::vector< vertex > > components;
    build_component_lists(g, num_scc, component_number, components);

    typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS >
        CG_t;
    CG_t CG(num_scc);
    for (cg_vertex s = 0; s < components.size(); ++s)
    {
        std::vector< cg_vertex > adj;
        for (size_type i = 0; i < components[s].size(); ++i)
        {
            vertex u = components[s][i];
            adjacency_iterator v, v_end;
            for (boost::tie(v, v_end) = adjacent_vertices(u, g); v != v_end;
                 ++v)
            {
                cg_vertex t = component_number[*v];
                if (s != t) // Avoid loops in the condensation graph
                    adj.push_back(t);
            }
        }
        std::sort(adj.begin(), adj.end());
        const typename std::vector< cg_vertex >::iterator di
            = std::unique(adj.begin(), adj.end());

        for (typename std::vector< cg_vertex >::const_iterator i = adj.begin();
             i != di; ++i)
        {
            add_edge(s, *i, CG);
        }
    }

    std::vector< cg_vertex > topo_order;
    std::vector< cg_vertex > topo_number(num_vertices(CG));
    topological_sort(CG, std::back_inserter(topo_order),
        vertex_index_map(identity_property_map()));
    std::reverse(topo_order.begin(), topo_order.end());
    size_type n = 0;
    for (typename std::vector< cg_vertex >::iterator iter = topo_order.begin();
         iter != topo_order.end(); ++iter)
        topo_number[*iter] = n++;

    std::vector< std::vector< cg_vertex > > CG_vec(num_vertices(CG));
    for (size_type i = 0; i < num_vertices(CG); ++i)
    {
        using namespace boost::placeholders;

        typedef typename boost::graph_traits< CG_t >::adjacency_iterator
            cg_adj_iter;
        std::pair< cg_adj_iter, cg_adj_iter > pr = adjacent_vertices(i, CG);
        CG_vec[i].assign(pr.first, pr.second);
        std::sort(CG_vec[i].begin(), CG_vec[i].end(),
            boost::bind(std::less< cg_vertex >(),
                boost::bind(detail::subscript(topo_number), _1),
                boost::bind(detail::subscript(topo_number), _2)));
    }

    std::vector< std::vector< cg_vertex > > chains;
    {
        std::vector< cg_vertex > in_a_chain(CG_vec.size());
        for (typename std::vector< cg_vertex >::iterator i = topo_order.begin();
             i != topo_order.end(); ++i)
        {
            cg_vertex v = *i;
            if (!in_a_chain[v])
            {
                chains.resize(chains.size() + 1);
                std::vector< cg_vertex >& chain = chains.back();
                for (;;)
                {
                    chain.push_back(v);
                    in_a_chain[v] = true;

                    typename std::vector< cg_vertex >::const_iterator next
                    #ifdef __cpp_lib_not_fn
                        = std::find_if(CG_vec[v].begin(), CG_vec[v].end(),
                                       std::not_fn(detail::subscript(in_a_chain)));
                    #else
                        = std::find_if(CG_vec[v].begin(), CG_vec[v].end(),
                                       std::not1(detail::subscript(in_a_chain)));
                    #endif

                    if (next != CG_vec[v].end())
                        v = *next;
                    else
                        break; // end of chain, dead-end
                }
            }
        }
    }
    std::vector< size_type > chain_number(CG_vec.size());
    std::vector< size_type > pos_in_chain(CG_vec.size());
    for (size_type i = 0; i < chains.size(); ++i)
        for (size_type j = 0; j < chains[i].size(); ++j)
        {
            cg_vertex v = chains[i][j];
            chain_number[v] = i;
            pos_in_chain[v] = j;
        }

    cg_vertex inf = (std::numeric_limits< cg_vertex >::max)();
    std::vector< std::vector< cg_vertex > > successors(
        CG_vec.size(), std::vector< cg_vertex >(chains.size(), inf));
    for (typename std::vector< cg_vertex >::reverse_iterator i
         = topo_order.rbegin();
         i != topo_order.rend(); ++i)
    {
        cg_vertex u = *i;
        typename std::vector< cg_vertex >::const_iterator adj, adj_last;
        for (adj = CG_vec[u].begin(), adj_last = CG_vec[u].end();
             adj != adj_last; ++adj)
        {
            cg_vertex v = *adj;
            if (topo_number[v] < successors[u][chain_number[v]])
            {
                // Succ(u) = Succ(u) U Succ(v)
                detail::union_successor_sets(
                    successors[u], successors[v], successors[u]);
                // Succ(u) = Succ(u) U {v}
                successors[u][chain_number[v]] = topo_number[v];
            }
        }
    }

    for (size_type i = 0; i < CG_vec.size(); ++i)
        CG_vec[i].clear();
    for (size_type i = 0; i < CG_vec.size(); ++i)
        for (size_type j = 0; j < chains.size(); ++j)
        {
            size_type topo_num = successors[i][j];
            if (topo_num < inf)
            {
                cg_vertex v = topo_order[topo_num];
                for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
                    CG_vec[i].push_back(chains[j][k]);
            }
        }

    // Add vertices to the transitive closure graph
    {
        vertex_iterator i, i_end;
        for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
            g_to_tc_map[*i] = add_vertex(tc);
    }
    // Add edges between all the vertices in two adjacent SCCs
    typename std::vector< std::vector< cg_vertex > >::const_iterator si, si_end;
    for (si = CG_vec.begin(), si_end = CG_vec.end(); si != si_end; ++si)
    {
        cg_vertex s = si - CG_vec.begin();
        typename std::vector< cg_vertex >::const_iterator i, i_end;
        for (i = CG_vec[s].begin(), i_end = CG_vec[s].end(); i != i_end; ++i)
        {
            cg_vertex t = *i;
            for (size_type k = 0; k < components[s].size(); ++k)
                for (size_type l = 0; l < components[t].size(); ++l)
                    add_edge(g_to_tc_map[components[s][k]],
                        g_to_tc_map[components[t][l]], tc);
        }
    }
    // Add edges connecting all vertices in a SCC
    for (size_type i = 0; i < components.size(); ++i)
        if (components[i].size() > 1)
            for (size_type k = 0; k < components[i].size(); ++k)
                for (size_type l = 0; l < components[i].size(); ++l)
                {
                    vertex u = components[i][k], v = components[i][l];
                    add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
                }

    // Find loopbacks in the original graph.
    // Need to add it to transitive closure.
    {
        vertex_iterator i, i_end;
        for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
        {
            adjacency_iterator ab, ae;
            for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
            {
                if (*ab == *i)
                    if (components[component_number[*i]].size() == 1)
                        add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
            }
        }
    }
}

template < typename Graph, typename GraphTC >
void transitive_closure(const Graph& g, GraphTC& tc)
{
    if (num_vertices(g) == 0)
        return;
    typedef typename property_map< Graph, vertex_index_t >::const_type
        VertexIndexMap;
    VertexIndexMap index_map = get(vertex_index, g);

    typedef typename graph_traits< GraphTC >::vertex_descriptor tc_vertex;
    std::vector< tc_vertex > to_tc_vec(num_vertices(g));
    iterator_property_map< tc_vertex*, VertexIndexMap, tc_vertex, tc_vertex& >
        g_to_tc_map(&to_tc_vec[0], index_map);

    transitive_closure(g, tc, g_to_tc_map, index_map);
}

namespace detail
{
    template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap,
        typename VertexIndexMap >
    void transitive_closure_dispatch(const Graph& g, GraphTC& tc,
        G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
    {
        typedef typename graph_traits< GraphTC >::vertex_descriptor tc_vertex;
        typename std::vector< tc_vertex >::size_type n
            = is_default_param(g_to_tc_map) ? num_vertices(g) : 1;
        std::vector< tc_vertex > to_tc_vec(n);

        transitive_closure(g, tc,
            choose_param(g_to_tc_map,
                make_iterator_property_map(
                    to_tc_vec.begin(), index_map, to_tc_vec[0])),
            index_map);
    }
} // namespace detail

template < typename Graph, typename GraphTC, typename P, typename T,
    typename R >
void transitive_closure(
    const Graph& g, GraphTC& tc, const bgl_named_params< P, T, R >& params)
{
    if (num_vertices(g) == 0)
        return;
    detail::transitive_closure_dispatch(g, tc,
        get_param(params, orig_to_copy_t()),
        choose_const_pmap(get_param(params, vertex_index), g, vertex_index));
}

template < typename G > void warshall_transitive_closure(G& g)
{
    typedef typename graph_traits< G >::vertex_iterator vertex_iterator;

    BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< G >));
    BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< G >));

    // Matrix form:
    // for k
    //  for i
    //    if A[i,k]
    //      for j
    //        A[i,j] = A[i,j] | A[k,j]
    vertex_iterator ki, ke, ii, ie, ji, je;
    for (boost::tie(ki, ke) = vertices(g); ki != ke; ++ki)
        for (boost::tie(ii, ie) = vertices(g); ii != ie; ++ii)
            if (edge(*ii, *ki, g).second)
                for (boost::tie(ji, je) = vertices(g); ji != je; ++ji)
                    if (!edge(*ii, *ji, g).second && edge(*ki, *ji, g).second)
                    {
                        add_edge(*ii, *ji, g);
                    }
}

template < typename G > void warren_transitive_closure(G& g)
{
    using namespace boost;
    typedef typename graph_traits< G >::vertex_iterator vertex_iterator;

    BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< G >));
    BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< G >));

    // Make sure second loop will work
    if (num_vertices(g) == 0)
        return;

    // for i = 2 to n
    //    for k = 1 to i - 1
    //      if A[i,k]
    //        for j = 1 to n
    //          A[i,j] = A[i,j] | A[k,j]

    vertex_iterator ic, ie, jc, je, kc, ke;
    for (boost::tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic)
        for (boost::tie(kc, ke) = vertices(g); *kc != *ic; ++kc)
            if (edge(*ic, *kc, g).second)
                for (boost::tie(jc, je) = vertices(g); jc != je; ++jc)
                    if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second)
                    {
                        add_edge(*ic, *jc, g);
                    }
    //  for i = 1 to n - 1
    //    for k = i + 1 to n
    //      if A[i,k]
    //        for j = 1 to n
    //          A[i,j] = A[i,j] | A[k,j]

    for (boost::tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic)
        for (kc = ic, ke = ie, ++kc; kc != ke; ++kc)
            if (edge(*ic, *kc, g).second)
                for (boost::tie(jc, je) = vertices(g); jc != je; ++jc)
                    if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second)
                    {
                        add_edge(*ic, *jc, g);
                    }
}

} // namespace boost

#endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP