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