summaryrefslogtreecommitdiff
path: root/boost/graph/biconnected_components.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/graph/biconnected_components.hpp')
-rw-r--r--boost/graph/biconnected_components.hpp104
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),