transitive_closure

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 = all 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!

Where Defined

boost/graph/transitive_closure.hpp

Parameters

A directed graph, where the Graph type must model the Vertex List Graph, Adjacency Graph, and Adjacency Matrix concepts.
Python: The parameter is named graph.

A directed graph, where the GraphTC type 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.

Named Parameters

This maps each vertex in the input graph to the new matching vertices in the output transitive closure graph.
Python: This must be a vertex_vertex_map of 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 type VertexIndexMap must 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 internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.
Python: Unsupported parameter.

Complexity

Example

Implementation Notes

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 v, denoted by Succ(v), is the set of vertices that are reachable from vertex v. The set of vertices adjacent to v in the transitive closure G* is the same as the successor set of v in the original graph G. Computing the transitive closure is equivalent to computing the successor set for every vertex in G.

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:

1. Compute strongly connected components of the graph.
2. Construct the condensation graph. A condensation graph is a a 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.
3. 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 chain decomposition [51,52]. The vertices of G are partitioned into chains Z₁, ..., Z_k, where each chain Z_i is a path in 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_i=1...k (Z_i & S). Each intersection can be represented by the first vertex in the path Z_i that is also in 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₃ = S₁ U S₂, can then be computed in 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
   

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