1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 2001 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: Transitive Closure</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<H1><A NAME="sec:transitive_closure"> 19<img src="figs/python.gif" alt="(Python)"/> 20<TT>transitive_closure</TT> 21</H1> 22 23<P> 24<PRE> 25template <typename Graph, typename GraphTC, 26 typename P, typename T, typename R> 27void transitive_closure(const Graph& g, GraphTC& tc, 28 const bgl_named_params<P, T, R>& params = <i>all defaults</i>) 29 30template <typename Graph, typename GraphTC, 31 typename G_to_TC_VertexMap, typename VertexIndexMap> 32void transitive_closure(const Graph& g, GraphTC& tc, 33 G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map) 34</PRE> 35 36The transitive closure of a graph <i>G = (V,E)</i> is a graph <i>G* = 37(V,E*)</i> such that <i>E*</i> contains an edge <i>(u,v)</i> if and 38only if <i>G</i> contains a <a 39href="graph_theory_review.html#def:path">path</a> (of at least one 40edge) from <i>u</i> to <i>v</i>. The <tt>transitive_closure()</tt> 41function transforms the input graph <tt>g</tt> into the transitive 42closure graph <tt>tc</tt>. 43 44<p> 45Thanks to Vladimir Prus for the implementation of this algorithm! 46 47 48 49<H3>Where Defined</H3> 50 51<P> 52<a href="../../../boost/graph/transitive_closure.hpp"><TT>boost/graph/transitive_closure.hpp</TT></a> 53 54<h3>Parameters</h3> 55 56IN: <tt>const Graph& g</tt> 57<blockquote> 58 A directed graph, where the <tt>Graph</tt> type must model the 59 <a href="./VertexListGraph.html">Vertex List Graph</a>, 60 <a href="./AdjacencyGraph.html">Adjacency Graph</a>, 61 and <a href="./AdjacencyMatrix.html">Adjacency Matrix</a> concepts.<br> 62 63 <b>Python</b>: The parameter is named <tt>graph</tt>. 64</blockquote> 65 66OUT: <tt>GraphTC& tc</tt> 67<blockquote> 68 A directed graph, where the <tt>GraphTC</tt> type must model the 69 <a href="./VertexMutableGraph.html">Vertex Mutable Graph</a> 70 and <a href="./EdgeMutableGraph.html">Edge Mutable Graph</a> concepts.<br> 71 72 <b>Python</b>: This parameter is not used in Python. Instead, a new 73 graph of the same type is returned. 74</blockquote> 75 76<h3>Named Parameters</h3> 77 78UTIL/OUT: <tt>orig_to_copy(G_to_TC_VertexMap g_to_tc_map)</tt> 79<blockquote> 80 This maps each vertex in the input graph to the new matching 81 vertices in the output transitive closure graph.<br> 82 83 <b>Python</b>: This must be a <tt>vertex_vertex_map</tt> of the graph. 84</blockquote> 85 86IN: <tt>vertex_index_map(VertexIndexMap& index_map)</tt> 87<blockquote> 88 This maps each vertex to an integer in the range <tt>[0, 89 num_vertices(g))</tt>. This parameter is only necessary when the 90 default color property map is used. The type <tt>VertexIndexMap</tt> 91 must be a model of <a 92 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 93 Map</a>. The value type of the map must be an integer type. The 94 vertex descriptor type of the graph needs to be usable as the key 95 type of the map.<br> 96 97 <b>Default:</b> <tt>get(vertex_index, g)</tt> 98 Note: if you use this default, make sure your graph has 99 an internal <tt>vertex_index</tt> property. For example, 100 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 101 not have an internal <tt>vertex_index</tt> property. 102 <br> 103 104 <b>Python</b>: Unsupported parameter. 105</blockquote> 106 107 108<h3>Complexity</h3> 109 110The time complexity (worst-case) is <i>O(|V||E|)</i>. 111 112<h3>Example</h3> 113 114The following is the graph from the example <tt><a 115href="../example/transitive_closure.cpp">example/transitive_closure.cpp</a></tt> 116and the transitive closure computed by the algorithm. 117 118<table> 119 <tr> 120 <td><img src="tc.gif" width="173" height="264" ></td> 121 <td><img src="tc-out.gif" width="200" height="360"></td> 122 </tr> 123</table> 124 125 126<h3>Implementation Notes</h3> 127 128<p> 129The algorithm used to implement the <tt>transitive_closure()</tt> 130function is based on the detection of strong components[<a 131href="bibliography.html#nuutila95">50</a>, <a 132href="bibliography.html#purdom70">53</a>]. The following discussion 133describes the algorithm (and some relevant background theory). 134 135<p> 136A <a name="def:successor-set"><i><b>successor set</b></i></a> of a 137vertex <i>v</i>, denoted by <i>Succ(v)</i>, is the set of vertices 138that are <a 139href="graph_theory_review.html#def:reachable">reachable</a> from 140vertex <i>v</i>. The set of vertices adjacent to <i>v</i> in the 141transitive closure <i>G*</i> is the same as the successor set of 142<i>v</i> in the original graph <i>G</i>. Computing the transitive 143closure is equivalent to computing the successor set for every vertex 144in <i>G</i>. 145 146<p> 147All vertices in the same strong component have the same successor set 148(because every vertex is reachable from all the other vertices in the 149component). Therefore, it is redundant to compute the successor set 150for every vertex in a strong component; it suffices to compute it for 151just one vertex per component. 152 153<p> 154The following is the outline of the algorithm: 155 156<ol> 157<li>Compute <a 158href="strong_components.html#def:strongly-connected-component">strongly 159connected components</a> of the graph. 160 161<li> Construct the condensation graph. A <a 162name="def:condensation-graph"><i><b>condensation graph</b></i></a> is 163a a graph <i>G'=(V',E')</i> based on the graph <i>G=(V,E)</i> where 164each vertex in <i>V'</i> corresponds to a strongly connected component 165in <i>G</i> and edge <i>(u,v)</i> is in <i>E'</i> if and only if there 166exists an edge in <i>E</i> connecting any of the vertices in the 167component of <i>u</i> to any of the vertices in the component of 168<i>v</i>. 169 170<li> Compute transitive closure on the condensation graph. 171 This is done using the following algorithm: 172<pre> 173 for each vertex u in G' in reverse topological order 174 for each vertex v in Adj[u] 175 if (v not in Succ(u)) 176 Succ(u) = Succ(u) U { v } U Succ(v) // "U" means set union 177</pre> 178 The vertices are considered in reverse topological order to 179 ensure that the when computing the successor set for a vertex 180 <i>u</i>, the successor set for each vertex in <i>Adj[u]</i> 181 has already been computed. 182 183 <p>An optimized implementation of the set union operation improves 184 the performance of the algorithm. Therefore this implementation 185 uses <a name="def:chain-decomposition"><i><b>chain 186 decomposition</b></i></a> [<a 187 href="bibliography.html#goral79">51</a>,<a 188 href="bibliography.html#simon86">52</a>]. The vertices of <i>G</i> 189 are partitioned into chains <i>Z<sub>1</sub>, ..., 190 Z<sub>k</sub></i>, where each chain <i>Z<sub>i</sub></i> is a path 191 in <i>G</i> and the vertices in a chain have increasing topological 192 number. A successor set <i>S</i> is then represented by a 193 collection of intersections with the chains, i.e., <i>S = 194 U<sub>i=1...k</sub> (Z<sub>i</sub> & S)</i>. Each intersection 195 can be represented by the first vertex in the path 196 <i>Z<sub>i</sub></i> that is also in <i>S</I>, since the rest of 197 the path is guaranteed to also be in <i>S</i>. The collection of 198 intersections is therefore represented by a vector of length 199 <i>k</i> where the ith element of the vector stores the first 200 vertex in the intersection of <i>S</i> with <i>Z<sub>i</sub></i>. 201 202 <p>Computing the union of two successor sets, <i>S<sub>3</sub> = 203 S<sub>1</sub> U S<sub>2</sub></i>, can then be computed in 204 <i>O(k)</i> time with the following operation: 205<pre> 206 for i = 0...k 207 S3[i] = min(S1[i], S2[i]) // where min compares the topological number of the vertices 208</pre> 209 210<li>Create the graph <i>G*</i> based on the transitive closure of 211 the condensation graph <i>G'*</i>. 212 213</ol> 214 215<br> 216<HR> 217<TABLE> 218<TR valign=top> 219<TD nowrap>Copyright © 2001</TD><TD> 220<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>) 221</TD></TR></TABLE> 222 223</BODY> 224</HTML> 225
