1 \documentclass[11pt]{report}
6 \setlength\overfullrule{5pt}
15 \title{A Generic Programming Implementation of Transitive Closure}
16 \author{Jeremy G. Siek}
20 \section{Introduction}
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
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.
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
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.
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$.
54 \section{The Implementation}
56 The following is the interface and outline of the function:
58 @d Transitive Closure Function
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)
67 if (num_vertices(g) == 0) return;
68 @<Some type definitions@>
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@>
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}.
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}.
88 @d The All Defaults Interface
90 template <typename Graph, typename GraphTC>
91 void transitive_closure(const Graph& g, GraphTC& tc)
93 if (num_vertices(g) == 0) return;
94 typedef typename property_map<Graph, vertex_index_t>::const_type
96 VertexIndexMap index_map = get(vertex_index, g);
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);
103 transitive_closure(g, tc, g_to_tc_map, index_map);
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)}.
113 @d The Named Parameter Interface
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)
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)
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.
132 @d Construct Default G to TC Vertex Mapping
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)
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);
150 choose_param(g_to_tc_map, make_iterator_property_map
151 (to_tc_vec.begin(), index_map, to_tc_vec[0])),
154 } // namespace detail
157 The following statements check to make sure that the template
158 parameters \emph{model} the concepts that are required for this
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> ));
170 \noindent To simplify the code in the rest of the function we make the
173 @d Some type definitions
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;
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.
191 @d Compute strongly connected components of the graph
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);
198 int num_scc = strong_components(g, component_number,
199 vertex_index_map(index_map));
201 std::vector< std::vector<vertex> > components;
202 build_component_lists(g, num_scc, component_number, components);
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}.
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
221 @d Construct the condensation graph (version 1)
223 typedef std::vector< std::set<cg_vertex> > CG_t;
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
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}.
244 @d Construct the condensation graph (version 2)
246 typedef std::vector< std::vector<cg_vertex> > CG_t;
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
259 std::sort(adj.begin(), adj.end());
260 std::vector<cg_vertex>::iterator di = std::unique(adj.begin(), adj.end());
262 adj.erase(di, adj.end());
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
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)$
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$.
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.
302 @d Union of successor sets
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)
310 for (std::size_t k = 0; k < s1.size(); ++k)
311 s3[k] = std::min(s1[k], s2[k]);
313 } // namespace detail
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
321 @d Compute transitive closure on the condensation graph
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@>
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.
334 @d Compute topological number for each vertex
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());
342 for (std::vector<cg_vertex>::iterator i = topo_order.begin();
343 i != topo_order.end(); ++i)
344 topo_number[*i] = n++;
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.
354 @d Sort the out-edge lists by topological number
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)));
363 Here is the code that defines the \code{subscript\_t} function object
364 and its associated helper object generation function.
366 @d Subscript function object
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]; }
375 Container *container;
377 template <typename Container>
378 subscript_t<Container> subscript(Container& c)
379 { return subscript_t<Container>(c); }
380 } // namespace detail
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
393 @d Decompose the condensation graph into chains
395 std::vector< std::vector<cg_vertex> > chains;
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) {
401 if (!in_a_chain[v]) {
402 chains.resize(chains.size() + 1);
403 std::vector<cg_vertex>& chain = chains.back();
405 @<Extend the chain until the path dead-ends@>
410 @<Record the chain number and chain position for each vertex@>
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
418 @d Extend the chain until the path dead-ends
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)
429 break; // end of chain, dead-end
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}.
437 @d Record the chain number and chain position for each vertex
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];
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.
460 @d Compute successor sets
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) {
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) {
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],
476 // Succ(u) = Succ(u) U {v}
477 successors[u][chain_number[v]] = topo_number[v];
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}
489 @d Build the transitive closure of the condensation graph
491 for (size_type i = 0; i < CG.size(); ++i)
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]);
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.
511 @d Build transitive closure of the original graph
513 // Add vertices to the transitive closure graph
514 typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
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);
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) {
524 graph_traits<CG_t>::adjacency_iterator i, i_end;
525 for (tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++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);
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);
542 // Find loopbacks in the original graph.
543 // Need to add it to transitive closure.
545 vertex_iterator i, i_end;
546 for (tie(i, i_end) = vertices(g); i != i_end; ++i)
548 adjacency_iterator ab, ae;
549 for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
552 if (components[component_number[*i]].size() == 1)
553 add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
561 @d Warshall Transitive Closure
563 template <typename G>
564 void warshall_transitive_closure(G& g)
566 typedef typename graph_traits<G>::vertex_descriptor vertex;
567 typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
569 BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<G> ));
570 BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept<G> ));
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)
586 add_edge(*ii, *ji, g);
591 @d Warren Transitive Closure
593 template <typename G>
594 void warren_transitive_closure(G& g)
596 using namespace boost;
597 typedef typename graph_traits<G>::vertex_descriptor vertex;
598 typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
600 BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<G> ));
601 BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept<G> ));
603 // Make sure second loop will work
604 if (num_vertices(g) == 0)
608 // for k = 1 to i - 1
611 // A[i,j] = A[i,j] | A[k,j]
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)
621 add_edge(*ic, *jc, g);
624 // for i = 1 to n - 1
625 // for k = i + 1 to n
628 // A[i,j] = A[i,j] | A[k,j]
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)
637 add_edge(*ic, *jc, g);
643 The following indent command was run on the output files before
644 they were checked into the Boost CVS repository.
648 indent -nut -npcs -i2 -br -cdw -ce transitive_closure.hpp
651 @o transitive_closure.hpp
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.
661 // NOTE: this final is generated by libs/graph/doc/transitive_closure.w
663 #ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
664 #define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
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>
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@>
685 @<Warshall Transitive Closure@>
687 @<Warren Transitive Closure@>
691 #endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
694 @o transitive_closure.cpp
696 // Copyright (c) Jeremy Siek 2001
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.
706 // NOTE: this final is generated by libs/graph/doc/transitive_closure.w
708 #include <boost/graph/transitive_closure.hpp>
709 #include <boost/graph/graphviz.hpp>
711 int main(int, char*[])
713 using namespace boost;
714 typedef property<vertex_name_t, char> Name;
715 typedef property<vertex_index_t, std::size_t,
717 typedef adjacency_list<listS, listS, directedS, Index> graph_t;
718 typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
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);
729 std::cout << "Graph G:" << std::endl;
730 print_graph(G, get(vertex_name, G));
733 transitive_closure(G, TC);
735 std::cout << std::endl << "Graph G+:" << std::endl;
736 char name[] = "abcd";
737 print_graph(TC, name);
738 std::cout << std::endl;
740 std::ofstream out("tc-out.dot");
741 write_graphviz(out, TC, make_label_writer(name));
747 \bibliographystyle{abbrv}
748 \bibliography{jtran,ggcl,optimization,generic-programming,cad}
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