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

From: qyang_at_[hidden]
Date: 2005-04-09 20:12:24

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