potential bugs in BGL function "brandes_betweenness_centrality()"
From my previous experience with BGL, the subgraph function has similar
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. 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
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
participants (2)
-
Douglas Gregor
-
Qiaofeng Yang