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