1 | // Copyright (c) Jeremy Siek 2001 |
2 | // Copyright (c) Douglas Gregor 2004 |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See |
5 | // accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | |
8 | // NOTE: this final is generated by libs/graph/doc/biconnected_components.w |
9 | |
10 | #ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP |
11 | #define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP |
12 | |
13 | #include <stack> |
14 | #include <vector> |
15 | #include <algorithm> // for std::min and std::max |
16 | #include <boost/config.hpp> |
17 | #include <boost/limits.hpp> |
18 | #include <boost/graph/graph_traits.hpp> |
19 | #include <boost/graph/graph_concepts.hpp> |
20 | #include <boost/property_map/property_map.hpp> |
21 | #include <boost/graph/depth_first_search.hpp> |
22 | #include <boost/graph/graph_utility.hpp> |
23 | #include <boost/concept/assert.hpp> |
24 | #include <boost/assert.hpp> |
25 | |
26 | namespace boost |
27 | { |
28 | namespace detail |
29 | { |
30 | template<typename ComponentMap, typename DiscoverTimeMap, |
31 | typename LowPointMap, typename PredecessorMap, |
32 | typename OutputIterator, typename Stack, |
33 | typename ArticulationVector, typename IndexMap, |
34 | typename DFSVisitor> |
35 | struct biconnected_components_visitor : public dfs_visitor<> |
36 | { |
37 | biconnected_components_visitor |
38 | (ComponentMap comp, std::size_t& c, |
39 | std::size_t& children_of_root, DiscoverTimeMap dtm, |
40 | std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred, |
41 | OutputIterator out, Stack& S, |
42 | ArticulationVector& is_articulation_point, IndexMap index_map, |
43 | DFSVisitor vis) |
44 | : comp(comp), c(c), children_of_root(children_of_root), |
45 | dtm(dtm), dfs_time(dfs_time), lowpt(lowpt), |
46 | pred(pred), out(out), S(S), |
47 | is_articulation_point(is_articulation_point), |
48 | index_map(index_map), vis(vis) { } |
49 | |
50 | template <typename Vertex, typename Graph> |
51 | void initialize_vertex(const Vertex& u, Graph& g) |
52 | { |
53 | put(pred, u, u); |
54 | vis.initialize_vertex(u, g); |
55 | } |
56 | |
57 | template <typename Vertex, typename Graph> |
58 | void start_vertex(const Vertex& u, Graph& g) |
59 | { |
60 | children_of_root = 0; |
61 | vis.start_vertex(u, g); |
62 | } |
63 | |
64 | template <typename Vertex, typename Graph> |
65 | void discover_vertex(const Vertex& u, Graph& g) |
66 | { |
67 | put(dtm, u, ++dfs_time); |
68 | put(lowpt, u, get(dtm, u)); |
69 | vis.discover_vertex(u, g); |
70 | } |
71 | |
72 | template <typename Edge, typename Graph> |
73 | void examine_edge(const Edge& e, Graph& g) |
74 | { |
75 | vis.examine_edge(e, g); |
76 | } |
77 | |
78 | template <typename Edge, typename Graph> |
79 | void tree_edge(const Edge& e, Graph& g) |
80 | { |
81 | typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g); |
82 | typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g); |
83 | |
84 | S.push(e); |
85 | put(pred, tgt, src); |
86 | if ( get(pred, src) == src ) { |
87 | ++children_of_root; |
88 | } |
89 | vis.tree_edge(e, g); |
90 | } |
91 | |
92 | template <typename Edge, typename Graph> |
93 | void back_edge(const Edge& e, Graph& g) |
94 | { |
95 | BOOST_USING_STD_MIN(); |
96 | |
97 | typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g); |
98 | typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g); |
99 | if ( tgt != get(pred, src) ) { |
100 | S.push(e); |
101 | put(lowpt, src, |
102 | min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, src), |
103 | get(dtm, tgt))); |
104 | } |
105 | vis.back_edge(e, g); |
106 | } |
107 | |
108 | template <typename Edge, typename Graph> |
109 | void forward_or_cross_edge(const Edge& e, Graph& g) |
110 | { |
111 | vis.forward_or_cross_edge(e, g); |
112 | } |
113 | |
114 | template <typename Vertex, typename Graph> |
115 | void finish_vertex(const Vertex& u, Graph& g) |
116 | { |
117 | BOOST_USING_STD_MIN(); |
118 | Vertex parent = get(pred, u); |
119 | if (parent == u) { // Root of tree is special |
120 | is_articulation_point[get(index_map, u)] = (children_of_root > 1); |
121 | } else { |
122 | put(lowpt, parent, |
123 | min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent), |
124 | get(lowpt, u))); |
125 | if ( get(lowpt, u) >= get(dtm, parent) ) { |
126 | is_articulation_point[get(index_map, parent)] = true; |
127 | while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) { |
128 | put(comp, S.top(), c); |
129 | S.pop(); |
130 | } |
131 | BOOST_ASSERT (source(S.top(), g) == parent); |
132 | BOOST_ASSERT (target(S.top(), g) == u); |
133 | put(comp, S.top(), c); |
134 | S.pop(); |
135 | ++c; |
136 | } |
137 | } |
138 | if ( is_articulation_point[get(index_map, u)] ) { |
139 | *out++ = u; |
140 | } |
141 | vis.finish_vertex(u, g); |
142 | } |
143 | |
144 | ComponentMap comp; |
145 | std::size_t& c; |
146 | std::size_t& children_of_root; |
147 | DiscoverTimeMap dtm; |
148 | std::size_t& dfs_time; |
149 | LowPointMap lowpt; |
150 | PredecessorMap pred; |
151 | OutputIterator out; |
152 | Stack& S; |
153 | ArticulationVector& is_articulation_point; |
154 | IndexMap index_map; |
155 | DFSVisitor vis; |
156 | }; |
157 | |
158 | template<typename Graph, typename ComponentMap, typename OutputIterator, |
159 | typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap, |
160 | typename PredecessorMap, typename DFSVisitor> |
161 | std::pair<std::size_t, OutputIterator> |
162 | biconnected_components_impl(const Graph & g, ComponentMap comp, |
163 | OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, |
164 | LowPointMap lowpt, PredecessorMap pred, DFSVisitor dfs_vis) |
165 | { |
166 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
167 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; |
168 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); |
169 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); |
170 | BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, edge_t> )); |
171 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<DiscoverTimeMap, |
172 | vertex_t> )); |
173 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<LowPointMap, vertex_t > )); |
174 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<PredecessorMap, |
175 | vertex_t> )); |
176 | |
177 | std::size_t num_components = 0; |
178 | std::size_t children_of_root; |
179 | std::size_t dfs_time = 0; |
180 | std::stack<edge_t> S; |
181 | std::vector<char> is_articulation_point(num_vertices(g)); |
182 | |
183 | biconnected_components_visitor<ComponentMap, DiscoverTimeMap, |
184 | LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, |
185 | std::vector<char>, VertexIndexMap, DFSVisitor> |
186 | vis(comp, num_components, children_of_root, dtm, dfs_time, |
187 | lowpt, pred, out, S, is_articulation_point, index_map, dfs_vis); |
188 | |
189 | depth_first_search(g, visitor(vis).vertex_index_map(index_map)); |
190 | |
191 | return std::pair<std::size_t, OutputIterator>(num_components, vis.out); |
192 | } |
193 | |
194 | template <typename PredecessorMap> |
195 | struct bicomp_dispatch3 |
196 | { |
197 | template<typename Graph, typename ComponentMap, typename OutputIterator, |
198 | typename VertexIndexMap, typename DiscoverTimeMap, |
199 | typename LowPointMap, class P, class T, class R> |
200 | static std::pair<std::size_t, OutputIterator> apply (const Graph & g, |
201 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, |
202 | DiscoverTimeMap dtm, LowPointMap lowpt, |
203 | const bgl_named_params<P, T, R>& params, PredecessorMap pred) |
204 | { |
205 | return biconnected_components_impl |
206 | (g, comp, out, index_map, dtm, lowpt, pred, |
207 | choose_param(get_param(params, graph_visitor), |
208 | make_dfs_visitor(vis: null_visitor()))); |
209 | } |
210 | }; |
211 | |
212 | template <> |
213 | struct bicomp_dispatch3<param_not_found> |
214 | { |
215 | template<typename Graph, typename ComponentMap, typename OutputIterator, |
216 | typename VertexIndexMap, typename DiscoverTimeMap, |
217 | typename LowPointMap, class P, class T, class R> |
218 | static std::pair<std::size_t, OutputIterator> apply (const Graph & g, |
219 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, |
220 | DiscoverTimeMap dtm, LowPointMap lowpt, |
221 | const bgl_named_params<P, T, R>& params, |
222 | param_not_found) |
223 | { |
224 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
225 | std::vector<vertex_t> pred(num_vertices(g)); |
226 | vertex_t vert = graph_traits<Graph>::null_vertex(); |
227 | |
228 | return biconnected_components_impl |
229 | (g, comp, out, index_map, dtm, lowpt, |
230 | make_iterator_property_map(pred.begin(), index_map, vert), |
231 | choose_param(get_param(params, graph_visitor), |
232 | make_dfs_visitor(vis: null_visitor()))); |
233 | } |
234 | }; |
235 | |
236 | template <typename LowPointMap> |
237 | struct bicomp_dispatch2 |
238 | { |
239 | template<typename Graph, typename ComponentMap, typename OutputIterator, |
240 | typename VertexIndexMap, typename DiscoverTimeMap, |
241 | typename P, typename T, typename R> |
242 | static std::pair<std::size_t, OutputIterator> apply (const Graph& g, |
243 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, |
244 | DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, |
245 | LowPointMap lowpt) |
246 | { |
247 | typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type; |
248 | |
249 | return bicomp_dispatch3<dispatch_type>::apply |
250 | (g, comp, out, index_map, dtm, lowpt, params, |
251 | get_param(params, vertex_predecessor)); |
252 | } |
253 | }; |
254 | |
255 | |
256 | template <> |
257 | struct bicomp_dispatch2<param_not_found> |
258 | { |
259 | template<typename Graph, typename ComponentMap, typename OutputIterator, |
260 | typename VertexIndexMap, typename DiscoverTimeMap, |
261 | typename P, typename T, typename R> |
262 | static std::pair<std::size_t, OutputIterator> apply (const Graph& g, |
263 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, |
264 | DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, |
265 | param_not_found) |
266 | { |
267 | typedef typename graph_traits<Graph>::vertices_size_type |
268 | vertices_size_type; |
269 | std::vector<vertices_size_type> lowpt(num_vertices(g)); |
270 | vertices_size_type vst(0); |
271 | |
272 | typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type; |
273 | |
274 | return bicomp_dispatch3<dispatch_type>::apply |
275 | (g, comp, out, index_map, dtm, |
276 | make_iterator_property_map(lowpt.begin(), index_map, vst), |
277 | params, get_param(params, vertex_predecessor)); |
278 | } |
279 | }; |
280 | |
281 | template <typename DiscoverTimeMap> |
282 | struct bicomp_dispatch1 |
283 | { |
284 | template<typename Graph, typename ComponentMap, typename OutputIterator, |
285 | typename VertexIndexMap, class P, class T, class R> |
286 | static std::pair<std::size_t, OutputIterator> apply(const Graph& g, |
287 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, |
288 | const bgl_named_params<P, T, R>& params, DiscoverTimeMap dtm) |
289 | { |
290 | typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type; |
291 | |
292 | return bicomp_dispatch2<dispatch_type>::apply |
293 | (g, comp, out, index_map, dtm, params, |
294 | get_param(params, vertex_lowpoint)); |
295 | } |
296 | }; |
297 | |
298 | template <> |
299 | struct bicomp_dispatch1<param_not_found> |
300 | { |
301 | template<typename Graph, typename ComponentMap, typename OutputIterator, |
302 | typename VertexIndexMap, class P, class T, class R> |
303 | static std::pair<std::size_t, OutputIterator> apply(const Graph& g, |
304 | ComponentMap comp, OutputIterator out, VertexIndexMap index_map, |
305 | const bgl_named_params<P, T, R>& params, param_not_found) |
306 | { |
307 | typedef typename graph_traits<Graph>::vertices_size_type |
308 | vertices_size_type; |
309 | std::vector<vertices_size_type> discover_time(num_vertices(g)); |
310 | vertices_size_type vst(0); |
311 | |
312 | typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type; |
313 | |
314 | return bicomp_dispatch2<dispatch_type>::apply |
315 | (g, comp, out, index_map, |
316 | make_iterator_property_map(discover_time.begin(), index_map, vst), |
317 | params, get_param(params, vertex_lowpoint)); |
318 | } |
319 | }; |
320 | |
321 | } |
322 | |
323 | template<typename Graph, typename ComponentMap, typename OutputIterator, |
324 | typename DiscoverTimeMap, typename LowPointMap> |
325 | std::pair<std::size_t, OutputIterator> |
326 | biconnected_components(const Graph& g, ComponentMap comp, |
327 | OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt) |
328 | { |
329 | typedef param_not_found dispatch_type; |
330 | |
331 | return detail::bicomp_dispatch3<dispatch_type>::apply |
332 | (g, comp, out, |
333 | get(vertex_index, g), |
334 | dtm, lowpt, |
335 | bgl_named_params<int, buffer_param_t>(0), |
336 | param_not_found()); |
337 | } |
338 | |
339 | template <typename Graph, typename ComponentMap, typename OutputIterator, |
340 | typename P, typename T, typename R> |
341 | std::pair<std::size_t, OutputIterator> |
342 | biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, |
343 | const bgl_named_params<P, T, R>& params) |
344 | { |
345 | typedef typename get_param_type< vertex_discover_time_t, bgl_named_params<P,T,R> >::type dispatch_type; |
346 | |
347 | return detail::bicomp_dispatch1<dispatch_type>::apply(g, comp, out, |
348 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |
349 | params, get_param(params, vertex_discover_time)); |
350 | } |
351 | |
352 | template < typename Graph, typename ComponentMap, typename OutputIterator> |
353 | std::pair<std::size_t, OutputIterator> |
354 | biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out) |
355 | { |
356 | return biconnected_components(g, comp, out, |
357 | bgl_named_params<int, buffer_param_t>(0)); |
358 | } |
359 | |
360 | namespace graph_detail { |
361 | struct dummy_output_iterator |
362 | { |
363 | typedef std::output_iterator_tag iterator_category; |
364 | typedef void value_type; |
365 | typedef void pointer; |
366 | typedef void difference_type; |
367 | |
368 | struct reference { |
369 | template<typename T> |
370 | reference& operator=(const T&) { return *this; } |
371 | }; |
372 | |
373 | reference operator*() const { return reference(); } |
374 | dummy_output_iterator& operator++() { return *this; } |
375 | dummy_output_iterator operator++(int) { return *this; } |
376 | }; |
377 | } // end namespace graph_detail |
378 | |
379 | template <typename Graph, typename ComponentMap, |
380 | typename P, typename T, typename R> |
381 | std::size_t |
382 | biconnected_components(const Graph& g, ComponentMap comp, |
383 | const bgl_named_params<P, T, R>& params) |
384 | { |
385 | return biconnected_components(g, comp, |
386 | graph_detail::dummy_output_iterator(), params).first; |
387 | } |
388 | |
389 | template <typename Graph, typename ComponentMap> |
390 | std::size_t |
391 | biconnected_components(const Graph& g, ComponentMap comp) |
392 | { |
393 | return biconnected_components(g, comp, |
394 | graph_detail::dummy_output_iterator()).first; |
395 | } |
396 | |
397 | template<typename Graph, typename OutputIterator, |
398 | typename P, typename T, typename R> |
399 | OutputIterator |
400 | articulation_points(const Graph& g, OutputIterator out, |
401 | const bgl_named_params<P, T, R>& params) |
402 | { |
403 | return biconnected_components(g, dummy_property_map(), out, |
404 | params).second; |
405 | } |
406 | |
407 | template<typename Graph, typename OutputIterator> |
408 | OutputIterator |
409 | articulation_points(const Graph& g, OutputIterator out) |
410 | { |
411 | return biconnected_components(g, dummy_property_map(), out, |
412 | bgl_named_params<int, buffer_param_t>(0)).second; |
413 | } |
414 | |
415 | } // namespace boost |
416 | |
417 | #endif /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */ |
418 | |