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

On 3/19/07, Greg Reynolds 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::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::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