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