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)The transitive closure of a graph G = (V,E) is a graph G* = (V,E*) such that E* contains an edge (u,v) if and only if G contains a path (of at least one edge) from u to v. The transitive_closure() function transforms the input graph g into the transitive closure graph tc. Thanks to Vladimir Prus for the implementation of this algorithm! Where Definedboost/graph/transitive_closure.hpp ParametersIN: const Graph& gA directed graph, where the Graph type must model the Vertex List Graph and Adjacency Graph concepts.OUT: GraphTC& tc A directed graph, where the GraphTC type must model the Vertex Mutable Graph and Edge Mutable Graph concepts. Named ParametersUTIL/OUT: orig_to_copy(G_to_TC_VertexMap g_to_tc_map)This maps each vertex in the input graph to the new matching vertices in the output transitive closure graph.IN: vertex_index_map(VertexIndexMap& index_map) 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. ComplexityThe time complexity (worst-case) is O(|V||E|).ExampleThe following is the graph from the example example/transitive_closure.cpp and the transitive closure computed by the algorithm.Implementation NotesThe 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:
|