Boost logo

Boost :

From: Yu Huang (yuhuang_at_[hidden])
Date: 2005-09-07 02:15:52


Yu Huang wrote:

>Hi all,
>
>I coded a program recursively cutting graphs based on
>brandes_betweenness_centrality.
>
>But the weird thing is that it succeeds on small graphs(<=8 vertices,
><=15 edges) and large graphs(~3500 vertices, ~138,000edges). But failed
>on medium-size (~37-200 vertices, ~42-350 edges).
>
>
>
>The failed output is like this:
>
>no_of_vertices: 203
>no_of_edges: 368
>connectivity: 0.0179486
>running brandes_betweenness_centrality... *** glibc detected *** double
>free or corruption (out): 0x080942d8 ***
>Aborted
>
>
>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). 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).
>
>Well, i paste my core function here. The main idea is I remove the edge
>with max centrality and form a vector of clusters(graphs) from the
>ancestor graph's components (if after cut, the ancestor has >=2
>components, otherwise keep cutting on the ancestor graph).
>
>
>void ClusterByEBC::cut_by_betweenness_centrality(Graph &graph, const int
>&size_cutoff, const float &conn_cutoff)
>/*
>*09-04-05
>* cut the graph with the edge of maximum betweenness_centrality
>*/
>{
> int no_of_vertices = num_vertices(graph);
> int no_of_edges = num_edges(graph);
> #ifdef DEBUG
> std::cerr<<"no_of_vertices: "<<no_of_vertices<<std::endl;
> std::cerr<<"no_of_edges: "<<no_of_edges<<std::endl;
> #endif
> if (no_of_vertices>=size_cutoff)
> {
> float connectivity =
>2.0*no_of_edges/(no_of_vertices*(no_of_vertices-1));
> #ifdef DEBUG
> std::cerr<<"connectivity: "<<connectivity<<std::endl;
> #endif
> if (connectivity>=conn_cutoff)
> {
> #ifdef DEBUG
> std::cerr<<"good subgraph "<<std::endl;
> #endif
> good_subgraph_vector.push_back(graph);
> }
> else
> {
> vector<double> edge_centrality(no_of_edges);
> EdgeCentralityMap ec_map(edge_centrality.begin(),
>get(edge_index, graph));
> //"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
> std::vector<int> component(num_vertices(graph));
> int no_of_components = connected_components(graph,
>&component[0]);
> if (no_of_components==1) //keep cutting
> {
> #ifdef DEBUG
> std::cerr<<"only one component, keep cutting
>"<<std::endl;
> #endif
> cut_by_betweenness_centrality(graph, size_cutoff,
>conn_cutoff);
> }
> else //first get the connected_components into a
>vector_sub_subgraph and cut them separately
> {
> #ifdef DEBUG
> std::cerr<<"get the connected_components into a
>vector_graph and cut them separately "<<std::endl;
> #endif
> std::vector<Graph> vector_graph =
>graph_components(graph, component, no_of_components);
> std::vector<Graph>::iterator g_iterator;
>
>for(g_iterator=vector_graph.begin();g_iterator!=vector_graph.end();++g_iterator)
> {
> cut_by_betweenness_centrality(*g_iterator,
>size_cutoff, conn_cutoff);
> }
> }
> }
> }
> #ifdef DEBUG
> else
> std::cerr<<"Bad graph, too
>small,"<<no_of_vertices<<"vertices"<<std::endl;
> #endif
>
>}
>
>
>This looks like a hard issue. I searched the mailing list and found one
>similar message,
>http://lists.boost.org/MailArchives/ublas/2005/08/0657.php (no one replied).
>
>Thanks,
>Yu
>
>
>
I forgot, if any of you guys wants the complete source code and the
graph data, i'll email you directly. The graph data is too large to be
an attachement.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk