| <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> |
