1// Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
2// Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
3// Distributed under the Boost Software License, Version 1.0. (See
4// accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7// NOTE: this final is generated by libs/graph/doc/transitive_closure.w
8
9#ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
10#define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
11
12#include <vector>
13#include <algorithm> // for std::min and std::max
14#include <functional>
15#include <boost/config.hpp>
16#include <boost/bind.hpp>
17#include <boost/graph/strong_components.hpp>
18#include <boost/graph/topological_sort.hpp>
19#include <boost/graph/graph_concepts.hpp>
20#include <boost/graph/named_function_params.hpp>
21#include <boost/graph/adjacency_list.hpp>
22#include <boost/concept/assert.hpp>
23
24namespace boost
25{
26
27 namespace detail
28 {
29 inline void
30 union_successor_sets(const std::vector < std::size_t > &s1,
31 const std::vector < std::size_t > &s2,
32 std::vector < std::size_t > &s3)
33 {
34 BOOST_USING_STD_MIN();
35 for (std::size_t k = 0; k < s1.size(); ++k)
36 s3[k] = min BOOST_PREVENT_MACRO_SUBSTITUTION(a: s1[k], b: s2[k]);
37 }
38 } // namespace detail
39
40 namespace detail
41 {
42 template < typename TheContainer, typename ST = std::size_t,
43 typename VT = typename TheContainer::value_type >
44 struct subscript_t:public std::unary_function < ST, VT >
45 {
46 typedef VT& result_type;
47
48 subscript_t(TheContainer & c):container(&c)
49 {
50 }
51 VT & operator() (const ST & i) const
52 {
53 return (*container)[i];
54 }
55 protected:
56 TheContainer * container;
57 };
58 template < typename TheContainer >
59 subscript_t < TheContainer > subscript(TheContainer & c) {
60 return subscript_t < TheContainer > (c);
61 }
62 } // namespace detail
63
64 template < typename Graph, typename GraphTC,
65 typename G_to_TC_VertexMap,
66 typename VertexIndexMap >
67 void transitive_closure(const Graph & g, GraphTC & tc,
68 G_to_TC_VertexMap g_to_tc_map,
69 VertexIndexMap index_map)
70 {
71 if (num_vertices(g) == 0)
72 return;
73 typedef typename graph_traits < Graph >::vertex_descriptor vertex;
74 typedef typename graph_traits < Graph >::vertex_iterator vertex_iterator;
75 typedef typename property_traits < VertexIndexMap >::value_type size_type;
76 typedef typename graph_traits <
77 Graph >::adjacency_iterator adjacency_iterator;
78
79 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept < Graph > ));
80 BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept < Graph > ));
81 BOOST_CONCEPT_ASSERT(( VertexMutableGraphConcept < GraphTC > ));
82 BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept < GraphTC > ));
83 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept < VertexIndexMap,
84 vertex > ));
85
86 typedef size_type cg_vertex;
87 std::vector < cg_vertex > component_number_vec(num_vertices(g));
88 iterator_property_map < cg_vertex *, VertexIndexMap, cg_vertex, cg_vertex& >
89 component_number(&component_number_vec[0], index_map);
90
91 int num_scc = strong_components(g, component_number,
92 vertex_index_map(index_map));
93
94 std::vector < std::vector < vertex > >components;
95 build_component_lists(g, num_scc, component_number, components);
96
97 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> CG_t;
98 CG_t CG(num_scc);
99 for (cg_vertex s = 0; s < components.size(); ++s) {
100 std::vector < cg_vertex > adj;
101 for (size_type i = 0; i < components[s].size(); ++i) {
102 vertex u = components[s][i];
103 adjacency_iterator v, v_end;
104 for (boost::tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) {
105 cg_vertex t = component_number[*v];
106 if (s != t) // Avoid loops in the condensation graph
107 adj.push_back(t);
108 }
109 }
110 std::sort(adj.begin(), adj.end());
111 typename std::vector<cg_vertex>::iterator di =
112 std::unique(adj.begin(), adj.end());
113 if (di != adj.end())
114 adj.erase(di, adj.end());
115 for (typename std::vector<cg_vertex>::const_iterator i = adj.begin();
116 i != adj.end(); ++i) {
117 add_edge(s, *i, CG);
118 }
119 }
120
121 std::vector<cg_vertex> topo_order;
122 std::vector<cg_vertex> topo_number(num_vertices(g_: CG));
123 topological_sort(CG, std::back_inserter(topo_order),
124 vertex_index_map(p: identity_property_map()));
125 std::reverse(topo_order.begin(), topo_order.end());
126 size_type n = 0;
127 for (typename std::vector<cg_vertex>::iterator iter = topo_order.begin();
128 iter != topo_order.end(); ++iter)
129 topo_number[*iter] = n++;
130
131 std::vector<std::vector<cg_vertex> > CG_vec(num_vertices(g_: CG));
132 for (size_type i = 0; i < num_vertices(g_: CG); ++i) {
133 typedef typename boost::graph_traits<CG_t>::adjacency_iterator cg_adj_iter;
134 std::pair<cg_adj_iter, cg_adj_iter> pr = adjacent_vertices(i, CG);
135 CG_vec[i].assign(pr.first, pr.second);
136 std::sort(CG_vec[i].begin(), CG_vec[i].end(),
137 boost::bind(std::less<cg_vertex>(),
138 boost::bind(detail::subscript(topo_number), _1),
139 boost::bind(detail::subscript(topo_number), _2)));
140 }
141
142 std::vector<std::vector<cg_vertex> > chains;
143 {
144 std::vector<cg_vertex> in_a_chain(CG_vec.size());
145 for (typename std::vector<cg_vertex>::iterator i = topo_order.begin();
146 i != topo_order.end(); ++i) {
147 cg_vertex v = *i;
148 if (!in_a_chain[v]) {
149 chains.resize(chains.size() + 1);
150 std::vector<cg_vertex>& chain = chains.back();
151 for (;;) {
152 chain.push_back(v);
153 in_a_chain[v] = true;
154 typename std::vector<cg_vertex>::const_iterator next
155 = std::find_if(CG_vec[v].begin(), CG_vec[v].end(),
156 std::not1(detail::subscript(in_a_chain)));
157 if (next != CG_vec[v].end())
158 v = *next;
159 else
160 break; // end of chain, dead-end
161
162 }
163 }
164 }
165 }
166 std::vector<size_type> chain_number(CG_vec.size());
167 std::vector<size_type> pos_in_chain(CG_vec.size());
168 for (size_type i = 0; i < chains.size(); ++i)
169 for (size_type j = 0; j < chains[i].size(); ++j) {
170 cg_vertex v = chains[i][j];
171 chain_number[v] = i;
172 pos_in_chain[v] = j;
173 }
174
175 cg_vertex inf = (std::numeric_limits< cg_vertex >::max)();
176 std::vector<std::vector<cg_vertex> > successors(CG_vec.size(),
177 std::vector<cg_vertex>
178 (chains.size(), inf));
179 for (typename std::vector<cg_vertex>::reverse_iterator
180 i = topo_order.rbegin(); i != topo_order.rend(); ++i) {
181 cg_vertex u = *i;
182 typename std::vector<cg_vertex>::const_iterator adj, adj_last;
183 for (adj = CG_vec[u].begin(), adj_last = CG_vec[u].end();
184 adj != adj_last; ++adj) {
185 cg_vertex v = *adj;
186 if (topo_number[v] < successors[u][chain_number[v]]) {
187 // Succ(u) = Succ(u) U Succ(v)
188 detail::union_successor_sets(s1: successors[u], s2: successors[v],
189 s3&: successors[u]);
190 // Succ(u) = Succ(u) U {v}
191 successors[u][chain_number[v]] = topo_number[v];
192 }
193 }
194 }
195
196 for (size_type i = 0; i < CG_vec.size(); ++i)
197 CG_vec[i].clear();
198 for (size_type i = 0; i < CG_vec.size(); ++i)
199 for (size_type j = 0; j < chains.size(); ++j) {
200 size_type topo_num = successors[i][j];
201 if (topo_num < inf) {
202 cg_vertex v = topo_order[topo_num];
203 for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
204 CG_vec[i].push_back(chains[j][k]);
205 }
206 }
207
208
209 // Add vertices to the transitive closure graph
210 {
211 vertex_iterator i, i_end;
212 for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
213 g_to_tc_map[*i] = add_vertex(tc);
214 }
215 // Add edges between all the vertices in two adjacent SCCs
216 typename std::vector<std::vector<cg_vertex> >::const_iterator si, si_end;
217 for (si = CG_vec.begin(), si_end = CG_vec.end(); si != si_end; ++si) {
218 cg_vertex s = si - CG_vec.begin();
219 typename std::vector<cg_vertex>::const_iterator i, i_end;
220 for (i = CG_vec[s].begin(), i_end = CG_vec[s].end(); i != i_end; ++i) {
221 cg_vertex t = *i;
222 for (size_type k = 0; k < components[s].size(); ++k)
223 for (size_type l = 0; l < components[t].size(); ++l)
224 add_edge(g_to_tc_map[components[s][k]],
225 g_to_tc_map[components[t][l]], tc);
226 }
227 }
228 // Add edges connecting all vertices in a SCC
229 for (size_type i = 0; i < components.size(); ++i)
230 if (components[i].size() > 1)
231 for (size_type k = 0; k < components[i].size(); ++k)
232 for (size_type l = 0; l < components[i].size(); ++l) {
233 vertex u = components[i][k], v = components[i][l];
234 add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
235 }
236
237 // Find loopbacks in the original graph.
238 // Need to add it to transitive closure.
239 {
240 vertex_iterator i, i_end;
241 for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
242 {
243 adjacency_iterator ab, ae;
244 for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
245 {
246 if (*ab == *i)
247 if (components[component_number[*i]].size() == 1)
248 add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
249 }
250 }
251 }
252 }
253
254 template <typename Graph, typename GraphTC>
255 void transitive_closure(const Graph & g, GraphTC & tc)
256 {
257 if (num_vertices(g) == 0)
258 return;
259 typedef typename property_map<Graph, vertex_index_t>::const_type
260 VertexIndexMap;
261 VertexIndexMap index_map = get(vertex_index, g);
262
263 typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
264 std::vector<tc_vertex> to_tc_vec(num_vertices(g));
265 iterator_property_map < tc_vertex *, VertexIndexMap, tc_vertex, tc_vertex&>
266 g_to_tc_map(&to_tc_vec[0], index_map);
267
268 transitive_closure(g, tc, g_to_tc_map, index_map);
269 }
270
271 namespace detail
272 {
273 template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap,
274 typename VertexIndexMap>
275 void transitive_closure_dispatch
276 (const Graph & g, GraphTC & tc,
277 G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
278 {
279 typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex;
280 typename std::vector < tc_vertex >::size_type
281 n = is_default_param(g_to_tc_map) ? num_vertices(g) : 1;
282 std::vector < tc_vertex > to_tc_vec(n);
283
284 transitive_closure
285 (g, tc,
286 choose_param(g_to_tc_map, make_iterator_property_map
287 (to_tc_vec.begin(), index_map, to_tc_vec[0])),
288 index_map);
289 }
290 } // namespace detail
291
292 template < typename Graph, typename GraphTC,
293 typename P, typename T, typename R >
294 void transitive_closure(const Graph & g, GraphTC & tc,
295 const bgl_named_params < P, T, R > &params)
296 {
297 if (num_vertices(g) == 0)
298 return;
299 detail::transitive_closure_dispatch
300 (g, tc, get_param(params, orig_to_copy_t()),
301 choose_const_pmap(get_param(params, vertex_index), g, vertex_index) );
302 }
303
304
305 template < typename G > void warshall_transitive_closure(G & g)
306 {
307 typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
308
309 BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept < G > ));
310 BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept < G > ));
311
312 // Matrix form:
313 // for k
314 // for i
315 // if A[i,k]
316 // for j
317 // A[i,j] = A[i,j] | A[k,j]
318 vertex_iterator ki, ke, ii, ie, ji, je;
319 for (boost::tie(ki, ke) = vertices(g); ki != ke; ++ki)
320 for (boost::tie(ii, ie) = vertices(g); ii != ie; ++ii)
321 if (edge(*ii, *ki, g).second)
322 for (boost::tie(ji, je) = vertices(g); ji != je; ++ji)
323 if (!edge(*ii, *ji, g).second && edge(*ki, *ji, g).second) {
324 add_edge(*ii, *ji, g);
325 }
326 }
327
328
329 template < typename G > void warren_transitive_closure(G & g)
330 {
331 using namespace boost;
332 typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
333
334 BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept < G > ));
335 BOOST_CONCEPT_ASSERT(( EdgeMutableGraphConcept < G > ));
336
337 // Make sure second loop will work
338 if (num_vertices(g) == 0)
339 return;
340
341 // for i = 2 to n
342 // for k = 1 to i - 1
343 // if A[i,k]
344 // for j = 1 to n
345 // A[i,j] = A[i,j] | A[k,j]
346
347 vertex_iterator ic, ie, jc, je, kc, ke;
348 for (boost::tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic)
349 for (boost::tie(kc, ke) = vertices(g); *kc != *ic; ++kc)
350 if (edge(*ic, *kc, g).second)
351 for (boost::tie(jc, je) = vertices(g); jc != je; ++jc)
352 if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) {
353 add_edge(*ic, *jc, g);
354 }
355 // for i = 1 to n - 1
356 // for k = i + 1 to n
357 // if A[i,k]
358 // for j = 1 to n
359 // A[i,j] = A[i,j] | A[k,j]
360
361 for (boost::tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic)
362 for (kc = ic, ke = ie, ++kc; kc != ke; ++kc)
363 if (edge(*ic, *kc, g).second)
364 for (boost::tie(jc, je) = vertices(g); jc != je; ++jc)
365 if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) {
366 add_edge(*ic, *jc, g);
367 }
368 }
369
370
371} // namespace boost
372
373#endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
374

source code of boost/boost/graph/transitive_closure.hpp