...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

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 =The transitive closure of a graphall defaults) 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)

Thanks to Vladimir Prus for the implementation of this algorithm!

`boost/graph/transitive_closure.hpp`

A directed graph, where theOUT:Graphtype must model the Vertex List Graph and Adjacency Graph concepts.

Python: The parameter is namedgraph.

A directed graph, where theGraphTCtype must model the Vertex Mutable Graph and Edge Mutable Graph concepts.

Python: This parameter is not used in Python. Instead, a new graph of the same type is returned.

This maps each vertex in the input graph to the new matching vertices in the output transitive closure graph.IN:

Python: This must be avertex_vertex_mapof the graph.

This maps each vertex to an integer in the range[0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The typeVertexIndexMapmust be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default:get(vertex_index, g)Note: if you use this default, make sure your graph has an internalvertex_indexproperty. For example,adjacenty_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

Python: Unsupported parameter.

The algorithm used to implement the `transitive_closure()`
function is based on the detection of strong components[50, 53]. The following discussion
describes the algorithm (and some relevant background theory).

A * successor set* of a
vertex

All vertices in the same strong component have the same successor set (because every vertex is reachable from all the other vertices in the component). Therefore, it is redundant to compute the successor set for every vertex in a strong component; it suffices to compute it for just one vertex per component.

The following is the outline of the algorithm:

- Compute strongly connected components of the graph.
- Construct the condensation graph. A
is a a graph**condensation graph***G'=(V',E')*based on the graph*G=(V,E)*where each vertex in*V'*corresponds to a strongly connected component in*G*and edge*(u,v)*is in*E'*if and only if there exists an edge in*E*connecting any of the vertices in the component of*u*to any of the vertices in the component of*v*. - Compute transitive closure on the condensation graph.
This is done using the following algorithm:
for each vertex u in G' in reverse topological order for each vertex v in Adj[u] if (v not in Succ(u)) Succ(u) = Succ(u) U { v } U Succ(v) // "U" means set union

The vertices are considered in reverse topological order to ensure that the when computing the successor set for a vertex*u*, the successor set for each vertex in*Adj[u]*has already been computed.An optimized implementation of the set union operation improves the performance of the algorithm. Therefore this implementation uses

[51,52]. The vertices of**chain decomposition***G*are partitioned into chains*Z*, where each chain_{1}, ..., Z_{k}*Z*is a path in_{i}*G*and the vertices in a chain have increasing topological number. A successor set*S*is then represented by a collection of intersections with the chains, i.e.,*S = U*. Each intersection can be represented by the first vertex in the path_{i=1...k}(Z_{i}& S)*Z*that is also in_{i}*S*, since the rest of the path is guaranteed to also be in*S*. The collection of intersections is therefore represented by a vector of length*k*where the ith element of the vector stores the first vertex in the intersection of*S*with*Z*._{i}Computing the union of two successor sets,

*S*, can then be computed in_{3}= S_{1}U S_{2}*O(k)*time with the following operation:for i = 0...k S3[i] = min(S1[i], S2[i]) // where min compares the topological number of the vertices

- Create the graph
*G**based on the transitive closure of the condensation graph*G'**.

Copyright © 2001 | Jeremy Siek, Indiana Univ.(jsiek@cs.indiana.edu) |