Chris@16: // Copyright (c) Jeremy Siek 2001
Chris@16: // Copyright (c) Douglas Gregor 2004
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: // NOTE: this final is generated by libs/graph/doc/biconnected_components.w
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
Chris@16: #define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
Chris@16: 
Chris@16: #include <stack>
Chris@16: #include <vector>
Chris@16: #include <algorithm> // for std::min and std::max
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/graph/depth_first_search.hpp>
Chris@16: #include <boost/graph/graph_utility.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16:   namespace detail
Chris@16:   {
Chris@16:     template<typename ComponentMap, typename DiscoverTimeMap,
Chris@16:              typename LowPointMap, typename PredecessorMap,
Chris@16:              typename OutputIterator, typename Stack,
Chris@16:              typename ArticulationVector, typename IndexMap,
Chris@16:              typename DFSVisitor>
Chris@16:     struct biconnected_components_visitor : public dfs_visitor<>
Chris@16:     {
Chris@16:       biconnected_components_visitor
Chris@16:         (ComponentMap comp, std::size_t& c, 
Chris@16:          std::size_t& children_of_root, DiscoverTimeMap dtm,
Chris@16:          std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred,
Chris@16:          OutputIterator out, Stack& S,
Chris@16:          ArticulationVector& is_articulation_point, IndexMap index_map,
Chris@16:          DFSVisitor vis)
Chris@16:           : comp(comp), c(c), children_of_root(children_of_root),
Chris@16:             dtm(dtm), dfs_time(dfs_time), lowpt(lowpt),
Chris@16:             pred(pred), out(out), S(S),
Chris@16:             is_articulation_point(is_articulation_point),
Chris@16:             index_map(index_map), vis(vis) { }
Chris@16: 
Chris@16:       template <typename Vertex, typename Graph>
Chris@16:       void initialize_vertex(const Vertex& u, Graph& g)
Chris@16:       {
Chris@16:         put(pred, u, u);
Chris@16:         vis.initialize_vertex(u, g);
Chris@16:       }
Chris@16: 
Chris@16:       template <typename Vertex, typename Graph>
Chris@16:       void start_vertex(const Vertex& u, Graph& g)
Chris@16:       {
Chris@16:         children_of_root = 0;
Chris@16:         vis.start_vertex(u, g);
Chris@16:       }
Chris@16: 
Chris@16:       template <typename Vertex, typename Graph>
Chris@16:       void discover_vertex(const Vertex& u, Graph& g)
Chris@16:       {
Chris@16:         put(dtm, u, ++dfs_time);
Chris@16:         put(lowpt, u, get(dtm, u));
Chris@16:         vis.discover_vertex(u, g);
Chris@16:       }
Chris@16: 
Chris@16:       template <typename Edge, typename Graph>
Chris@16:       void examine_edge(const Edge& e, Graph& g)
Chris@16:       {
Chris@16:         vis.examine_edge(e, g);
Chris@16:       }
Chris@16: 
Chris@16:       template <typename Edge, typename Graph>
Chris@16:       void tree_edge(const Edge& e, Graph& g)
Chris@16:       {
Chris@16:         typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g);
Chris@16:         typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g);
Chris@16: 
Chris@16:         S.push(e);
Chris@16:         put(pred, tgt, src);
Chris@16:         if ( get(pred, src) == src ) {
Chris@16:           ++children_of_root;
Chris@16:         }
Chris@16:         vis.tree_edge(e, g);
Chris@16:       }
Chris@16: 
Chris@16:       template <typename Edge, typename Graph>
Chris@16:       void back_edge(const Edge& e, Graph& g)
Chris@16:       {
Chris@16:         BOOST_USING_STD_MIN();
Chris@16: 
Chris@16:         typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g);
Chris@16:         typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g);
Chris@16:         if ( tgt != get(pred, src) ) {
Chris@16:           S.push(e);
Chris@16:           put(lowpt, src,
Chris@16:               min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, src),
Chris@16:                                                    get(dtm, tgt)));
Chris@16:         }
Chris@16:         vis.back_edge(e, g);
Chris@16:       }
Chris@16: 
Chris@16:       template <typename Edge, typename Graph>
Chris@16:       void forward_or_cross_edge(const Edge& e, Graph& g)
Chris@16:       {
Chris@16:         vis.forward_or_cross_edge(e, g);
Chris@16:       }
Chris@16: 
Chris@16:       template <typename Vertex, typename Graph>
Chris@16:       void finish_vertex(const Vertex& u, Graph& g)
Chris@16:       {
Chris@16:         BOOST_USING_STD_MIN();
Chris@16:         Vertex parent = get(pred, u);
Chris@16:         if (parent == u) { // Root of tree is special
Chris@16:           is_articulation_point[get(index_map, u)] = (children_of_root > 1);
Chris@16:         } else {
Chris@16:           put(lowpt, parent,
Chris@16:               min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent),
Chris@16:                                                  get(lowpt, u)));
Chris@16:           if ( get(lowpt, u) >= get(dtm, parent) ) {
Chris@16:             is_articulation_point[get(index_map, parent)] = true;
Chris@16:             while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) {
Chris@16:               put(comp, S.top(), c);
Chris@16:               S.pop();
Chris@16:             }
Chris@16:             BOOST_ASSERT (source(S.top(), g) == parent);
Chris@16:             BOOST_ASSERT (target(S.top(), g) == u);
Chris@16:             put(comp, S.top(), c);
Chris@16:             S.pop();
Chris@16:             ++c;
Chris@16:           }
Chris@16:         }
Chris@16:         if ( is_articulation_point[get(index_map, u)] ) {
Chris@16:           *out++ = u;
Chris@16:         }
Chris@16:         vis.finish_vertex(u, g);
Chris@16:       }
Chris@16: 
Chris@16:       ComponentMap comp;
Chris@16:       std::size_t& c;
Chris@16:       std::size_t& children_of_root;
Chris@16:       DiscoverTimeMap dtm;
Chris@16:       std::size_t& dfs_time;
Chris@16:       LowPointMap lowpt;
Chris@16:       PredecessorMap pred;
Chris@16:       OutputIterator out;
Chris@16:       Stack& S;
Chris@16:       ArticulationVector& is_articulation_point;
Chris@16:       IndexMap index_map;
Chris@16:       DFSVisitor vis;
Chris@16:     };
Chris@16: 
Chris@16:   template<typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:         typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap,
Chris@16:         typename PredecessorMap, typename DFSVisitor>
Chris@16:   std::pair<std::size_t, OutputIterator>
Chris@16:     biconnected_components_impl(const Graph & g, ComponentMap comp,
Chris@16:         OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm,
Chris@16:         LowPointMap lowpt, PredecessorMap pred, DFSVisitor dfs_vis)
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
Chris@16:     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
Chris@16:     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, edge_t> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<DiscoverTimeMap,
Chris@16:                                                   vertex_t> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<LowPointMap, vertex_t > ));
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<PredecessorMap,
Chris@16:                                                   vertex_t> ));
Chris@16: 
Chris@16:     std::size_t num_components = 0;
Chris@16:     std::size_t children_of_root;
Chris@16:     std::size_t dfs_time = 0;
Chris@16:     std::stack<edge_t> S;
Chris@16:         std::vector<char> is_articulation_point(num_vertices(g));
Chris@16: 
Chris@16:     biconnected_components_visitor<ComponentMap, DiscoverTimeMap,
Chris@16:         LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, 
Chris@16:         std::vector<char>, VertexIndexMap, DFSVisitor>
Chris@16:     vis(comp, num_components, children_of_root, dtm, dfs_time,
Chris@16:         lowpt, pred, out, S, is_articulation_point, index_map, dfs_vis);
Chris@16: 
Chris@16:     depth_first_search(g, visitor(vis).vertex_index_map(index_map));
Chris@16: 
Chris@16:     return std::pair<std::size_t, OutputIterator>(num_components, vis.out);
Chris@16:   }
Chris@16: 
Chris@16:     template <typename PredecessorMap>
Chris@16:     struct bicomp_dispatch3
Chris@16:     {
Chris@16:   template<typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:                 typename VertexIndexMap, typename DiscoverTimeMap, 
Chris@16:                 typename LowPointMap, class P, class T, class R>
Chris@16:       static std::pair<std::size_t, OutputIterator> apply (const Graph & g, 
Chris@16:           ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
Chris@16:           DiscoverTimeMap dtm, LowPointMap lowpt, 
Chris@16:           const bgl_named_params<P, T, R>& params, PredecessorMap pred)
Chris@16:       {
Chris@16:         return biconnected_components_impl
Chris@16:                 (g, comp, out, index_map, dtm, lowpt, pred,
Chris@16:                  choose_param(get_param(params, graph_visitor),
Chris@16:                     make_dfs_visitor(null_visitor())));
Chris@16:       }
Chris@16:     };
Chris@16:     
Chris@16:     template <>
Chris@16:     struct bicomp_dispatch3<param_not_found>
Chris@16:     {
Chris@16:       template<typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:                 typename VertexIndexMap, typename DiscoverTimeMap, 
Chris@16:                 typename LowPointMap, class P, class T, class R>
Chris@16:       static std::pair<std::size_t, OutputIterator> apply (const Graph & g, 
Chris@16:           ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
Chris@16:           DiscoverTimeMap dtm, LowPointMap lowpt, 
Chris@16:           const bgl_named_params<P, T, R>& params, 
Chris@16:           param_not_found)
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
Chris@16:     std::vector<vertex_t> pred(num_vertices(g));
Chris@16:     vertex_t vert = graph_traits<Graph>::null_vertex();
Chris@16: 
Chris@16:         return biconnected_components_impl
Chris@16:                 (g, comp, out, index_map, dtm, lowpt, 
Chris@16:               make_iterator_property_map(pred.begin(), index_map, vert),
Chris@16:                  choose_param(get_param(params, graph_visitor),
Chris@16:                     make_dfs_visitor(null_visitor())));
Chris@16:   }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename LowPointMap>
Chris@16:     struct bicomp_dispatch2
Chris@16:     {
Chris@16:   template<typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:                 typename VertexIndexMap, typename DiscoverTimeMap, 
Chris@16:                 typename P, typename T, typename R>
Chris@16:       static std::pair<std::size_t, OutputIterator> apply (const Graph& g, 
Chris@16:           ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
Chris@16:           DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, 
Chris@16:           LowPointMap lowpt)
Chris@16:       {
Chris@16:         typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type;
Chris@16: 
Chris@16:         return bicomp_dispatch3<dispatch_type>::apply
Chris@16:             (g, comp, out, index_map, dtm, lowpt, params, 
Chris@16:              get_param(params, vertex_predecessor));
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16:     template <>
Chris@16:     struct bicomp_dispatch2<param_not_found>
Chris@16:     {
Chris@16:       template<typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:                 typename VertexIndexMap, typename DiscoverTimeMap, 
Chris@16:                 typename P, typename T, typename R>
Chris@16:       static std::pair<std::size_t, OutputIterator> apply (const Graph& g, 
Chris@16:           ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
Chris@16:           DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, 
Chris@16:           param_not_found)
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type
Chris@16:       vertices_size_type;
Chris@16:     std::vector<vertices_size_type> lowpt(num_vertices(g));
Chris@16:         vertices_size_type vst(0);
Chris@16: 
Chris@16:         typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type;
Chris@16:   
Chris@16:         return bicomp_dispatch3<dispatch_type>::apply
Chris@16:             (g, comp, out, index_map, dtm,
Chris@16:              make_iterator_property_map(lowpt.begin(), index_map, vst),
Chris@16:              params, get_param(params, vertex_predecessor));
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename DiscoverTimeMap>
Chris@16:     struct bicomp_dispatch1
Chris@16:     {
Chris@16:       template<typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:                 typename VertexIndexMap, class P, class T, class R>
Chris@16:       static std::pair<std::size_t, OutputIterator> apply(const Graph& g, 
Chris@16:           ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
Chris@16:           const bgl_named_params<P, T, R>& params, DiscoverTimeMap dtm)
Chris@16:       {
Chris@16:         typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type;
Chris@16: 
Chris@16:         return bicomp_dispatch2<dispatch_type>::apply
Chris@16:             (g, comp, out, index_map, dtm, params, 
Chris@16:              get_param(params, vertex_lowpoint));
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct bicomp_dispatch1<param_not_found>
Chris@16:     {
Chris@16:       template<typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:                 typename VertexIndexMap, class P, class T, class R>
Chris@16:       static std::pair<std::size_t, OutputIterator> apply(const Graph& g, 
Chris@16:           ComponentMap comp, OutputIterator out, VertexIndexMap index_map, 
Chris@16:           const bgl_named_params<P, T, R>& params, param_not_found)
Chris@16:       {
Chris@16:         typedef typename graph_traits<Graph>::vertices_size_type
Chris@16:             vertices_size_type;
Chris@16:         std::vector<vertices_size_type> discover_time(num_vertices(g));
Chris@16:     vertices_size_type vst(0);
Chris@16: 
Chris@16:         typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type;
Chris@16: 
Chris@16:         return bicomp_dispatch2<dispatch_type>::apply
Chris@16:             (g, comp, out, index_map, 
Chris@16:               make_iterator_property_map(discover_time.begin(), index_map, vst),
Chris@16:              params, get_param(params, vertex_lowpoint));
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16:   template<typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:       typename DiscoverTimeMap, typename LowPointMap>
Chris@16:   std::pair<std::size_t, OutputIterator>
Chris@16:   biconnected_components(const Graph& g, ComponentMap comp, 
Chris@16:       OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt)
Chris@16:   {
Chris@16:     typedef param_not_found dispatch_type;
Chris@16: 
Chris@16:     return detail::bicomp_dispatch3<dispatch_type>::apply
Chris@16:             (g, comp, out, 
Chris@16:              get(vertex_index, g), 
Chris@16:              dtm, lowpt, 
Chris@16:              bgl_named_params<int, buffer_param_t>(0), 
Chris@16:              param_not_found());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Graph, typename ComponentMap, typename OutputIterator,
Chris@16:       typename P, typename T, typename R>
Chris@16:   std::pair<std::size_t, OutputIterator>
Chris@16:   biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, 
Chris@16:       const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     typedef typename get_param_type< vertex_discover_time_t, bgl_named_params<P,T,R> >::type dispatch_type;
Chris@16: 
Chris@16:     return detail::bicomp_dispatch1<dispatch_type>::apply(g, comp, out, 
Chris@16:         choose_const_pmap(get_param(params, vertex_index), g, vertex_index), 
Chris@16:         params, get_param(params, vertex_discover_time));
Chris@16:   }
Chris@16: 
Chris@16:   template < typename Graph, typename ComponentMap, typename OutputIterator>
Chris@16:   std::pair<std::size_t, OutputIterator>
Chris@16:   biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out)
Chris@16:   {
Chris@16:     return biconnected_components(g, comp, out,  
Chris@16:         bgl_named_params<int, buffer_param_t>(0));
Chris@16:   }
Chris@16: 
Chris@16:   namespace graph_detail {
Chris@16:     struct dummy_output_iterator
Chris@16:     {
Chris@16:       typedef std::output_iterator_tag iterator_category;
Chris@16:       typedef void value_type;
Chris@16:       typedef void pointer;
Chris@16:       typedef void difference_type;
Chris@16: 
Chris@16:       struct reference {
Chris@16:         template<typename T>
Chris@16:         reference& operator=(const T&) { return *this; }
Chris@16:       };
Chris@16: 
Chris@16:       reference operator*() const { return reference(); }
Chris@16:       dummy_output_iterator& operator++() { return *this; }
Chris@16:       dummy_output_iterator operator++(int) { return *this; }
Chris@16:     };
Chris@16:   } // end namespace graph_detail
Chris@16: 
Chris@16:   template <typename Graph, typename ComponentMap,
Chris@16:       typename P, typename T, typename R>
Chris@16:   std::size_t
Chris@16:   biconnected_components(const Graph& g, ComponentMap comp, 
Chris@16:       const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     return biconnected_components(g, comp,
Chris@16:         graph_detail::dummy_output_iterator(), params).first;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Graph, typename ComponentMap>
Chris@16:   std::size_t
Chris@16:   biconnected_components(const Graph& g, ComponentMap comp)
Chris@16:   {
Chris@16:     return biconnected_components(g, comp,
Chris@16:                                   graph_detail::dummy_output_iterator()).first;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename Graph, typename OutputIterator, 
Chris@16:       typename P, typename T, typename R>
Chris@16:   OutputIterator
Chris@16:   articulation_points(const Graph& g, OutputIterator out, 
Chris@16:       const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     return biconnected_components(g, dummy_property_map(), out, 
Chris@16:         params).second;
Chris@16:   }
Chris@16: 
Chris@16:   template<typename Graph, typename OutputIterator>
Chris@16:   OutputIterator
Chris@16:   articulation_points(const Graph& g, OutputIterator out)
Chris@16:   {
Chris@16:     return biconnected_components(g, dummy_property_map(), out, 
Chris@16:         bgl_named_params<int, buffer_param_t>(0)).second;
Chris@16:   }
Chris@16: 
Chris@16: }                               // namespace boost
Chris@16: 
Chris@16: #endif  /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */