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