BGL graph library biconnected components
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? Thanks, Greg
On 3/19/07, Greg Reynolds <gmr001@bham.ac.uk> 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
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@bham.ac.uk> 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On 3/20/07, Greg Reynolds <gmr001@bham.ac.uk> wrote:
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? :)
If you don't explicitly pass the second parameter, it defaults to an identity property map (a map id where get(id, v) = v for all values v.) So you don't really need to pass the second argument if the values in the domain of the property map are actually a block of contiguous integers starting with 0 (Note that this is actually the case for vertex descriptors if you use a vector to store vertices in the adjacency_list template.) But for any other case, you'd need to supply a map as the second parameter. Regards, Aaron
participants (2)
-
Aaron Windsor
-
Greg Reynolds