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

From: Qiaofeng Yang (qyang_at_[hidden])
Date: 2005-04-08 22:37:09

Hi,

I use g++ (GCC) 3.2.2 20030222 (Red Hat Linux 3.2.2-5).

What I did is as follows:
=====================================================================
1. Use "brandes_betweenness_centrality()" to calculate the vertex
betweenness centrality for all the vertices in the graph.
2. Find the vertex with the highest betweenness value.
3. Delete the vertex from the graph.
4. Repeat step 1 until no vertex left in the graph.
=====================================================================

The code is sketched as follows:
========================================================================
typedef property<vertex_name_t, string> VertexName;
typedef property<vertex_index_t, int, VertexName> VertexProperty;
typedef property<edge_index_t, int> EdgeProperty;
typedef adjacency_list<listS, listS, undirectedS, VertexProperty,
EdgeProperty> Graph;

Graph G;

//load graph
...

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(...);
}
========================================================================

The above code is run on a graph with 8 vertices and 9 edges. Below is the
edge list representation of my graph:
node0 node4
node0 node1
node0 node2
node0 node3
node1 node2
node2 node3
node4 node5
node4 node6
node4 node7

The problem is as follows:
1. Extremely slow. The first iteration is fast, but you have to wait for a
long time before the results of the second iteration to print out.
2. After several iterations, the vertex name printed out is wrong.
(In my graph, at the third iteration, the vertex name is printed out
wrong)
3. When there are two vertices and no edges in the graph, the program
stops printing out anything, basically freezes there.

>From my previous experience with BGL, the subgraph function has similar
problem. When I create a subgraph from a graph, everything is inherited
correctly, including vertex names, edges, etc. When I try to create a
subgraph from the subgraph from the previous step, I get segmentation
fault when trying to print out vertex names. I think there may be some
bugs in the source files dealing with the graph structure modification.

Best regards,
Qiaofeng