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