// 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.hpp> | |
#include <boost/graph/vector_as_graph.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> | |
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:public std::unary_function < ST, VT > | |
{ | |
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 >::edge_descriptor edge; | |
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; | |
function_requires < VertexListGraphConcept < Graph > >(); | |
function_requires < AdjacencyGraphConcept < Graph > >(); | |
function_requires < VertexMutableGraphConcept < GraphTC > >(); | |
function_requires < EdgeMutableGraphConcept < GraphTC > >(); | |
function_requires < 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); | |
int 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 std::vector<std::vector<cg_vertex> > 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()); | |
typename std::vector<cg_vertex>::iterator di = | |
std::unique(adj.begin(), adj.end()); | |
if (di != adj.end()) | |
adj.erase(di, adj.end()); | |
CG[s] = adj; | |
} | |
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++; | |
for (size_type i = 0; i < num_vertices(CG); ++i) | |
std::sort(CG[i].begin(), CG[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(num_vertices(CG)); | |
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 graph_traits<CG_t>::adjacency_iterator adj_first, adj_last; | |
boost::tie(adj_first, adj_last) = adjacent_vertices(v, CG); | |
typename graph_traits<CG_t>::adjacency_iterator next | |
= std::find_if(adj_first, adj_last, | |
std::not1(detail::subscript(in_a_chain))); | |
if (next != adj_last) | |
v = *next; | |
else | |
break; // end of chain, dead-end | |
} | |
} | |
} | |
} | |
std::vector<size_type> chain_number(num_vertices(CG)); | |
std::vector<size_type> pos_in_chain(num_vertices(CG)); | |
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(num_vertices(CG), | |
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 graph_traits<CG_t>::adjacency_iterator adj, adj_last; | |
for (boost::tie(adj, adj_last) = adjacent_vertices(u, CG); | |
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.size(); ++i) | |
CG[i].clear(); | |
for (size_type i = 0; i < CG.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[i].push_back(chains[j][k]); | |
} | |
} | |
// Add vertices to the transitive closure graph | |
typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex; | |
{ | |
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 graph_traits<CG_t>::vertex_iterator si, si_end; | |
for (boost::tie(si, si_end) = vertices(CG); si != si_end; ++si) { | |
cg_vertex s = *si; | |
typename graph_traits<CG_t>::adjacency_iterator i, i_end; | |
for (boost::tie(i, i_end) = adjacent_vertices(s, CG); 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 > ¶ms) | |
{ | |
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_descriptor vertex; | |
typedef typename graph_traits < G >::vertex_iterator vertex_iterator; | |
function_requires < AdjacencyMatrixConcept < G > >(); | |
function_requires < 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_descriptor vertex; | |
typedef typename graph_traits < G >::vertex_iterator vertex_iterator; | |
function_requires < AdjacencyMatrixConcept < G > >(); | |
function_requires < 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 |