<HTML> <!-- Copyright (c) Jeremy Siek 2001 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) --> <Head> <Title>Boost Graph Library: Transitive Closure</Title> <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="../../../boost.png" ALT="C++ Boost" width="277" height="86"> <BR Clear> <H1><A NAME="sec:transitive_closure"> <img src="figs/python.gif" alt="(Python)"/> <TT>transitive_closure</TT> </H1> <P> <PRE> 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 = <i>all defaults</i>) 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) </PRE> The transitive closure of a graph <i>G = (V,E)</i> is a graph <i>G* = (V,E*)</i> such that <i>E*</i> contains an edge <i>(u,v)</i> if and only if <i>G</i> contains a <a href="graph_theory_review.html#def:path">path</a> (of at least one edge) from <i>u</i> to <i>v</i>. The <tt>transitive_closure()</tt> function transforms the input graph <tt>g</tt> into the transitive closure graph <tt>tc</tt>. <p> Thanks to Vladimir Prus for the implementation of this algorithm! <H3>Where Defined</H3> <P> <a href="../../../boost/graph/transitive_closure.hpp"><TT>boost/graph/transitive_closure.hpp</TT></a> <h3>Parameters</h3> IN: <tt>const Graph& g</tt> <blockquote> A directed graph, where the <tt>Graph</tt> type must model the <a href="./VertexListGraph.html">Vertex List Graph</a>, <a href="./AdjacencyGraph.html">Adjacency Graph</a>, and <a href="./AdjacencyMatrix.html">Adjacency Matrix</a> concepts.<br> <b>Python</b>: The parameter is named <tt>graph</tt>. </blockquote> OUT: <tt>GraphTC& tc</tt> <blockquote> A directed graph, where the <tt>GraphTC</tt> type must model the <a href="./VertexMutableGraph.html">Vertex Mutable Graph</a> and <a href="./EdgeMutableGraph.html">Edge Mutable Graph</a> concepts.<br> <b>Python</b>: This parameter is not used in Python. Instead, a new graph of the same type is returned. </blockquote> <h3>Named Parameters</h3> UTIL/OUT: <tt>orig_to_copy(G_to_TC_VertexMap g_to_tc_map)</tt> <blockquote> This maps each vertex in the input graph to the new matching vertices in the output transitive closure graph.<br> <b>Python</b>: This must be a <tt>vertex_vertex_map</tt> of the graph. </blockquote> IN: <tt>vertex_index_map(VertexIndexMap& index_map)</tt> <blockquote> This maps each vertex to an integer in the range <tt>[0, num_vertices(g))</tt>. This parameter is only necessary when the default color property map is used. The type <tt>VertexIndexMap</tt> must be a model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. 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.<br> <b>Default:</b> <tt>get(vertex_index, g)</tt> Note: if you use this default, make sure your graph has an internal <tt>vertex_index</tt> property. For example, <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does not have an internal <tt>vertex_index</tt> property. <br> <b>Python</b>: Unsupported parameter. </blockquote> <h3>Complexity</h3> The time complexity (worst-case) is <i>O(|V||E|)</i>. <h3>Example</h3> The following is the graph from the example <tt><a href="../example/transitive_closure.cpp">example/transitive_closure.cpp</a></tt> and the transitive closure computed by the algorithm. <table> <tr> <td><img src="tc.gif" width="173" height="264" ></td> <td><img src="tc-out.gif" width="200" height="360"></td> </tr> </table> <h3>Implementation Notes</h3> <p> The algorithm used to implement the <tt>transitive_closure()</tt> function is based on the detection of strong components[<a href="bibliography.html#nuutila95">50</a>, <a href="bibliography.html#purdom70">53</a>]. The following discussion describes the algorithm (and some relevant background theory). <p> A <a name="def:successor-set"><i><b>successor set</b></i></a> of a vertex <i>v</i>, denoted by <i>Succ(v)</i>, is the set of vertices that are <a href="graph_theory_review.html#def:reachable">reachable</a> from vertex <i>v</i>. The set of vertices adjacent to <i>v</i> in the transitive closure <i>G*</i> is the same as the successor set of <i>v</i> in the original graph <i>G</i>. Computing the transitive closure is equivalent to computing the successor set for every vertex in <i>G</i>. <p> 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. <p> The following is the outline of the algorithm: <ol> <li>Compute <a href="strong_components.html#def:strongly-connected-component">strongly connected components</a> of the graph. <li> Construct the condensation graph. A <a name="def:condensation-graph"><i><b>condensation graph</b></i></a> is a a graph <i>G'=(V',E')</i> based on the graph <i>G=(V,E)</i> where each vertex in <i>V'</i> corresponds to a strongly connected component in <i>G</i> and edge <i>(u,v)</i> is in <i>E'</i> if and only if there exists an edge in <i>E</i> connecting any of the vertices in the component of <i>u</i> to any of the vertices in the component of <i>v</i>. <li> Compute transitive closure on the condensation graph. This is done using the following algorithm: <pre> 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 </pre> The vertices are considered in reverse topological order to ensure that the when computing the successor set for a vertex <i>u</i>, the successor set for each vertex in <i>Adj[u]</i> has already been computed. <p>An optimized implementation of the set union operation improves the performance of the algorithm. Therefore this implementation uses <a name="def:chain-decomposition"><i><b>chain decomposition</b></i></a> [<a href="bibliography.html#goral79">51</a>,<a href="bibliography.html#simon86">52</a>]. The vertices of <i>G</i> are partitioned into chains <i>Z<sub>1</sub>, ..., Z<sub>k</sub></i>, where each chain <i>Z<sub>i</sub></i> is a path in <i>G</i> and the vertices in a chain have increasing topological number. A successor set <i>S</i> is then represented by a collection of intersections with the chains, i.e., <i>S = U<sub>i=1...k</sub> (Z<sub>i</sub> & S)</i>. Each intersection can be represented by the first vertex in the path <i>Z<sub>i</sub></i> that is also in <i>S</I>, since the rest of the path is guaranteed to also be in <i>S</i>. The collection of intersections is therefore represented by a vector of length <i>k</i> where the ith element of the vector stores the first vertex in the intersection of <i>S</i> with <i>Z<sub>i</sub></i>. <p>Computing the union of two successor sets, <i>S<sub>3</sub> = S<sub>1</sub> U S<sub>2</sub></i>, can then be computed in <i>O(k)</i> time with the following operation: <pre> for i = 0...k S3[i] = min(S1[i], S2[i]) // where min compares the topological number of the vertices </pre> <li>Create the graph <i>G*</i> based on the transitive closure of the condensation graph <i>G'*</i>. </ol> <br> <HR> <TABLE> <TR valign=top> <TD nowrap>Copyright © 2001</TD><TD> <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana Univ.(<A HREF="mailto:jsiek@cs.indiana.edu">jsiek@cs.indiana.edu</A>) </TD></TR></TABLE> </BODY> </HTML>