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

From: Greg Reynolds (gmr001_at_[hidden])
Date: 2007-03-20 09:09:56

Hi Aaron,

Thanks for the response.

It turns out that I was being a bit dim; I didn't realise that long paths 
of vertices, e.g. 1--2--3--4--5 turn into lots of biconnected components 
: it's not something that the previous (non-boost) implementation of 
biconnected components I used did.

Your comments on the code were interesting - is the second parameter to 
the property map really necessary? I have used lots of property maps and 
have never used this - have I just been lucky? :)

Thanks,

Greg

On Mon, 19 Mar 2007, Aaron Windsor wrote:

> 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>