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