Hi Doug, Thanks for the hint! I manually re-index all the vertices after the vertex removal(a for() loop) and put vertex_centrality(num_vertices(G)) outside the while() loop. The code works fine now :). I have another question concerning vertex and edge iterator. The problem is now that I want to remove the nth edge in the graph. I use the following code: ================================================== //typedef stuff ... EdgeDescriptor Edge; Edge = *(edges(G).first + n); //n is an int remove_edge(Edge, G); ================================================== I got compilation errors at line "Edge = *(edges(G).first + n);". I have to use the following code in order to compile the code and to run it correctly: ================================================== //typedef stuff ... EdgeDescriptor Edge; EdgeIterator edge_iter; edge_iter = edges(G).first; for(int i = 0; i < n; i++) { edge_iter++;} Edge = *edge_iter; remove_edge(Edge, G); ================================================== Basically, you have to use a for() loop to increment the edge_iterator varialbe. Is it possible just to use one addition(the first code) instead of n additions(the second code) to increment the iterator? Best regards, Qiaofeng
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