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