]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | { | |
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(s1[k], 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(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 | 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(successors[u], successors[v], | |
189 | 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 > ¶ms) | |
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 |