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