225 lines
8.0 KiB
HTML
225 lines
8.0 KiB
HTML
<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>
|