]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | \documentclass[11pt]{report} |
2 | ||
3 | \input{defs} | |
4 | ||
5 | ||
6 | \setlength\overfullrule{5pt} | |
7 | \tolerance=10000 | |
8 | \sloppy | |
9 | \hfuzz=10pt | |
10 | ||
11 | \makeindex | |
12 | ||
13 | \begin{document} | |
14 | ||
15 | \title{A Generic Programming Implementation of Transitive Closure} | |
16 | \author{Jeremy G. Siek} | |
17 | ||
18 | \maketitle | |
19 | ||
20 | \section{Introduction} | |
21 | ||
22 | This paper documents the implementation of the | |
23 | \code{transitive\_closure()} function of the Boost Graph Library. The | |
24 | function was implemented by Vladimir Prus and some editing was done by | |
25 | Jeremy Siek. | |
26 | ||
27 | The algorithm used to implement the \code{transitive\_closure()} | |
28 | function is based on the detection of strong components | |
29 | \cite{nuutila95, purdom70}. The following discussion describes the | |
30 | main ideas of the algorithm and some relevant background theory. | |
31 | ||
32 | The \keyword{transitive closure} of a graph $G = (V,E)$ is a graph $G^+ | |
33 | = (V,E^+)$ such that $E^+$ contains an edge $(u,v)$ if and only if $G$ | |
34 | contains a path (of at least one edge) from $u$ to $v$. A | |
35 | \keyword{successor set} of a vertex $v$, denoted by $Succ(v)$, is the | |
36 | set of vertices that are reachable from vertex $v$. The set of | |
37 | vertices adjacent to $v$ in the transitive closure $G^+$ is the same as | |
38 | the successor set of $v$ in the original graph $G$. Computing the | |
39 | transitive closure is equivalent to computing the successor set for | |
40 | every vertex in $G$. | |
41 | ||
42 | All vertices in the same strong component have the same successor set | |
43 | (because every vertex is reachable from all the other vertices in the | |
44 | component). Therefore, it is redundant to compute the successor set | |
45 | for every vertex in a strong component; it suffices to compute it for | |
46 | just one vertex per component. | |
47 | ||
48 | A \keyword{condensation graph} is a a graph $G'=(V',E')$ based on the | |
49 | graph $G=(V,E)$ where each vertex in $V'$ corresponds to a strongly | |
50 | connected component in $G$ and the edge $(s,t)$ is in $E'$ if and only | |
51 | if there exists an edge in $E$ connecting any of the vertices in the | |
52 | component of $s$ to any of the vertices in the component of $t$. | |
53 | ||
54 | \section{The Implementation} | |
55 | ||
56 | The following is the interface and outline of the function: | |
57 | ||
58 | @d Transitive Closure Function | |
59 | @{ | |
60 | template <typename Graph, typename GraphTC, | |
61 | typename G_to_TC_VertexMap, | |
62 | typename VertexIndexMap> | |
63 | void transitive_closure(const Graph& g, GraphTC& tc, | |
64 | G_to_TC_VertexMap g_to_tc_map, | |
65 | VertexIndexMap index_map) | |
66 | { | |
67 | if (num_vertices(g) == 0) return; | |
68 | @<Some type definitions@> | |
69 | @<Concept checking@> | |
70 | @<Compute strongly connected components of the graph@> | |
71 | @<Construct the condensation graph (version 2)@> | |
72 | @<Compute transitive closure on the condensation graph@> | |
73 | @<Build transitive closure of the original graph@> | |
74 | } | |
75 | @} | |
76 | ||
77 | The parameter \code{g} is the input graph and the parameter \code{tc} | |
78 | is the output graph that will contain the transitive closure of | |
79 | \code{g}. The \code{g\_to\_tc\_map} maps vertices in the input graph | |
80 | to the new vertices in the output transitive closure. The | |
81 | \code{index\_map} maps vertices in the input graph to the integers | |
82 | zero to \code{num\_vertices(g) - 1}. | |
83 | ||
84 | There are two alternate interfaces for the transitive closure | |
85 | function. The following is the version where defaults are used for | |
86 | both the \code{g\_to\_tc\_map} and the \code{index\_map}. | |
87 | ||
88 | @d The All Defaults Interface | |
89 | @{ | |
90 | template <typename Graph, typename GraphTC> | |
91 | void transitive_closure(const Graph& g, GraphTC& tc) | |
92 | { | |
93 | if (num_vertices(g) == 0) return; | |
94 | typedef typename property_map<Graph, vertex_index_t>::const_type | |
95 | VertexIndexMap; | |
96 | VertexIndexMap index_map = get(vertex_index, g); | |
97 | ||
98 | typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex; | |
99 | std::vector<tc_vertex> to_tc_vec(num_vertices(g)); | |
100 | iterator_property_map<tc_vertex*, VertexIndexMap> | |
101 | g_to_tc_map(&to_tc_vec[0], index_map); | |
102 | ||
103 | transitive_closure(g, tc, g_to_tc_map, index_map); | |
104 | } | |
105 | @} | |
106 | ||
107 | \noindent The following alternate interface uses the named parameter | |
108 | trick for specifying the parameters. The named parameter functions to | |
109 | use in creating the \code{params} argument are | |
110 | \code{vertex\_index(VertexIndexMap index\_map)} and | |
111 | \code{orig\_to\_copy(G\_to\_TC\_VertexMap g\_to\_tc\_map)}. | |
112 | ||
113 | @d The Named Parameter Interface | |
114 | @{ | |
115 | template <typename Graph, typename GraphTC, | |
116 | typename P, typename T, typename R> | |
117 | void transitive_closure(const Graph& g, GraphTC& tc, | |
118 | const bgl_named_params<P, T, R>& params) | |
119 | { | |
120 | if (num_vertices(g) == 0) return; | |
121 | detail::transitive_closure_dispatch(g, tc, | |
122 | get_param(params, orig_to_copy), | |
123 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index) | |
124 | ); | |
125 | } | |
126 | @} | |
127 | ||
128 | \noindent This dispatch function is used to handle the logic for | |
129 | deciding between a user-provided graph to transitive closure vertex | |
130 | mapping or to use the default, a vector, to map between the two. | |
131 | ||
132 | @d Construct Default G to TC Vertex Mapping | |
133 | @{ | |
134 | namespace detail { | |
135 | template <typename Graph, typename GraphTC, | |
136 | typename G_to_TC_VertexMap, | |
137 | typename VertexIndexMap> | |
138 | void transitive_closure_dispatch | |
139 | (const Graph& g, GraphTC& tc, | |
140 | G_to_TC_VertexMap g_to_tc_map, | |
141 | VertexIndexMap index_map) | |
142 | { | |
143 | typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex; | |
144 | typename std::vector<tc_vertex>::size_type | |
145 | n = is_default_param(g_to_tc_map) ? num_vertices(g) : 1; | |
146 | std::vector<tc_vertex> to_tc_vec(n); | |
147 | ||
148 | transitive_closure | |
149 | (g, tc, | |
150 | choose_param(g_to_tc_map, make_iterator_property_map | |
151 | (to_tc_vec.begin(), index_map, to_tc_vec[0])), | |
152 | index_map); | |
153 | } | |
154 | } // namespace detail | |
155 | @} | |
156 | ||
157 | The following statements check to make sure that the template | |
158 | parameters \emph{model} the concepts that are required for this | |
159 | algorithm. | |
160 | ||
161 | @d Concept checking | |
162 | @{ | |
163 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); | |
164 | BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<Graph> )); | |
165 | BOOST_CONCEPT_ASSERT(( VertexMutableGraphConcept<GraphTC> )); | |
166 | BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept<GraphTC> )); | |
167 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<VertexIndexMap, vertex> )); | |
168 | @} | |
169 | ||
170 | \noindent To simplify the code in the rest of the function we make the | |
171 | following typedefs. | |
172 | ||
173 | @d Some type definitions | |
174 | @{ | |
175 | typedef typename graph_traits<Graph>::vertex_descriptor vertex; | |
176 | typedef typename graph_traits<Graph>::edge_descriptor edge; | |
177 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; | |
178 | typedef typename property_traits<VertexIndexMap>::value_type size_type; | |
179 | typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator; | |
180 | @} | |
181 | ||
182 | The first step of the algorithm is to compute which vertices are in | |
183 | each strongly connected component (SCC) of the graph. This is done | |
184 | with the \code{strong\_components()} function. The result of this | |
185 | function is stored in the \code{component\_number} array which maps | |
186 | each vertex to the number of the SCC to which it belongs (the | |
187 | components are numbered zero through \code{num\_scc}). We will use | |
188 | the SCC numbers for vertices in the condensation graph (CG), so we use | |
189 | the same integer type \code{cg\_vertex} for both. | |
190 | ||
191 | @d Compute strongly connected components of the graph | |
192 | @{ | |
193 | typedef size_type cg_vertex; | |
194 | std::vector<cg_vertex> component_number_vec(num_vertices(g)); | |
195 | iterator_property_map<cg_vertex*, VertexIndexMap> | |
196 | component_number(&component_number_vec[0], index_map); | |
197 | ||
198 | int num_scc = strong_components(g, component_number, | |
199 | vertex_index_map(index_map)); | |
200 | ||
201 | std::vector< std::vector<vertex> > components; | |
202 | build_component_lists(g, num_scc, component_number, components); | |
203 | @} | |
204 | ||
205 | \noindent Later we will need efficient access to all vertices in the | |
206 | same SCC so we create a \code{std::vector} of vertices for each SCC | |
207 | and fill it in with the \code{build\_components\_lists()} function | |
208 | from \code{strong\_components.hpp}. | |
209 | ||
210 | The next step is to construct the condensation graph. There will be | |
211 | one vertex in the CG for every strongly connected component in the | |
212 | original graph. We will add an edge to the CG whenever there is one or | |
213 | more edges in the original graph that has its source in one SCC and | |
214 | its target in another SCC. The data structure we will use for the CG | |
215 | is an adjacency-list with a \code{std::set} for each out-edge list. We | |
216 | use \code{std::set} because it will automatically discard parallel | |
217 | edges. This makes the code simpler since we can just call | |
218 | \code{insert()} every time there is an edge connecting two SCCs in the | |
219 | original graph. | |
220 | ||
221 | @d Construct the condensation graph (version 1) | |
222 | @{ | |
223 | typedef std::vector< std::set<cg_vertex> > CG_t; | |
224 | CG_t CG(num_scc); | |
225 | for (cg_vertex s = 0; s < components.size(); ++s) { | |
226 | for (size_type i = 0; i < components[s].size(); ++i) { | |
227 | vertex u = components[s][i]; | |
228 | adjacency_iterator vi, vi_end; | |
229 | for (tie(vi, vi_end) = adjacent_vertices(u, g); vi != vi_end; ++vi) { | |
230 | cg_vertex t = component_number[*vi]; | |
231 | if (s != t) // Avoid loops in the condensation graph | |
232 | CG[s].insert(t); // add edge (s,t) to the condensation graph | |
233 | } | |
234 | } | |
235 | } | |
236 | @} | |
237 | ||
238 | Inserting into a \code{std::set} and iterator traversal for | |
239 | \code{std::set} is a bit slow. We can get better performance if we use | |
240 | \code{std::vector} and then explicitly remove duplicated vertices from | |
241 | the out-edge lists. Here is the construction of the condensation graph | |
242 | rewritten to use \code{std::vector}. | |
243 | ||
244 | @d Construct the condensation graph (version 2) | |
245 | @{ | |
246 | typedef std::vector< std::vector<cg_vertex> > CG_t; | |
247 | CG_t CG(num_scc); | |
248 | for (cg_vertex s = 0; s < components.size(); ++s) { | |
249 | std::vector<cg_vertex> adj; | |
250 | for (size_type i = 0; i < components[s].size(); ++i) { | |
251 | vertex u = components[s][i]; | |
252 | adjacency_iterator v, v_end; | |
253 | for (tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) { | |
254 | cg_vertex t = component_number[*v]; | |
255 | if (s != t) // Avoid loops in the condensation graph | |
256 | adj.push_back(t); | |
257 | } | |
258 | } | |
259 | std::sort(adj.begin(), adj.end()); | |
260 | std::vector<cg_vertex>::iterator di = std::unique(adj.begin(), adj.end()); | |
261 | if (di != adj.end()) | |
262 | adj.erase(di, adj.end()); | |
263 | CG[s] = adj; | |
264 | } | |
265 | @} | |
266 | ||
267 | Next we compute the transitive closure of the condensation graph. The | |
268 | basic outline of the algorithm is below. The vertices are considered | |
269 | in reverse topological order to ensure that the when computing the | |
270 | successor set for a vertex $u$, the successor set for each vertex in | |
271 | $Adj[u]$ has already been computed. The successor set for a vertex $u$ | |
272 | can then be constructed by taking the union of the successor sets for | |
273 | all of its adjacent vertices together with the adjacent vertices | |
274 | themselves. | |
275 | ||
276 | \begin{tabbing} | |
277 | \textbf{for} \= ea\=ch \= vertex $u$ in $G'$ in reverse topological order \\ | |
278 | \>\textbf{for} each vertex $v$ in $Adj[u]$ \\ | |
279 | \>\>if ($v \notin Succ(u)$) \\ | |
280 | \>\>\>$Succ(u)$ := $Succ(u) \cup \{ v \} \cup Succ(v)$ | |
281 | \end{tabbing} | |
282 | ||
283 | An optimized implementation of the set union operation improves the | |
284 | performance of the algorithm. Therefore this implementation uses | |
285 | \keyword{chain decomposition}\cite{goral79,simon86}. The vertices of | |
286 | $G$ are partitioned into chains $Z_1, ..., Z_k$, where each chain | |
287 | $Z_i$ is a path in $G$ and the vertices in a chain have increasing | |
288 | topological number. A successor set $S$ is then represented by a | |
289 | collection of intersections with the chains, i.e., $S = | |
290 | \bigcup_{i=1 \ldots k} (Z_i \cap S)$. Each intersection can be represented | |
291 | by the first vertex in the path $Z_i$ that is also in $S$, since the | |
292 | rest of the path is guaranteed to also be in $S$. The collection of | |
293 | intersections is therefore represented by a vector of length $k$ where | |
294 | the $i$th element of the vector stores the first vertex in the | |
295 | intersection of $S$ with $Z_i$. | |
296 | ||
297 | Computing the union of two successor sets, $S_3 = S_1 \cup S_2$, can | |
298 | then be computed in $O(k)$ time with the below operation. We will | |
299 | represent the successor sets by vectors of integers where the integers | |
300 | are the topological numbers for the vertices in the set. | |
301 | ||
302 | @d Union of successor sets | |
303 | @{ | |
304 | namespace detail { | |
305 | inline void | |
306 | union_successor_sets(const std::vector<std::size_t>& s1, | |
307 | const std::vector<std::size_t>& s2, | |
308 | std::vector<std::size_t>& s3) | |
309 | { | |
310 | for (std::size_t k = 0; k < s1.size(); ++k) | |
311 | s3[k] = std::min(s1[k], s2[k]); | |
312 | } | |
313 | } // namespace detail | |
314 | @} | |
315 | ||
316 | So to compute the transitive closure we must first sort the graph by | |
317 | topological number and then decompose the graph into chains. Once | |
318 | that is accomplished we can enter the main loop and begin computing | |
319 | the successor sets. | |
320 | ||
321 | @d Compute transitive closure on the condensation graph | |
322 | @{ | |
323 | @<Compute topological number for each vertex@> | |
324 | @<Sort the out-edge lists by topological number@> | |
325 | @<Decompose the condensation graph into chains@> | |
326 | @<Compute successor sets@> | |
327 | @<Build the transitive closure of the condensation graph@> | |
328 | @} | |
329 | ||
330 | The \code{topological\_sort()} function is called to obtain a list of | |
331 | vertices in topological order and then we use this ordering to assign | |
332 | topological numbers to the vertices. | |
333 | ||
334 | @d Compute topological number for each vertex | |
335 | @{ | |
336 | std::vector<cg_vertex> topo_order; | |
337 | std::vector<cg_vertex> topo_number(num_vertices(CG)); | |
338 | topological_sort(CG, std::back_inserter(topo_order), | |
339 | vertex_index_map(identity_property_map())); | |
340 | std::reverse(topo_order.begin(), topo_order.end()); | |
341 | size_type n = 0; | |
342 | for (std::vector<cg_vertex>::iterator i = topo_order.begin(); | |
343 | i != topo_order.end(); ++i) | |
344 | topo_number[*i] = n++; | |
345 | @} | |
346 | ||
347 | Next we sort the out-edge lists of the condensation graph by | |
348 | topological number. This is needed for computing the chain | |
349 | decomposition, for each the vertices in a chain must be in topological | |
350 | order and we will be adding vertices to the chains from the out-edge | |
351 | lists. The \code{subscript()} function creates a function object that | |
352 | returns the topological number of its input argument. | |
353 | ||
354 | @d Sort the out-edge lists by topological number | |
355 | @{ | |
356 | for (size_type i = 0; i < num_vertices(CG); ++i) | |
357 | std::sort(CG[i].begin(), CG[i].end(), | |
358 | compose_f_gx_hy(std::less<cg_vertex>(), | |
359 | detail::subscript(topo_number), | |
360 | detail::subscript(topo_number))); | |
361 | @} | |
362 | ||
363 | Here is the code that defines the \code{subscript\_t} function object | |
364 | and its associated helper object generation function. | |
365 | ||
366 | @d Subscript function object | |
367 | @{ | |
368 | namespace detail { | |
369 | template <typename Container, typename ST = std::size_t, | |
370 | typename VT = typename Container::value_type> | |
371 | struct subscript_t : public std::unary_function<ST, VT> { | |
372 | subscript_t(Container& c) : container(&c) { } | |
373 | VT& operator()(const ST& i) const { return (*container)[i]; } | |
374 | protected: | |
375 | Container *container; | |
376 | }; | |
377 | template <typename Container> | |
378 | subscript_t<Container> subscript(Container& c) | |
379 | { return subscript_t<Container>(c); } | |
380 | } // namespace detail | |
381 | @} | |
382 | ||
383 | ||
384 | Now we are ready to decompose the condensation graph into chains. The | |
385 | idea is that we want to form lists of vertices that are in a path and | |
386 | that the vertices in the list should be ordered by topological number. | |
387 | These lists will be stored in the \code{chains} vector below. To | |
388 | create the chains we consider each vertex in the graph in topological | |
389 | order. If the vertex is not already in a chain then it will be the | |
390 | start of a new chain. We then follow a path from this vertex to extend | |
391 | the chain. | |
392 | ||
393 | @d Decompose the condensation graph into chains | |
394 | @{ | |
395 | std::vector< std::vector<cg_vertex> > chains; | |
396 | { | |
397 | std::vector<cg_vertex> in_a_chain(num_vertices(CG)); | |
398 | for (std::vector<cg_vertex>::iterator i = topo_order.begin(); | |
399 | i != topo_order.end(); ++i) { | |
400 | cg_vertex v = *i; | |
401 | if (!in_a_chain[v]) { | |
402 | chains.resize(chains.size() + 1); | |
403 | std::vector<cg_vertex>& chain = chains.back(); | |
404 | for (;;) { | |
405 | @<Extend the chain until the path dead-ends@> | |
406 | } | |
407 | } | |
408 | } | |
409 | } | |
410 | @<Record the chain number and chain position for each vertex@> | |
411 | @} | |
412 | ||
413 | \noindent To extend the chain we pick an adjacent vertex that is not | |
414 | already in a chain. Also, the adjacent vertex chosen will be the one | |
415 | with lowest topological number since the out-edges of \code{CG} are in | |
416 | topological order. | |
417 | ||
418 | @d Extend the chain until the path dead-ends | |
419 | @{ | |
420 | chain.push_back(v); | |
421 | in_a_chain[v] = true; | |
422 | graph_traits<CG_t>::adjacency_iterator adj_first, adj_last; | |
423 | tie(adj_first, adj_last) = adjacent_vertices(v, CG); | |
424 | graph_traits<CG_t>::adjacency_iterator next | |
425 | = std::find_if(adj_first, adj_last, not1(detail::subscript(in_a_chain))); | |
426 | if (next != adj_last) | |
427 | v = *next; | |
428 | else | |
429 | break; // end of chain, dead-end | |
430 | @} | |
431 | ||
432 | In the next steps of the algorithm we will need to efficiently find | |
433 | the chain for a vertex and the position in the chain for a vertex, so | |
434 | here we compute this information and store it in two vectors: | |
435 | \code{chain\_number} and \code{pos\_in\_chain}. | |
436 | ||
437 | @d Record the chain number and chain position for each vertex | |
438 | @{ | |
439 | std::vector<size_type> chain_number(num_vertices(CG)); | |
440 | std::vector<size_type> pos_in_chain(num_vertices(CG)); | |
441 | for (size_type i = 0; i < chains.size(); ++i) | |
442 | for (size_type j = 0; j < chains[i].size(); ++j) { | |
443 | cg_vertex v = chains[i][j]; | |
444 | chain_number[v] = i; | |
445 | pos_in_chain[v] = j; | |
446 | } | |
447 | @} | |
448 | ||
449 | Now that we have completed the chain decomposition we are ready to | |
450 | write the main loop for computing the transitive closure of the | |
451 | condensation graph. The output of this will be a successor set for | |
452 | each vertex. Remember that the successor set is stored as a collection | |
453 | of intersections with the chains. Each successor set is represented by | |
454 | a vector where the $i$th element is the representative vertex for the | |
455 | intersection of the set with the $i$th chain. We compute the successor | |
456 | sets for every vertex in decreasing topological order. The successor | |
457 | set for each vertex is the union of the successor sets of the adjacent | |
458 | vertex plus the adjacent vertices themselves. | |
459 | ||
460 | @d Compute successor sets | |
461 | @{ | |
462 | cg_vertex inf = std::numeric_limits<cg_vertex>::max(); | |
463 | std::vector< std::vector<cg_vertex> > successors(num_vertices(CG), | |
464 | std::vector<cg_vertex>(chains.size(), inf)); | |
465 | for (std::vector<cg_vertex>::reverse_iterator i = topo_order.rbegin(); | |
466 | i != topo_order.rend(); ++i) { | |
467 | cg_vertex u = *i; | |
468 | graph_traits<CG_t>::adjacency_iterator adj, adj_last; | |
469 | for (tie(adj, adj_last) = adjacent_vertices(u, CG); | |
470 | adj != adj_last; ++adj) { | |
471 | cg_vertex v = *adj; | |
472 | if (topo_number[v] < successors[u][chain_number[v]]) { | |
473 | // Succ(u) = Succ(u) U Succ(v) | |
474 | detail::union_successor_sets(successors[u], successors[v], | |
475 | successors[u]); | |
476 | // Succ(u) = Succ(u) U {v} | |
477 | successors[u][chain_number[v]] = topo_number[v]; | |
478 | } | |
479 | } | |
480 | } | |
481 | @} | |
482 | ||
483 | We now rebuild the condensation graph, adding in edges to connect each | |
484 | vertex to every vertex in its successor set, thereby obtaining the | |
485 | transitive closure. The successor set vectors contain topological | |
486 | numbers, so we map back to vertices using the \code{topo\_order} | |
487 | vector. | |
488 | ||
489 | @d Build the transitive closure of the condensation graph | |
490 | @{ | |
491 | for (size_type i = 0; i < CG.size(); ++i) | |
492 | CG[i].clear(); | |
493 | for (size_type i = 0; i < CG.size(); ++i) | |
494 | for (size_type j = 0; j < chains.size(); ++j) { | |
495 | size_type topo_num = successors[i][j]; | |
496 | if (topo_num < inf) { | |
497 | cg_vertex v = topo_order[topo_num]; | |
498 | for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k) | |
499 | CG[i].push_back(chains[j][k]); | |
500 | } | |
501 | } | |
502 | @} | |
503 | ||
504 | The last stage is to create the transitive closure graph $G^+$ based on | |
505 | the transitive closure of the condensation graph $G'^+$. We do this in | |
506 | two steps. First we add edges between all the vertices in one SCC to | |
507 | all the vertices in another SCC when the two SCCs are adjacent in the | |
508 | condensation graph. Second we add edges to connect each vertex in a | |
509 | SCC to every other vertex in the SCC. | |
510 | ||
511 | @d Build transitive closure of the original graph | |
512 | @{ | |
513 | // Add vertices to the transitive closure graph | |
514 | typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex; | |
515 | { | |
516 | vertex_iterator i, i_end; | |
517 | for (tie(i, i_end) = vertices(g); i != i_end; ++i) | |
518 | g_to_tc_map[*i] = add_vertex(tc); | |
519 | } | |
520 | // Add edges between all the vertices in two adjacent SCCs | |
521 | graph_traits<CG_t>::vertex_iterator si, si_end; | |
522 | for (tie(si, si_end) = vertices(CG); si != si_end; ++si) { | |
523 | cg_vertex s = *si; | |
524 | graph_traits<CG_t>::adjacency_iterator i, i_end; | |
525 | for (tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++i) { | |
526 | cg_vertex t = *i; | |
527 | for (size_type k = 0; k < components[s].size(); ++k) | |
528 | for (size_type l = 0; l < components[t].size(); ++l) | |
529 | add_edge(g_to_tc_map[components[s][k]], | |
530 | g_to_tc_map[components[t][l]], tc); | |
531 | } | |
532 | } | |
533 | // Add edges connecting all vertices in a SCC | |
534 | for (size_type i = 0; i < components.size(); ++i) | |
535 | if (components[i].size() > 1) | |
536 | for (size_type k = 0; k < components[i].size(); ++k) | |
537 | for (size_type l = 0; l < components[i].size(); ++l) { | |
538 | vertex u = components[i][k], v = components[i][l]; | |
539 | add_edge(g_to_tc_map[u], g_to_tc_map[v], tc); | |
540 | } | |
541 | ||
542 | // Find loopbacks in the original graph. | |
543 | // Need to add it to transitive closure. | |
544 | { | |
545 | vertex_iterator i, i_end; | |
546 | for (tie(i, i_end) = vertices(g); i != i_end; ++i) | |
547 | { | |
548 | adjacency_iterator ab, ae; | |
549 | for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab) | |
550 | { | |
551 | if (*ab == *i) | |
552 | if (components[component_number[*i]].size() == 1) | |
553 | add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc); | |
554 | } | |
555 | } | |
556 | } | |
557 | @} | |
558 | ||
559 | \section{Appendix} | |
560 | ||
561 | @d Warshall Transitive Closure | |
562 | @{ | |
563 | template <typename G> | |
564 | void warshall_transitive_closure(G& g) | |
565 | { | |
566 | typedef typename graph_traits<G>::vertex_descriptor vertex; | |
567 | typedef typename graph_traits<G>::vertex_iterator vertex_iterator; | |
568 | ||
569 | BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<G> )); | |
570 | BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept<G> )); | |
571 | ||
572 | // Matrix form: | |
573 | // for k | |
574 | // for i | |
575 | // if A[i,k] | |
576 | // for j | |
577 | // A[i,j] = A[i,j] | A[k,j] | |
578 | vertex_iterator ki, ke, ii, ie, ji, je; | |
579 | for (tie(ki, ke) = vertices(g); ki != ke; ++ki) | |
580 | for (tie(ii, ie) = vertices(g); ii != ie; ++ii) | |
581 | if (edge(*ii, *ki, g).second) | |
582 | for (tie(ji, je) = vertices(g); ji != je; ++ji) | |
583 | if (!edge(*ii, *ji, g).second && | |
584 | edge(*ki, *ji, g).second) | |
585 | { | |
586 | add_edge(*ii, *ji, g); | |
587 | } | |
588 | } | |
589 | @} | |
590 | ||
591 | @d Warren Transitive Closure | |
592 | @{ | |
593 | template <typename G> | |
594 | void warren_transitive_closure(G& g) | |
595 | { | |
596 | using namespace boost; | |
597 | typedef typename graph_traits<G>::vertex_descriptor vertex; | |
598 | typedef typename graph_traits<G>::vertex_iterator vertex_iterator; | |
599 | ||
600 | BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<G> )); | |
601 | BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept<G> )); | |
602 | ||
603 | // Make sure second loop will work | |
604 | if (num_vertices(g) == 0) | |
605 | return; | |
606 | ||
607 | // for i = 2 to n | |
608 | // for k = 1 to i - 1 | |
609 | // if A[i,k] | |
610 | // for j = 1 to n | |
611 | // A[i,j] = A[i,j] | A[k,j] | |
612 | ||
613 | vertex_iterator ic, ie, jc, je, kc, ke; | |
614 | for (tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic) | |
615 | for (tie(kc, ke) = vertices(g); *kc != *ic; ++kc) | |
616 | if (edge(*ic, *kc, g).second) | |
617 | for (tie(jc, je) = vertices(g); jc != je; ++jc) | |
618 | if (!edge(*ic, *jc, g).second && | |
619 | edge(*kc, *jc, g).second) | |
620 | { | |
621 | add_edge(*ic, *jc, g); | |
622 | } | |
623 | ||
624 | // for i = 1 to n - 1 | |
625 | // for k = i + 1 to n | |
626 | // if A[i,k] | |
627 | // for j = 1 to n | |
628 | // A[i,j] = A[i,j] | A[k,j] | |
629 | ||
630 | for (tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic) | |
631 | for (kc = ic, ke = ie, ++kc; kc != ke; ++kc) | |
632 | if (edge(*ic, *kc, g).second) | |
633 | for (tie(jc, je) = vertices(g); jc != je; ++jc) | |
634 | if (!edge(*ic, *jc, g).second && | |
635 | edge(*kc, *jc, g).second) | |
636 | { | |
637 | add_edge(*ic, *jc, g); | |
638 | } | |
639 | } | |
640 | @} | |
641 | ||
642 | ||
643 | The following indent command was run on the output files before | |
644 | they were checked into the Boost CVS repository. | |
645 | ||
646 | @e indentation | |
647 | @{ | |
648 | indent -nut -npcs -i2 -br -cdw -ce transitive_closure.hpp | |
649 | @} | |
650 | ||
651 | @o transitive_closure.hpp | |
652 | @{ | |
653 | // Copyright (C) 2001 Vladimir Prus <ghost@@cs.msu.su> | |
654 | // Copyright (C) 2001 Jeremy Siek <jsiek@@cs.indiana.edu> | |
655 | // Permission to copy, use, modify, sell and distribute this software is | |
656 | // granted, provided this copyright notice appears in all copies and | |
657 | // modified version are clearly marked as such. This software is provided | |
658 | // "as is" without express or implied warranty, and with no claim as to its | |
659 | // suitability for any purpose. | |
660 | ||
661 | // NOTE: this final is generated by libs/graph/doc/transitive_closure.w | |
662 | ||
663 | #ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP | |
664 | #define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP | |
665 | ||
666 | #include <vector> | |
667 | #include <functional> | |
668 | #include <boost/compose.hpp> | |
669 | #include <boost/graph/vector_as_graph.hpp> | |
670 | #include <boost/graph/strong_components.hpp> | |
671 | #include <boost/graph/topological_sort.hpp> | |
672 | #include <boost/graph/graph_concepts.hpp> | |
673 | #include <boost/graph/named_function_params.hpp> | |
674 | #include <boost/concept/assert.hpp> | |
675 | ||
676 | namespace boost { | |
677 | ||
678 | @<Union of successor sets@> | |
679 | @<Subscript function object@> | |
680 | @<Transitive Closure Function@> | |
681 | @<The All Defaults Interface@> | |
682 | @<Construct Default G to TC Vertex Mapping@> | |
683 | @<The Named Parameter Interface@> | |
684 | ||
685 | @<Warshall Transitive Closure@> | |
686 | ||
687 | @<Warren Transitive Closure@> | |
688 | ||
689 | } // namespace boost | |
690 | ||
691 | #endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP | |
692 | @} | |
693 | ||
694 | @o transitive_closure.cpp | |
695 | @{ | |
696 | // Copyright (c) Jeremy Siek 2001 | |
697 | // | |
698 | // Permission to use, copy, modify, distribute and sell this software | |
699 | // and its documentation for any purpose is hereby granted without fee, | |
700 | // provided that the above copyright notice appears in all copies and | |
701 | // that both that copyright notice and this permission notice appear | |
702 | // in supporting documentation. Silicon Graphics makes no | |
703 | // representations about the suitability of this software for any | |
704 | // purpose. It is provided "as is" without express or implied warranty. | |
705 | ||
706 | // NOTE: this final is generated by libs/graph/doc/transitive_closure.w | |
707 | ||
708 | #include <boost/graph/transitive_closure.hpp> | |
709 | #include <boost/graph/graphviz.hpp> | |
710 | ||
711 | int main(int, char*[]) | |
712 | { | |
713 | using namespace boost; | |
714 | typedef property<vertex_name_t, char> Name; | |
715 | typedef property<vertex_index_t, std::size_t, | |
716 | Name> Index; | |
717 | typedef adjacency_list<listS, listS, directedS, Index> graph_t; | |
718 | typedef graph_traits<graph_t>::vertex_descriptor vertex_t; | |
719 | graph_t G; | |
720 | std::vector<vertex_t> verts(4); | |
721 | for (int i = 0; i < 4; ++i) | |
722 | verts[i] = add_vertex(Index(i, Name('a' + i)), G); | |
723 | add_edge(verts[1], verts[2], G); | |
724 | add_edge(verts[1], verts[3], G); | |
725 | add_edge(verts[2], verts[1], G); | |
726 | add_edge(verts[3], verts[2], G); | |
727 | add_edge(verts[3], verts[0], G); | |
728 | ||
729 | std::cout << "Graph G:" << std::endl; | |
730 | print_graph(G, get(vertex_name, G)); | |
731 | ||
732 | adjacency_list<> TC; | |
733 | transitive_closure(G, TC); | |
734 | ||
735 | std::cout << std::endl << "Graph G+:" << std::endl; | |
736 | char name[] = "abcd"; | |
737 | print_graph(TC, name); | |
738 | std::cout << std::endl; | |
739 | ||
740 | std::ofstream out("tc-out.dot"); | |
741 | write_graphviz(out, TC, make_label_writer(name)); | |
742 | ||
743 | return 0; | |
744 | } | |
745 | @} | |
746 | ||
747 | \bibliographystyle{abbrv} | |
748 | \bibliography{jtran,ggcl,optimization,generic-programming,cad} | |
749 | ||
750 | \end{document} | |
751 | % LocalWords: Siek Prus Succ typename GraphTC VertexIndexMap const tc typedefs | |
752 | % LocalWords: typedef iterator adjacency SCC num scc CG cg resize SCCs di ch | |
753 | % LocalWords: traversal ith namespace topo inserter gx hy struct pos inf max | |
754 | % LocalWords: rbegin vec si hpp ifndef endif jtran ggcl |