Re: [Boost-users] BGL graph library biconnected components

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-03-19 20:41:36

On 3/19/07, Greg Reynolds <gmr001_at_[hidden]> wrote:
> Hi,
>
> I have been using "biconnected_components.hpp" for quite a while
> now. However, I have come across some graphs for which it finds far too
> many components...
>
> Here is my usage:
>
> ////////////////////////////
>
> Graph g;
>
> // initialise g and give edges an index
>
> std::vector< int > vec_bcc_nums( num_edges(g) );
>
> iterator_property_map< std::vector< int >::iterator, property_map<Graph,
> edge_index_t>::type > mapEdgeComponent( vec_bcc_nums.begin() );
>
> int num = biconnected_components(g, mapEdgeComponent);
>
> ///////////////////////////
>
> I'm afraid I can't post an example of the graphs (they are really big and
> I signed an NDA).
>
> What I would like to know is:
>
> a) Is the code above sensible, is there something subtly wrong with it?
> b) Has anyone else used the biconnected components code in anger on
> largish (> 300 vertices) graphs?
>

Hi Greg,

a) Almost - the iterator_property_map constructor should take a second
argument that would be an edge index map in this case - if you're
using an interior edge index map, your code would look like:

iterator_property_map< std::vector< int >::iterator,
property_map<Graph, edge_index_t>::type > mapEdgeComponent(
vec_bcc_nums.begin() , get(edge_index,g));

...and that's assuming that you've initialized the edge index map with
distinct values in the range 0..num_edges(g)-1. I would also use
graph_traits<Graph>::edges_size_type instead of int as the value type
of the vector, but that's a minor point.

b) Yes, I've been using it recently, running a lot of tests on largish
graphs (never in anger, though.) I haven't come across any problems
yet, although it could just be that my tests are silently failing
somehow.

In case the omission of an edge index map above was just a typo, and
you're still seeing failures, is there any more information you can
give about how you think it's failing, or a sample graph it fails on?

Regards,
Aaron