Re: [Boost-users] potential bugs in BGL function "brandes_betweenness_centrality()"

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-04-09 09:17:41

On Apr 8, 2005, at 10:37 PM, Qiaofeng Yang wrote:
> while(num_vertices(G)>0)
> {
> int V = num_vertices(G);
> vector<double> vertex_centrality(V);
>
> brandes_betweenness_centrality(G,
> make_iterator_property_map(vertex_centrality.begin(), get(vertex_index,
> G), double()));
>
> //print the vertex betweenness centrality for all the vertices
> ...
>
> //find the index of the vertex with the highest betweenness centrality
> ...
>
> clear_vertex(...);
> remove_vertex(...);
> }

After the call to remove_vertex, the vertex indices are no longer 
valid, e.g.,

1) The first time through the loop, V = 9. The vertices have indices 0, 
1, 2, 3, 4, 5, 6, 7, 8
2) We delete one vertex, so V = 8. Say it's the vertex with index 3. 
The vertices have indices 0, 1, 2, 4, 5, 6, 7, 8

During the execution of brandes_betweenness_centrality in the second 
iteration, we'll try to access vertex_centrality[8], which is an error. 
vertex_centrality has been reallocated to only allow 8 elements, not 9.

The easiest way to fix this is to remove the vertex_centrality vector 
from the loop, then add:

   vector<double> vertex_centrality(num_vertices(G));

*before* the loop. This will speed up the computation because the 
vector doesn't get reallocated each time. More importantly, it will 
stay at the maximum number of vertices, so even though we delete vertex 
index "3" there is still a vertex index "8". The vector will have some 
"holes" in it where values aren't used after the first iteration, but 
that's okay.

Vertex and edge indices are a weak point in the BGL. It seems like they 
should be automatically updated, but that can't be done efficiently. We 
have a partial solution (a graph type that is reasonably good 
all-around and does automatic (re-)indexing), but it's not ready for 
release yet.

        Doug