[Boost-users] problem with boost::strong_components

From: Tamas Marki (tmarki_at_[hidden])
Date: 2007-01-26 03:30:28

Hello,
I'm trying to use the boost library's strong_components function to
partition a graph to connected sub-partitions, and ran into a problem.
Namely, when I generate the graph, for some reason the 'names' (indices) of
the vertices have some gaps (basically the graph that needs to be
partitioned is generated from another graph by throwing out a bunch of
vertices).
When I pass this graph to the function, it will count the left out vertices
and treat them as 1-vertex sub-partitions, which is not desired. I then
tried to use the vertex_index_map named parameter, that I thought would
solve this. I used something like this (not the actual code as it would be
too big)

std::vector<int> other;
// fill up the vector with the vertices by pushing back each one. The number
of vertices is about 170k and the biggest vertex index is about 260k.
// ..
// bigedges and bigweights have the edges and the weights, dim is the total
number of vertices - all these are checked and proper.

graph_t cityg (bigedges.begin (), bigedges.end (), bigweights.begin (),
dim);
std::vector<int> component(num_vertices(cityg));
int num = strong_components(cityg, &component[0], boost::vertex_index_map
(&other[0]));

I must be doing it wrong, since it segfaults. The documentation says "This
maps each vertex to an integer in the range [0, num_vertices(g))", that's
why I thought it would work this way, but it does not.
The obvious solution would be to throw out 1-vertex partitions, but I'd
really like to know what's the proper way of doing this.
Thanks in advance for any help!

Tamas