1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
<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>
and <a href="./AdjacencyGraph.html">Adjacency Graph</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/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>
|
