Boost logo

Boost :

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.

> 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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at