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