diff options
Diffstat (limited to 'boost/graph/biconnected_components.hpp')
-rw-r--r-- | boost/graph/biconnected_components.hpp | 104 |
1 files changed, 54 insertions, 50 deletions
diff --git a/boost/graph/biconnected_components.hpp b/boost/graph/biconnected_components.hpp index 9586f9a211..1669f69522 100644 --- a/boost/graph/biconnected_components.hpp +++ b/boost/graph/biconnected_components.hpp @@ -21,6 +21,7 @@ #include <boost/graph/depth_first_search.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/concept/assert.hpp> +#include <boost/assert.hpp> namespace boost { @@ -28,17 +29,23 @@ namespace boost { template<typename ComponentMap, typename DiscoverTimeMap, typename LowPointMap, typename PredecessorMap, - typename OutputIterator, typename Stack, + typename OutputIterator, typename Stack, + typename ArticulationVector, typename IndexMap, typename DFSVisitor> struct biconnected_components_visitor : public dfs_visitor<> { biconnected_components_visitor - (ComponentMap comp, std::size_t& c, DiscoverTimeMap dtm, + (ComponentMap comp, std::size_t& c, + std::size_t& children_of_root, DiscoverTimeMap dtm, std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred, - OutputIterator out, Stack& S, DFSVisitor vis) - : comp(comp), c(c), children_of_root(0), dtm(dtm), - dfs_time(dfs_time), lowpt(lowpt), - pred(pred), out(out), S(S), vis(vis) { } + OutputIterator out, Stack& S, + ArticulationVector& is_articulation_point, IndexMap index_map, + DFSVisitor vis) + : comp(comp), c(c), children_of_root(children_of_root), + dtm(dtm), dfs_time(dfs_time), lowpt(lowpt), + pred(pred), out(out), S(S), + is_articulation_point(is_articulation_point), + index_map(index_map), vis(vis) { } template <typename Vertex, typename Graph> void initialize_vertex(const Vertex& u, Graph& g) @@ -89,8 +96,7 @@ namespace boost typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g); typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g); - if ( ( tgt != get(pred, src) || get(pred, src) == src ) && - get(dtm, tgt) < get(dtm, src) ) { + if ( tgt != get(pred, src) ) { S.push(e); put(lowpt, src, min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, src), @@ -111,40 +117,41 @@ namespace boost BOOST_USING_STD_MIN(); Vertex parent = get(pred, u); if (parent == u) { // Root of tree is special - if (children_of_root >= 2) { - *out++ = u; - } - return; - } - put(lowpt, parent, - min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent), + is_articulation_point[get(index_map, u)] = (children_of_root > 1); + } else { + put(lowpt, parent, + min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent), get(lowpt, u))); - if ( get(lowpt, u) >= get(dtm, parent) ) { - if ( get(pred, parent) != parent ) { - *out++ = parent; - } - while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) { + if ( get(lowpt, u) >= get(dtm, parent) ) { + is_articulation_point[get(index_map, parent)] = true; + while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) { + put(comp, S.top(), c); + S.pop(); + } + BOOST_ASSERT (source(S.top(), g) == parent); + BOOST_ASSERT (target(S.top(), g) == u); put(comp, S.top(), c); S.pop(); + ++c; } - assert (source(S.top(), g) == parent); - assert (target(S.top(), g) == u); - put(comp, S.top(), c); - S.pop(); - ++c; + } + if ( is_articulation_point[get(index_map, u)] ) { + *out++ = u; } vis.finish_vertex(u, g); } ComponentMap comp; std::size_t& c; - std::size_t children_of_root; + std::size_t& children_of_root; DiscoverTimeMap dtm; std::size_t& dfs_time; LowPointMap lowpt; PredecessorMap pred; OutputIterator out; Stack& S; + ArticulationVector& is_articulation_point; + IndexMap index_map; DFSVisitor vis; }; @@ -168,14 +175,16 @@ namespace boost vertex_t> )); std::size_t num_components = 0; + std::size_t children_of_root; std::size_t dfs_time = 0; - std::stack<edge_t> S; + std::stack<edge_t> S; + std::vector<char> is_articulation_point(num_vertices(g)); - biconnected_components_visitor<ComponentMap, DiscoverTimeMap, - LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, - DFSVisitor> - vis(comp, num_components, dtm, dfs_time, lowpt, pred, out, - S, dfs_vis); + biconnected_components_visitor<ComponentMap, DiscoverTimeMap, + LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, + std::vector<char>, VertexIndexMap, DFSVisitor> + vis(comp, num_components, children_of_root, dtm, dfs_time, + lowpt, pred, out, S, is_articulation_point, index_map, dfs_vis); depth_first_search(g, visitor(vis).vertex_index_map(index_map)); @@ -201,7 +210,7 @@ namespace boost }; template <> - struct bicomp_dispatch3<error_property_not_found> + struct bicomp_dispatch3<param_not_found> { template<typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, @@ -210,7 +219,7 @@ namespace boost ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, LowPointMap lowpt, const bgl_named_params<P, T, R>& params, - error_property_not_found) + param_not_found) { typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; std::vector<vertex_t> pred(num_vertices(g)); @@ -235,8 +244,7 @@ namespace boost DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, LowPointMap lowpt) { - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_predecessor_t>::type dispatch_type; + typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type; return bicomp_dispatch3<dispatch_type>::apply (g, comp, out, index_map, dtm, lowpt, params, @@ -246,7 +254,7 @@ namespace boost template <> - struct bicomp_dispatch2<error_property_not_found> + struct bicomp_dispatch2<param_not_found> { template<typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, @@ -254,15 +262,14 @@ namespace boost static std::pair<std::size_t, OutputIterator> apply (const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, - error_property_not_found) + param_not_found) { typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; std::vector<vertices_size_type> lowpt(num_vertices(g)); vertices_size_type vst(0); - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_predecessor_t>::type dispatch_type; + typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type; return bicomp_dispatch3<dispatch_type>::apply (g, comp, out, index_map, dtm, @@ -280,8 +287,7 @@ namespace boost ComponentMap comp, OutputIterator out, VertexIndexMap index_map, const bgl_named_params<P, T, R>& params, DiscoverTimeMap dtm) { - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_lowpoint_t>::type dispatch_type; + typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type; return bicomp_dispatch2<dispatch_type>::apply (g, comp, out, index_map, dtm, params, @@ -290,21 +296,20 @@ namespace boost }; template <> - struct bicomp_dispatch1<error_property_not_found> + struct bicomp_dispatch1<param_not_found> { template<typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, class P, class T, class R> static std::pair<std::size_t, OutputIterator> apply(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, - const bgl_named_params<P, T, R>& params, error_property_not_found) + const bgl_named_params<P, T, R>& params, param_not_found) { typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; std::vector<vertices_size_type> discover_time(num_vertices(g)); vertices_size_type vst(0); - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_lowpoint_t>::type dispatch_type; + typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type; return bicomp_dispatch2<dispatch_type>::apply (g, comp, out, index_map, @@ -321,14 +326,14 @@ namespace boost biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt) { - typedef detail::error_property_not_found dispatch_type; + typedef param_not_found dispatch_type; return detail::bicomp_dispatch3<dispatch_type>::apply (g, comp, out, get(vertex_index, g), dtm, lowpt, bgl_named_params<int, buffer_param_t>(0), - detail::error_property_not_found()); + param_not_found()); } template <typename Graph, typename ComponentMap, typename OutputIterator, @@ -337,8 +342,7 @@ namespace boost biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, const bgl_named_params<P, T, R>& params) { - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_discover_time_t>::type dispatch_type; + typedef typename get_param_type< vertex_discover_time_t, bgl_named_params<P,T,R> >::type dispatch_type; return detail::bicomp_dispatch1<dispatch_type>::apply(g, comp, out, choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |