Re: [boost] [BGL] brandes_betweenness_centrality failed on medium-size graphs

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-09-07 09:14:15

On Sep 7, 2005, at 2:11 AM, Yu Huang wrote:
> Actually, I can't say the it succeeds on large graph. I stopped it  
> after
> ~45 brandes_betweenness_centrality() calls(because it took too long,
> over-night).

Make sure to compile with full optimization (e.g., -O3 on GCC),  
because it makes a *huge* difference in the performance.

> But on medium-size ones, the first
> brandes_betweenness_centrality() is always ok. But failed quickly,
> mostly 2nd loop, some 3rd, even 5th. Only 0x080942d8 changed from  
> run to
> run. Others remain same(Am i stupid to say this? of course it won't  
> change).

I'm guessing that you will need to renumber the edges after removing  
an edge.

[snip]
>             vector<double> edge_centrality(no_of_edges);
>             EdgeCentralityMap ec_map(edge_centrality.begin(),
> get(edge_index, graph));

At this point, we need to be 100% sure that no_of_edges > the index  
of every edge in the graph, otherwise we'll be reading/writing past  
the end of the edge_centrality vector.

>                 //"make_iterator_property_map(edge_centrality.begin(),
> get(edge_index, subgraph), double())" also works.
>             indirect_cmp<EdgeCentralityMap,  
> std::less<centrality_type> >
> cmp(ec_map);
>             #ifdef DEBUG
>                 std::cerr<<"running  
> brandes_betweenness_centrality... ";
>             #endif
>             brandes_betweenness_centrality(graph,
> edge_centrality_map(ec_map));
>             #ifdef DEBUG
>                 std::cerr<<"done."<<std::endl;
>             #endif
>             edgeDescriptor e = *max_element(edges(graph).first,
> edges(graph).second, cmp);
>             centrality_type max_centrality = get(ec_map, e);
>             #ifdef DEBUG
>                 std::cerr<<"max_centrality is  
> "<<max_centrality<<std::endl;
>             #endif
>             remove_edge(e, graph);
>             #ifdef DEBUG
>                 std::cerr<<"after removal the subgraph has
> "<<num_edges(graph)<<" edges."<<std::endl;
>             #endif

I believe this is the problem. When you remove an edge, num_edges 
(graph) is reduced by one. However, there may still exist an edge  
with edge_index=num_edges(graph). There are two ways to fix the problem:

   1) After calling remove_edge, loop over the edges in the graph and  
reindex them to be sure they are in the range [0, num_edges(graph))  
after removal.
   2) Allocate the edge_centrality vector for the total number of  
edges *outside* of the cut_by_betweenness_centrality function, then  
pass in a reference to the vector (or its property map). That way,  
even without changing the edge indices you'll still have enough space  
in the vector, even though its usage will be sparse.

#1 is the smallest fix, whereas #2 might result in slightly faster code.

     Doug