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