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     {
biconnected_components_visitorboost::detail::biconnected_components_visitor37       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>
initialize_vertexboost::detail::biconnected_components_visitor51       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>
start_vertexboost::detail::biconnected_components_visitor58       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>
discover_vertexboost::detail::biconnected_components_visitor65       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>
examine_edgeboost::detail::biconnected_components_visitor73       void examine_edge(const Edge& e, Graph& g)
74       {
75         vis.examine_edge(e, g);
76       }
77 
78       template <typename Edge, typename Graph>
tree_edgeboost::detail::biconnected_components_visitor79       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>
back_edgeboost::detail::biconnected_components_visitor93       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>
forward_or_cross_edgeboost::detail::biconnected_components_visitor109       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>
finish_vertexboost::detail::biconnected_components_visitor115       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>
biconnected_components_impl(const Graph & g,ComponentMap comp,OutputIterator out,VertexIndexMap index_map,DiscoverTimeMap dtm,LowPointMap lowpt,PredecessorMap pred,DFSVisitor dfs_vis)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>
applyboost::detail::bicomp_dispatch3200       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(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>
applyboost::detail::bicomp_dispatch3218       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(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>
applyboost::detail::bicomp_dispatch2242       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>
applyboost::detail::bicomp_dispatch2262       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>
applyboost::detail::bicomp_dispatch1286       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>
applyboost::detail::bicomp_dispatch1303       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>
biconnected_components(const Graph & g,ComponentMap comp,OutputIterator out,DiscoverTimeMap dtm,LowPointMap lowpt)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>
biconnected_components(const Graph & g,ComponentMap comp,OutputIterator out,const bgl_named_params<P,T,R> & params)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>
biconnected_components(const Graph & g,ComponentMap comp,OutputIterator out)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>
operator =boost::graph_detail::dummy_output_iterator::reference370         reference& operator=(const T&) { return *this; }
371       };
372 
operator *boost::graph_detail::dummy_output_iterator373       reference operator*() const { return reference(); }
operator ++boost::graph_detail::dummy_output_iterator374       dummy_output_iterator& operator++() { return *this; }
operator ++boost::graph_detail::dummy_output_iterator375       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
biconnected_components(const Graph & g,ComponentMap comp,const bgl_named_params<P,T,R> & params)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
biconnected_components(const Graph & g,ComponentMap comp)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
articulation_points(const Graph & g,OutputIterator out)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