123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754 |
- \documentclass[11pt]{report}
- \input{defs}
- \setlength\overfullrule{5pt}
- \tolerance=10000
- \sloppy
- \hfuzz=10pt
- \makeindex
- \begin{document}
- \title{A Generic Programming Implementation of Transitive Closure}
- \author{Jeremy G. Siek}
- \maketitle
- \section{Introduction}
- This paper documents the implementation of the
- \code{transitive\_closure()} function of the Boost Graph Library. The
- function was implemented by Vladimir Prus and some editing was done by
- Jeremy Siek.
- The algorithm used to implement the \code{transitive\_closure()}
- function is based on the detection of strong components
- \cite{nuutila95, purdom70}. The following discussion describes the
- main ideas of the algorithm and some relevant background theory.
- The \keyword{transitive closure} of a graph $G = (V,E)$ is a graph $G^+
- = (V,E^+)$ such that $E^+$ contains an edge $(u,v)$ if and only if $G$
- contains a path (of at least one edge) from $u$ to $v$. A
- \keyword{successor set} of a vertex $v$, denoted by $Succ(v)$, is the
- set of vertices that are reachable from vertex $v$. The set of
- vertices adjacent to $v$ in the transitive closure $G^+$ is the same as
- the successor set of $v$ in the original graph $G$. Computing the
- transitive closure is equivalent to computing the successor set for
- every vertex in $G$.
- 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.
- A \keyword{condensation graph} is a a graph $G'=(V',E')$ based on the
- graph $G=(V,E)$ where each vertex in $V'$ corresponds to a strongly
- connected component in $G$ and the edge $(s,t)$ is in $E'$ if and only
- if there exists an edge in $E$ connecting any of the vertices in the
- component of $s$ to any of the vertices in the component of $t$.
- \section{The Implementation}
- The following is the interface and outline of the function:
- @d Transitive Closure Function
- @{
- 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)
- {
- if (num_vertices(g) == 0) return;
- @<Some type definitions@>
- @<Concept checking@>
- @<Compute strongly connected components of the graph@>
- @<Construct the condensation graph (version 2)@>
- @<Compute transitive closure on the condensation graph@>
- @<Build transitive closure of the original graph@>
- }
- @}
- The parameter \code{g} is the input graph and the parameter \code{tc}
- is the output graph that will contain the transitive closure of
- \code{g}. The \code{g\_to\_tc\_map} maps vertices in the input graph
- to the new vertices in the output transitive closure. The
- \code{index\_map} maps vertices in the input graph to the integers
- zero to \code{num\_vertices(g) - 1}.
- There are two alternate interfaces for the transitive closure
- function. The following is the version where defaults are used for
- both the \code{g\_to\_tc\_map} and the \code{index\_map}.
- @d The All Defaults Interface
- @{
- template <typename Graph, typename GraphTC>
- void transitive_closure(const Graph& g, GraphTC& tc)
- {
- if (num_vertices(g) == 0) return;
- typedef typename property_map<Graph, vertex_index_t>::const_type
- VertexIndexMap;
- VertexIndexMap index_map = get(vertex_index, g);
- typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
- std::vector<tc_vertex> to_tc_vec(num_vertices(g));
- iterator_property_map<tc_vertex*, VertexIndexMap>
- g_to_tc_map(&to_tc_vec[0], index_map);
- transitive_closure(g, tc, g_to_tc_map, index_map);
- }
- @}
- \noindent The following alternate interface uses the named parameter
- trick for specifying the parameters. The named parameter functions to
- use in creating the \code{params} argument are
- \code{vertex\_index(VertexIndexMap index\_map)} and
- \code{orig\_to\_copy(G\_to\_TC\_VertexMap g\_to\_tc\_map)}.
- @d The Named Parameter Interface
- @{
- 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)
- {
- if (num_vertices(g) == 0) return;
- detail::transitive_closure_dispatch(g, tc,
- get_param(params, orig_to_copy),
- choose_const_pmap(get_param(params, vertex_index), g, vertex_index)
- );
- }
- @}
- \noindent This dispatch function is used to handle the logic for
- deciding between a user-provided graph to transitive closure vertex
- mapping or to use the default, a vector, to map between the two.
- @d Construct Default G to TC Vertex Mapping
- @{
- namespace detail {
- template <typename Graph, typename GraphTC,
- typename G_to_TC_VertexMap,
- typename VertexIndexMap>
- void transitive_closure_dispatch
- (const Graph& g, GraphTC& tc,
- G_to_TC_VertexMap g_to_tc_map,
- VertexIndexMap index_map)
- {
- typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
- typename std::vector<tc_vertex>::size_type
- n = is_default_param(g_to_tc_map) ? num_vertices(g) : 1;
- std::vector<tc_vertex> to_tc_vec(n);
- transitive_closure
- (g, tc,
- choose_param(g_to_tc_map, make_iterator_property_map
- (to_tc_vec.begin(), index_map, to_tc_vec[0])),
- index_map);
- }
- } // namespace detail
- @}
- The following statements check to make sure that the template
- parameters \emph{model} the concepts that are required for this
- algorithm.
- @d Concept checking
- @{
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( VertexMutableGraphConcept<GraphTC> ));
- BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept<GraphTC> ));
- BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<VertexIndexMap, vertex> ));
- @}
- \noindent To simplify the code in the rest of the function we make the
- following typedefs.
- @d Some type definitions
- @{
- typedef typename graph_traits<Graph>::vertex_descriptor vertex;
- typedef typename graph_traits<Graph>::edge_descriptor edge;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename property_traits<VertexIndexMap>::value_type size_type;
- typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
- @}
- The first step of the algorithm is to compute which vertices are in
- each strongly connected component (SCC) of the graph. This is done
- with the \code{strong\_components()} function. The result of this
- function is stored in the \code{component\_number} array which maps
- each vertex to the number of the SCC to which it belongs (the
- components are numbered zero through \code{num\_scc}). We will use
- the SCC numbers for vertices in the condensation graph (CG), so we use
- the same integer type \code{cg\_vertex} for both.
- @d Compute strongly connected components of the graph
- @{
- typedef size_type cg_vertex;
- std::vector<cg_vertex> component_number_vec(num_vertices(g));
- iterator_property_map<cg_vertex*, VertexIndexMap>
- component_number(&component_number_vec[0], index_map);
- int num_scc = strong_components(g, component_number,
- vertex_index_map(index_map));
- std::vector< std::vector<vertex> > components;
- build_component_lists(g, num_scc, component_number, components);
- @}
- \noindent Later we will need efficient access to all vertices in the
- same SCC so we create a \code{std::vector} of vertices for each SCC
- and fill it in with the \code{build\_components\_lists()} function
- from \code{strong\_components.hpp}.
- The next step is to construct the condensation graph. There will be
- one vertex in the CG for every strongly connected component in the
- original graph. We will add an edge to the CG whenever there is one or
- more edges in the original graph that has its source in one SCC and
- its target in another SCC. The data structure we will use for the CG
- is an adjacency-list with a \code{std::set} for each out-edge list. We
- use \code{std::set} because it will automatically discard parallel
- edges. This makes the code simpler since we can just call
- \code{insert()} every time there is an edge connecting two SCCs in the
- original graph.
- @d Construct the condensation graph (version 1)
- @{
- typedef std::vector< std::set<cg_vertex> > CG_t;
- CG_t CG(num_scc);
- for (cg_vertex s = 0; s < components.size(); ++s) {
- for (size_type i = 0; i < components[s].size(); ++i) {
- vertex u = components[s][i];
- adjacency_iterator vi, vi_end;
- for (tie(vi, vi_end) = adjacent_vertices(u, g); vi != vi_end; ++vi) {
- cg_vertex t = component_number[*vi];
- if (s != t) // Avoid loops in the condensation graph
- CG[s].insert(t); // add edge (s,t) to the condensation graph
- }
- }
- }
- @}
- Inserting into a \code{std::set} and iterator traversal for
- \code{std::set} is a bit slow. We can get better performance if we use
- \code{std::vector} and then explicitly remove duplicated vertices from
- the out-edge lists. Here is the construction of the condensation graph
- rewritten to use \code{std::vector}.
- @d Construct the condensation graph (version 2)
- @{
- typedef std::vector< std::vector<cg_vertex> > CG_t;
- CG_t CG(num_scc);
- for (cg_vertex s = 0; s < components.size(); ++s) {
- std::vector<cg_vertex> adj;
- for (size_type i = 0; i < components[s].size(); ++i) {
- vertex u = components[s][i];
- adjacency_iterator v, v_end;
- for (tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) {
- cg_vertex t = component_number[*v];
- if (s != t) // Avoid loops in the condensation graph
- adj.push_back(t);
- }
- }
- std::sort(adj.begin(), adj.end());
- std::vector<cg_vertex>::iterator di = std::unique(adj.begin(), adj.end());
- if (di != adj.end())
- adj.erase(di, adj.end());
- CG[s] = adj;
- }
- @}
- Next we compute the transitive closure of the condensation graph. The
- basic outline of the algorithm is below. The vertices are considered
- in reverse topological order to ensure that the when computing the
- successor set for a vertex $u$, the successor set for each vertex in
- $Adj[u]$ has already been computed. The successor set for a vertex $u$
- can then be constructed by taking the union of the successor sets for
- all of its adjacent vertices together with the adjacent vertices
- themselves.
- \begin{tabbing}
- \textbf{for} \= ea\=ch \= vertex $u$ in $G'$ in reverse topological order \\
- \>\textbf{for} each vertex $v$ in $Adj[u]$ \\
- \>\>if ($v \notin Succ(u)$) \\
- \>\>\>$Succ(u)$ := $Succ(u) \cup \{ v \} \cup Succ(v)$
- \end{tabbing}
- An optimized implementation of the set union operation improves the
- performance of the algorithm. Therefore this implementation uses
- \keyword{chain decomposition}\cite{goral79,simon86}. The vertices of
- $G$ are partitioned into chains $Z_1, ..., Z_k$, where each chain
- $Z_i$ is a path in $G$ and the vertices in a chain have increasing
- topological number. A successor set $S$ is then represented by a
- collection of intersections with the chains, i.e., $S =
- \bigcup_{i=1 \ldots k} (Z_i \cap S)$. Each intersection can be represented
- by the first vertex in the path $Z_i$ that is also in $S$, since the
- rest of the path is guaranteed to also be in $S$. The collection of
- intersections is therefore represented by a vector of length $k$ where
- the $i$th element of the vector stores the first vertex in the
- intersection of $S$ with $Z_i$.
- Computing the union of two successor sets, $S_3 = S_1 \cup S_2$, can
- then be computed in $O(k)$ time with the below operation. We will
- represent the successor sets by vectors of integers where the integers
- are the topological numbers for the vertices in the set.
- @d Union of successor sets
- @{
- namespace detail {
- inline void
- union_successor_sets(const std::vector<std::size_t>& s1,
- const std::vector<std::size_t>& s2,
- std::vector<std::size_t>& s3)
- {
- for (std::size_t k = 0; k < s1.size(); ++k)
- s3[k] = std::min(s1[k], s2[k]);
- }
- } // namespace detail
- @}
- So to compute the transitive closure we must first sort the graph by
- topological number and then decompose the graph into chains. Once
- that is accomplished we can enter the main loop and begin computing
- the successor sets.
- @d Compute transitive closure on the condensation graph
- @{
- @<Compute topological number for each vertex@>
- @<Sort the out-edge lists by topological number@>
- @<Decompose the condensation graph into chains@>
- @<Compute successor sets@>
- @<Build the transitive closure of the condensation graph@>
- @}
- The \code{topological\_sort()} function is called to obtain a list of
- vertices in topological order and then we use this ordering to assign
- topological numbers to the vertices.
- @d Compute topological number for each vertex
- @{
- std::vector<cg_vertex> topo_order;
- std::vector<cg_vertex> topo_number(num_vertices(CG));
- topological_sort(CG, std::back_inserter(topo_order),
- vertex_index_map(identity_property_map()));
- std::reverse(topo_order.begin(), topo_order.end());
- size_type n = 0;
- for (std::vector<cg_vertex>::iterator i = topo_order.begin();
- i != topo_order.end(); ++i)
- topo_number[*i] = n++;
- @}
- Next we sort the out-edge lists of the condensation graph by
- topological number. This is needed for computing the chain
- decomposition, for each the vertices in a chain must be in topological
- order and we will be adding vertices to the chains from the out-edge
- lists. The \code{subscript()} function creates a function object that
- returns the topological number of its input argument.
- @d Sort the out-edge lists by topological number
- @{
- for (size_type i = 0; i < num_vertices(CG); ++i)
- std::sort(CG[i].begin(), CG[i].end(),
- compose_f_gx_hy(std::less<cg_vertex>(),
- detail::subscript(topo_number),
- detail::subscript(topo_number)));
- @}
- Here is the code that defines the \code{subscript\_t} function object
- and its associated helper object generation function.
- @d Subscript function object
- @{
- namespace detail {
- template <typename Container, typename ST = std::size_t,
- typename VT = typename Container::value_type>
- struct subscript_t : public std::unary_function<ST, VT> {
- subscript_t(Container& c) : container(&c) { }
- VT& operator()(const ST& i) const { return (*container)[i]; }
- protected:
- Container *container;
- };
- template <typename Container>
- subscript_t<Container> subscript(Container& c)
- { return subscript_t<Container>(c); }
- } // namespace detail
- @}
- Now we are ready to decompose the condensation graph into chains. The
- idea is that we want to form lists of vertices that are in a path and
- that the vertices in the list should be ordered by topological number.
- These lists will be stored in the \code{chains} vector below. To
- create the chains we consider each vertex in the graph in topological
- order. If the vertex is not already in a chain then it will be the
- start of a new chain. We then follow a path from this vertex to extend
- the chain.
- @d Decompose the condensation graph into chains
- @{
- std::vector< std::vector<cg_vertex> > chains;
- {
- std::vector<cg_vertex> in_a_chain(num_vertices(CG));
- for (std::vector<cg_vertex>::iterator i = topo_order.begin();
- i != topo_order.end(); ++i) {
- cg_vertex v = *i;
- if (!in_a_chain[v]) {
- chains.resize(chains.size() + 1);
- std::vector<cg_vertex>& chain = chains.back();
- for (;;) {
- @<Extend the chain until the path dead-ends@>
- }
- }
- }
- }
- @<Record the chain number and chain position for each vertex@>
- @}
- \noindent To extend the chain we pick an adjacent vertex that is not
- already in a chain. Also, the adjacent vertex chosen will be the one
- with lowest topological number since the out-edges of \code{CG} are in
- topological order.
- @d Extend the chain until the path dead-ends
- @{
- chain.push_back(v);
- in_a_chain[v] = true;
- graph_traits<CG_t>::adjacency_iterator adj_first, adj_last;
- tie(adj_first, adj_last) = adjacent_vertices(v, CG);
- graph_traits<CG_t>::adjacency_iterator next
- = std::find_if(adj_first, adj_last, not1(detail::subscript(in_a_chain)));
- if (next != adj_last)
- v = *next;
- else
- break; // end of chain, dead-end
- @}
- In the next steps of the algorithm we will need to efficiently find
- the chain for a vertex and the position in the chain for a vertex, so
- here we compute this information and store it in two vectors:
- \code{chain\_number} and \code{pos\_in\_chain}.
- @d Record the chain number and chain position for each vertex
- @{
- std::vector<size_type> chain_number(num_vertices(CG));
- std::vector<size_type> pos_in_chain(num_vertices(CG));
- for (size_type i = 0; i < chains.size(); ++i)
- for (size_type j = 0; j < chains[i].size(); ++j) {
- cg_vertex v = chains[i][j];
- chain_number[v] = i;
- pos_in_chain[v] = j;
- }
- @}
- Now that we have completed the chain decomposition we are ready to
- write the main loop for computing the transitive closure of the
- condensation graph. The output of this will be a successor set for
- each vertex. Remember that the successor set is stored as a collection
- of intersections with the chains. Each successor set is represented by
- a vector where the $i$th element is the representative vertex for the
- intersection of the set with the $i$th chain. We compute the successor
- sets for every vertex in decreasing topological order. The successor
- set for each vertex is the union of the successor sets of the adjacent
- vertex plus the adjacent vertices themselves.
- @d Compute successor sets
- @{
- cg_vertex inf = std::numeric_limits<cg_vertex>::max();
- std::vector< std::vector<cg_vertex> > successors(num_vertices(CG),
- std::vector<cg_vertex>(chains.size(), inf));
- for (std::vector<cg_vertex>::reverse_iterator i = topo_order.rbegin();
- i != topo_order.rend(); ++i) {
- cg_vertex u = *i;
- graph_traits<CG_t>::adjacency_iterator adj, adj_last;
- for (tie(adj, adj_last) = adjacent_vertices(u, CG);
- adj != adj_last; ++adj) {
- cg_vertex v = *adj;
- if (topo_number[v] < successors[u][chain_number[v]]) {
- // Succ(u) = Succ(u) U Succ(v)
- detail::union_successor_sets(successors[u], successors[v],
- successors[u]);
- // Succ(u) = Succ(u) U {v}
- successors[u][chain_number[v]] = topo_number[v];
- }
- }
- }
- @}
- We now rebuild the condensation graph, adding in edges to connect each
- vertex to every vertex in its successor set, thereby obtaining the
- transitive closure. The successor set vectors contain topological
- numbers, so we map back to vertices using the \code{topo\_order}
- vector.
- @d Build the transitive closure of the condensation graph
- @{
- for (size_type i = 0; i < CG.size(); ++i)
- CG[i].clear();
- for (size_type i = 0; i < CG.size(); ++i)
- for (size_type j = 0; j < chains.size(); ++j) {
- size_type topo_num = successors[i][j];
- if (topo_num < inf) {
- cg_vertex v = topo_order[topo_num];
- for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
- CG[i].push_back(chains[j][k]);
- }
- }
- @}
- The last stage is to create the transitive closure graph $G^+$ based on
- the transitive closure of the condensation graph $G'^+$. We do this in
- two steps. First we add edges between all the vertices in one SCC to
- all the vertices in another SCC when the two SCCs are adjacent in the
- condensation graph. Second we add edges to connect each vertex in a
- SCC to every other vertex in the SCC.
- @d Build transitive closure of the original graph
- @{
- // Add vertices to the transitive closure graph
- typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
- {
- vertex_iterator i, i_end;
- for (tie(i, i_end) = vertices(g); i != i_end; ++i)
- g_to_tc_map[*i] = add_vertex(tc);
- }
- // Add edges between all the vertices in two adjacent SCCs
- graph_traits<CG_t>::vertex_iterator si, si_end;
- for (tie(si, si_end) = vertices(CG); si != si_end; ++si) {
- cg_vertex s = *si;
- graph_traits<CG_t>::adjacency_iterator i, i_end;
- for (tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++i) {
- cg_vertex t = *i;
- for (size_type k = 0; k < components[s].size(); ++k)
- for (size_type l = 0; l < components[t].size(); ++l)
- add_edge(g_to_tc_map[components[s][k]],
- g_to_tc_map[components[t][l]], tc);
- }
- }
- // Add edges connecting all vertices in a SCC
- for (size_type i = 0; i < components.size(); ++i)
- if (components[i].size() > 1)
- for (size_type k = 0; k < components[i].size(); ++k)
- for (size_type l = 0; l < components[i].size(); ++l) {
- vertex u = components[i][k], v = components[i][l];
- add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
- }
- // Find loopbacks in the original graph.
- // Need to add it to transitive closure.
- {
- vertex_iterator i, i_end;
- for (tie(i, i_end) = vertices(g); i != i_end; ++i)
- {
- adjacency_iterator ab, ae;
- for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
- {
- if (*ab == *i)
- if (components[component_number[*i]].size() == 1)
- add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
- }
- }
- }
- @}
- \section{Appendix}
- @d Warshall Transitive Closure
- @{
- template <typename G>
- void warshall_transitive_closure(G& g)
- {
- typedef typename graph_traits<G>::vertex_descriptor vertex;
- typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
- BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<G> ));
- BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept<G> ));
- // Matrix form:
- // for k
- // for i
- // if A[i,k]
- // for j
- // A[i,j] = A[i,j] | A[k,j]
- vertex_iterator ki, ke, ii, ie, ji, je;
- for (tie(ki, ke) = vertices(g); ki != ke; ++ki)
- for (tie(ii, ie) = vertices(g); ii != ie; ++ii)
- if (edge(*ii, *ki, g).second)
- for (tie(ji, je) = vertices(g); ji != je; ++ji)
- if (!edge(*ii, *ji, g).second &&
- edge(*ki, *ji, g).second)
- {
- add_edge(*ii, *ji, g);
- }
- }
- @}
- @d Warren Transitive Closure
- @{
- template <typename G>
- void warren_transitive_closure(G& g)
- {
- using namespace boost;
- typedef typename graph_traits<G>::vertex_descriptor vertex;
- typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
- BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<G> ));
- BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept<G> ));
- // Make sure second loop will work
- if (num_vertices(g) == 0)
- return;
- // for i = 2 to n
- // for k = 1 to i - 1
- // if A[i,k]
- // for j = 1 to n
- // A[i,j] = A[i,j] | A[k,j]
- vertex_iterator ic, ie, jc, je, kc, ke;
- for (tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic)
- for (tie(kc, ke) = vertices(g); *kc != *ic; ++kc)
- if (edge(*ic, *kc, g).second)
- for (tie(jc, je) = vertices(g); jc != je; ++jc)
- if (!edge(*ic, *jc, g).second &&
- edge(*kc, *jc, g).second)
- {
- add_edge(*ic, *jc, g);
- }
- // for i = 1 to n - 1
- // for k = i + 1 to n
- // if A[i,k]
- // for j = 1 to n
- // A[i,j] = A[i,j] | A[k,j]
- for (tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic)
- for (kc = ic, ke = ie, ++kc; kc != ke; ++kc)
- if (edge(*ic, *kc, g).second)
- for (tie(jc, je) = vertices(g); jc != je; ++jc)
- if (!edge(*ic, *jc, g).second &&
- edge(*kc, *jc, g).second)
- {
- add_edge(*ic, *jc, g);
- }
- }
- @}
- The following indent command was run on the output files before
- they were checked into the Boost CVS repository.
- @e indentation
- @{
- indent -nut -npcs -i2 -br -cdw -ce transitive_closure.hpp
- @}
- @o transitive_closure.hpp
- @{
- // Copyright (C) 2001 Vladimir Prus <ghost@@cs.msu.su>
- // Copyright (C) 2001 Jeremy Siek <jsiek@@cs.indiana.edu>
- // Permission to copy, use, modify, sell and distribute this software is
- // granted, provided this copyright notice appears in all copies and
- // modified version are clearly marked as such. This software is provided
- // "as is" without express or implied warranty, and with no claim as to its
- // suitability for any purpose.
- // NOTE: this final is generated by libs/graph/doc/transitive_closure.w
- #ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
- #define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
- #include <vector>
- #include <functional>
- #include <boost/compose.hpp>
- #include <boost/graph/vector_as_graph.hpp>
- #include <boost/graph/strong_components.hpp>
- #include <boost/graph/topological_sort.hpp>
- #include <boost/graph/graph_concepts.hpp>
- #include <boost/graph/named_function_params.hpp>
- #include <boost/concept/assert.hpp>
- namespace boost {
- @<Union of successor sets@>
- @<Subscript function object@>
- @<Transitive Closure Function@>
- @<The All Defaults Interface@>
- @<Construct Default G to TC Vertex Mapping@>
- @<The Named Parameter Interface@>
- @<Warshall Transitive Closure@>
- @<Warren Transitive Closure@>
- } // namespace boost
- #endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
- @}
- @o transitive_closure.cpp
- @{
- // Copyright (c) Jeremy Siek 2001
- //
- // Permission to use, copy, modify, distribute and sell this software
- // and its documentation for any purpose is hereby granted without fee,
- // provided that the above copyright notice appears in all copies and
- // that both that copyright notice and this permission notice appear
- // in supporting documentation. Silicon Graphics makes no
- // representations about the suitability of this software for any
- // purpose. It is provided "as is" without express or implied warranty.
- // NOTE: this final is generated by libs/graph/doc/transitive_closure.w
- #include <boost/graph/transitive_closure.hpp>
- #include <boost/graph/graphviz.hpp>
- int main(int, char*[])
- {
- using namespace boost;
- typedef property<vertex_name_t, char> Name;
- typedef property<vertex_index_t, std::size_t,
- Name> Index;
- typedef adjacency_list<listS, listS, directedS, Index> graph_t;
- typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
- graph_t G;
- std::vector<vertex_t> verts(4);
- for (int i = 0; i < 4; ++i)
- verts[i] = add_vertex(Index(i, Name('a' + i)), G);
- add_edge(verts[1], verts[2], G);
- add_edge(verts[1], verts[3], G);
- add_edge(verts[2], verts[1], G);
- add_edge(verts[3], verts[2], G);
- add_edge(verts[3], verts[0], G);
- std::cout << "Graph G:" << std::endl;
- print_graph(G, get(vertex_name, G));
- adjacency_list<> TC;
- transitive_closure(G, TC);
- std::cout << std::endl << "Graph G+:" << std::endl;
- char name[] = "abcd";
- print_graph(TC, name);
- std::cout << std::endl;
- std::ofstream out("tc-out.dot");
- write_graphviz(out, TC, make_label_writer(name));
- return 0;
- }
- @}
- \bibliographystyle{abbrv}
- \bibliography{jtran,ggcl,optimization,generic-programming,cad}
- \end{document}
- % LocalWords: Siek Prus Succ typename GraphTC VertexIndexMap const tc typedefs
- % LocalWords: typedef iterator adjacency SCC num scc CG cg resize SCCs di ch
- % LocalWords: traversal ith namespace topo inserter gx hy struct pos inf max
- % LocalWords: rbegin vec si hpp ifndef endif jtran ggcl
|