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
26namespace 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

source code of boost/boost/graph/biconnected_components.hpp