boost/graph/biconnected_components.hpp

0001 // Copyright (c) Jeremy Siek 2001
0002 // Copyright (c) Douglas Gregor 2004
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See
0005 // accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007
0008 // NOTE: this final is generated by libs/graph/doc/biconnected_components.w
0009
0010 #ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
0011 #define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
0012
0013 #include <stack>
0014 #include <vector>
0015 #include <algorithm> // for std::min and std::max
0016 #include <boost/config.hpp>
0017 #include <boost/limits.hpp>
0018 #include <boost/graph/graph_traits.hpp>
0019 #include <boost/graph/graph_concepts.hpp>
0020 #include <boost/property_map/property_map.hpp>
0021 #include <boost/graph/depth_first_search.hpp>
0022 #include <boost/graph/graph_utility.hpp>
0023 #include <boost/concept/assert.hpp>
0024 #include <boost/assert.hpp>
0025
0026 namespace boost
0027 {
0028 namespace detail
0029 {
0030     template < typename ComponentMap, typename DiscoverTimeMap,
0031         typename LowPointMap, typename PredecessorMap, typename OutputIterator,
0032         typename Stack, typename ArticulationVector, typename IndexMap,
0033         typename DFSVisitor >
0034     struct biconnected_components_visitor : public dfs_visitor<>
0035     {
0036         biconnected_components_visitor(ComponentMap comp, std::size_t& c,
0037             std::size_t& children_of_root, DiscoverTimeMap dtm,
0038             std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred,
0039             OutputIterator out, Stack& S,
0040             ArticulationVector& is_articulation_point, IndexMap index_map,
0041             DFSVisitor vis)
0042         : comp(comp)
0043         , c(c)
0044         , children_of_root(children_of_root)
0045         , dtm(dtm)
0046         , dfs_time(dfs_time)
0047         , lowpt(lowpt)
0048         , pred(pred)
0049         , out(out)
0050         , S(S)
0051         , is_articulation_point(is_articulation_point)
0052         , index_map(index_map)
0053         , vis(vis)
0054         {
0055         }
0056
0057         template < typename Vertex, typename Graph >
0058         void initialize_vertex(const Vertex& u, Graph& g)
0059         {
0060             put(pred, u, u);
0061             vis.initialize_vertex(u, g);
0062         }
0063
0064         template < typename Vertex, typename Graph >
0065         void start_vertex(const Vertex& u, Graph& g)
0066         {
0067             children_of_root = 0;
0068             vis.start_vertex(u, g);
0069         }
0070
0071         template < typename Vertex, typename Graph >
0072         void discover_vertex(const Vertex& u, Graph& g)
0073         {
0074             put(dtm, u, ++dfs_time);
0075             put(lowpt, u, get(dtm, u));
0076             vis.discover_vertex(u, g);
0077         }
0078
0079         template < typename Edge, typename Graph >
0080         void examine_edge(const Edge& e, Graph& g)
0081         {
0082             vis.examine_edge(e, g);
0083         }
0084
0085         template < typename Edge, typename Graph >
0086         void tree_edge(const Edge& e, Graph& g)
0087         {
0088             typename boost::graph_traits< Graph >::vertex_descriptor src
0089                 = source(e, g);
0090             typename boost::graph_traits< Graph >::vertex_descriptor tgt
0091                 = target(e, g);
0092
0093             S.push(e);
0094             put(pred, tgt, src);
0095             if (get(pred, src) == src)
0096             {
0097                 ++children_of_root;
0098             }
0099             vis.tree_edge(e, g);
0100         }
0101
0102         template < typename Edge, typename Graph >
0103         void back_edge(const Edge& e, Graph& g)
0104         {
0105             BOOST_USING_STD_MIN();
0106
0107             typename boost::graph_traits< Graph >::vertex_descriptor src
0108                 = source(e, g);
0109             typename boost::graph_traits< Graph >::vertex_descriptor tgt
0110                 = target(e, g);
0111             if (tgt != get(pred, src))
0112             {
0113                 S.push(e);
0114                 put(lowpt, src,
0115                     min BOOST_PREVENT_MACRO_SUBSTITUTION(
0116                         get(lowpt, src), get(dtm, tgt)));
0117             }
0118             vis.back_edge(e, g);
0119         }
0120
0121         template < typename Edge, typename Graph >
0122         void forward_or_cross_edge(const Edge& e, Graph& g)
0123         {
0124             vis.forward_or_cross_edge(e, g);
0125         }
0126
0127         template < typename Vertex, typename Graph >
0128         void finish_vertex(const Vertex& u, Graph& g)
0129         {
0130             BOOST_USING_STD_MIN();
0131             Vertex parent = get(pred, u);
0132             if (parent == u)
0133             { // Root of tree is special
0134                 is_articulation_point[get(index_map, u)]
0135                     = (children_of_root > 1);
0136             }
0137             else
0138             {
0139                 put(lowpt, parent,
0140                     min BOOST_PREVENT_MACRO_SUBSTITUTION(
0141                         get(lowpt, parent), get(lowpt, u)));
0142                 if (get(lowpt, u) >= get(dtm, parent))
0143                 {
0144                     is_articulation_point[get(index_map, parent)] = true;
0145                     while (get(dtm, source(S.top(), g)) >= get(dtm, u))
0146                     {
0147                         put(comp, S.top(), c);
0148                         S.pop();
0149                     }
0150                     BOOST_ASSERT(source(S.top(), g) == parent);
0151                     BOOST_ASSERT(target(S.top(), g) == u);
0152                     put(comp, S.top(), c);
0153                     S.pop();
0154                     ++c;
0155                 }
0156             }
0157             if (is_articulation_point[get(index_map, u)])
0158             {
0159                 *out++ = u;
0160             }
0161             vis.finish_vertex(u, g);
0162         }
0163
0164         ComponentMap comp;
0165         std::size_t& c;
0166         std::size_t& children_of_root;
0167         DiscoverTimeMap dtm;
0168         std::size_t& dfs_time;
0169         LowPointMap lowpt;
0170         PredecessorMap pred;
0171         OutputIterator out;
0172         Stack& S;
0173         ArticulationVector& is_articulation_point;
0174         IndexMap index_map;
0175         DFSVisitor vis;
0176     };
0177
0178     template < typename Graph, typename ComponentMap, typename OutputIterator,
0179         typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap,
0180         typename PredecessorMap, typename DFSVisitor >
0181     std::pair< std::size_t, OutputIterator > biconnected_components_impl(
0182         const Graph& g, ComponentMap comp, OutputIterator out,
0183         VertexIndexMap index_map, DiscoverTimeMap dtm, LowPointMap lowpt,
0184         PredecessorMap pred, DFSVisitor dfs_vis)
0185     {
0186         typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0187         typedef typename graph_traits< Graph >::edge_descriptor edge_t;
0188         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0189         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
0190         BOOST_CONCEPT_ASSERT(
0191             (WritablePropertyMapConcept< ComponentMap, edge_t >));
0192         BOOST_CONCEPT_ASSERT(
0193             (ReadWritePropertyMapConcept< DiscoverTimeMap, vertex_t >));
0194         BOOST_CONCEPT_ASSERT(
0195             (ReadWritePropertyMapConcept< LowPointMap, vertex_t >));
0196         BOOST_CONCEPT_ASSERT(
0197             (ReadWritePropertyMapConcept< PredecessorMap, vertex_t >));
0198
0199         std::size_t num_components = 0;
0200         std::size_t children_of_root;
0201         std::size_t dfs_time = 0;
0202         std::stack< edge_t > S;
0203         std::vector< char > is_articulation_point(num_vertices(g));
0204
0205         biconnected_components_visitor< ComponentMap, DiscoverTimeMap,
0206             LowPointMap, PredecessorMap, OutputIterator, std::stack< edge_t >,
0207             std::vector< char >, VertexIndexMap, DFSVisitor >
0208             vis(comp, num_components, children_of_root, dtm, dfs_time, lowpt,
0209                 pred, out, S, is_articulation_point, index_map, dfs_vis);
0210
0211         depth_first_search(g, visitor(vis).vertex_index_map(index_map));
0212
0213         return std::pair< std::size_t, OutputIterator >(
0214             num_components, vis.out);
0215     }
0216
0217     template < typename PredecessorMap > struct bicomp_dispatch3
0218     {
0219         template < typename Graph, typename ComponentMap,
0220             typename OutputIterator, typename VertexIndexMap,
0221             typename DiscoverTimeMap, typename LowPointMap, class P, class T,
0222             class R >
0223         static std::pair< std::size_t, OutputIterator > apply(const Graph& g,
0224             ComponentMap comp, OutputIterator out, VertexIndexMap index_map,
0225             DiscoverTimeMap dtm, LowPointMap lowpt,
0226             const bgl_named_params< P, T, R >& params, PredecessorMap pred)
0227         {
0228             return biconnected_components_impl(g, comp, out, index_map, dtm,
0229                 lowpt, pred,
0230                 choose_param(get_param(params, graph_visitor),
0231                     make_dfs_visitor(null_visitor())));
0232         }
0233     };
0234
0235     template <> struct bicomp_dispatch3< param_not_found >
0236     {
0237         template < typename Graph, typename ComponentMap,
0238             typename OutputIterator, typename VertexIndexMap,
0239             typename DiscoverTimeMap, typename LowPointMap, class P, class T,
0240             class R >
0241         static std::pair< std::size_t, OutputIterator > apply(const Graph& g,
0242             ComponentMap comp, OutputIterator out, VertexIndexMap index_map,
0243             DiscoverTimeMap dtm, LowPointMap lowpt,
0244             const bgl_named_params< P, T, R >& params, param_not_found)
0245         {
0246             typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0247             std::vector< vertex_t > pred(num_vertices(g));
0248             vertex_t vert = graph_traits< Graph >::null_vertex();
0249
0250             return biconnected_components_impl(g, comp, out, index_map, dtm,
0251                 lowpt,
0252                 make_iterator_property_map(pred.begin(), index_map, vert),
0253                 choose_param(get_param(params, graph_visitor),
0254                     make_dfs_visitor(null_visitor())));
0255         }
0256     };
0257
0258     template < typename LowPointMap > struct bicomp_dispatch2
0259     {
0260         template < typename Graph, typename ComponentMap,
0261             typename OutputIterator, typename VertexIndexMap,
0262             typename DiscoverTimeMap, typename P, typename T, typename R >
0263         static std::pair< std::size_t, OutputIterator > apply(const Graph& g,
0264             ComponentMap comp, OutputIterator out, VertexIndexMap index_map,
0265             DiscoverTimeMap dtm, const bgl_named_params< P, T, R >& params,
0266             LowPointMap lowpt)
0267         {
0268             typedef typename get_param_type< vertex_predecessor_t,
0269                 bgl_named_params< P, T, R > >::type dispatch_type;
0270
0271             return bicomp_dispatch3< dispatch_type >::apply(g, comp, out,
0272                 index_map, dtm, lowpt, params,
0273                 get_param(params, vertex_predecessor));
0274         }
0275     };
0276
0277     template <> struct bicomp_dispatch2< param_not_found >
0278     {
0279         template < typename Graph, typename ComponentMap,
0280             typename OutputIterator, typename VertexIndexMap,
0281             typename DiscoverTimeMap, typename P, typename T, typename R >
0282         static std::pair< std::size_t, OutputIterator > apply(const Graph& g,
0283             ComponentMap comp, OutputIterator out, VertexIndexMap index_map,
0284             DiscoverTimeMap dtm, const bgl_named_params< P, T, R >& params,
0285             param_not_found)
0286         {
0287             typedef typename graph_traits< Graph >::vertices_size_type
0288                 vertices_size_type;
0289             std::vector< vertices_size_type > lowpt(num_vertices(g));
0290             vertices_size_type vst(0);
0291
0292             typedef typename get_param_type< vertex_predecessor_t,
0293                 bgl_named_params< P, T, R > >::type dispatch_type;
0294
0295             return bicomp_dispatch3< dispatch_type >::apply(g, comp, out,
0296                 index_map, dtm,
0297                 make_iterator_property_map(lowpt.begin(), index_map, vst),
0298                 params, get_param(params, vertex_predecessor));
0299         }
0300     };
0301
0302     template < typename DiscoverTimeMap > struct bicomp_dispatch1
0303     {
0304         template < typename Graph, typename ComponentMap,
0305             typename OutputIterator, typename VertexIndexMap, class P, class T,
0306             class R >
0307         static std::pair< std::size_t, OutputIterator > apply(const Graph& g,
0308             ComponentMap comp, OutputIterator out, VertexIndexMap index_map,
0309             const bgl_named_params< P, T, R >& params, DiscoverTimeMap dtm)
0310         {
0311             typedef typename get_param_type< vertex_lowpoint_t,
0312                 bgl_named_params< P, T, R > >::type dispatch_type;
0313
0314             return bicomp_dispatch2< dispatch_type >::apply(g, comp, out,
0315                 index_map, dtm, params, get_param(params, vertex_lowpoint));
0316         }
0317     };
0318
0319     template <> struct bicomp_dispatch1< param_not_found >
0320     {
0321         template < typename Graph, typename ComponentMap,
0322             typename OutputIterator, typename VertexIndexMap, class P, class T,
0323             class R >
0324         static std::pair< std::size_t, OutputIterator > apply(const Graph& g,
0325             ComponentMap comp, OutputIterator out, VertexIndexMap index_map,
0326             const bgl_named_params< P, T, R >& params, param_not_found)
0327         {
0328             typedef typename graph_traits< Graph >::vertices_size_type
0329                 vertices_size_type;
0330             std::vector< vertices_size_type > discover_time(num_vertices(g));
0331             vertices_size_type vst(0);
0332
0333             typedef typename get_param_type< vertex_lowpoint_t,
0334                 bgl_named_params< P, T, R > >::type dispatch_type;
0335
0336             return bicomp_dispatch2< dispatch_type >::apply(g, comp, out,
0337                 index_map,
0338                 make_iterator_property_map(
0339                     discover_time.begin(), index_map, vst),
0340                 params, get_param(params, vertex_lowpoint));
0341         }
0342     };
0343
0344 }
0345
0346 template < typename Graph, typename ComponentMap, typename OutputIterator,
0347     typename DiscoverTimeMap, typename LowPointMap >
0348 std::pair< std::size_t, OutputIterator > biconnected_components(const Graph& g,
0349     ComponentMap comp, OutputIterator out, DiscoverTimeMap dtm,
0350     LowPointMap lowpt)
0351 {
0352     typedef param_not_found dispatch_type;
0353
0354     return detail::bicomp_dispatch3< dispatch_type >::apply(g, comp, out,
0355         get(vertex_index, g), dtm, lowpt,
0356         bgl_named_params< int, buffer_param_t >(0), param_not_found());
0357 }
0358
0359 template < typename Graph, typename ComponentMap, typename OutputIterator,
0360     typename P, typename T, typename R >
0361 std::pair< std::size_t, OutputIterator > biconnected_components(const Graph& g,
0362     ComponentMap comp, OutputIterator out,
0363     const bgl_named_params< P, T, R >& params)
0364 {
0365     typedef typename get_param_type< vertex_discover_time_t,
0366         bgl_named_params< P, T, R > >::type dispatch_type;
0367
0368     return detail::bicomp_dispatch1< dispatch_type >::apply(g, comp, out,
0369         choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
0370         params, get_param(params, vertex_discover_time));
0371 }
0372
0373 template < typename Graph, typename ComponentMap, typename OutputIterator >
0374 std::pair< std::size_t, OutputIterator > biconnected_components(
0375     const Graph& g, ComponentMap comp, OutputIterator out)
0376 {
0377     return biconnected_components(
0378         g, comp, out, bgl_named_params< int, buffer_param_t >(0));
0379 }
0380
0381 namespace graph_detail
0382 {
0383     struct dummy_output_iterator
0384     {
0385         typedef std::output_iterator_tag iterator_category;
0386         typedef void value_type;
0387         typedef void pointer;
0388         typedef void difference_type;
0389
0390         struct reference
0391         {
0392             template < typename T > reference& operator=(const T&)
0393             {
0394                 return *this;
0395             }
0396         };
0397
0398         reference operator*() const { return reference(); }
0399         dummy_output_iterator& operator++() { return *this; }
0400         dummy_output_iterator operator++(int) { return *this; }
0401     };
0402 } // end namespace graph_detail
0403
0404 template < typename Graph, typename ComponentMap, typename P, typename T,
0405     typename R >
0406 std::size_t biconnected_components(const Graph& g, ComponentMap comp,
0407     const bgl_named_params< P, T, R >& params)
0408 {
0409     return biconnected_components(
0410         g, comp, graph_detail::dummy_output_iterator(), params)
0411         .first;
0412 }
0413
0414 template < typename Graph, typename ComponentMap >
0415 std::size_t biconnected_components(const Graph& g, ComponentMap comp)
0416 {
0417     return biconnected_components(
0418         g, comp, graph_detail::dummy_output_iterator())
0419         .first;
0420 }
0421
0422 template < typename Graph, typename OutputIterator, typename P, typename T,
0423     typename R >
0424 OutputIterator articulation_points(const Graph& g, OutputIterator out,
0425     const bgl_named_params< P, T, R >& params)
0426 {
0427     return biconnected_components(g, dummy_property_map(), out, params).second;
0428 }
0429
0430 template < typename Graph, typename OutputIterator >
0431 OutputIterator articulation_points(const Graph& g, OutputIterator out)
0432 {
0433     return biconnected_components(g, dummy_property_map(), out,
0434         bgl_named_params< int, buffer_param_t >(0))
0435         .second;
0436 }
0437
0438 } // namespace boost
0439
0440 #endif /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */