Boost logo

Boost :

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

Hi all,

I coded a program recursively cutting graphs based on

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

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)
* 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;
    if (no_of_vertices>=size_cutoff)
        float connectivity =
        #ifdef DEBUG
            std::cerr<<"connectivity: "<<connectivity<<std::endl;
        if (connectivity>=conn_cutoff)
            #ifdef DEBUG
                std::cerr<<"good subgraph "<<std::endl;
            vector<double> edge_centrality(no_of_edges);
            EdgeCentralityMap ec_map(edge_centrality.begin(),
get(edge_index, graph));
get(edge_index, subgraph), double())" also works.
            indirect_cmp<EdgeCentralityMap, std::less<centrality_type> >
            #ifdef DEBUG
                std::cerr<<"running brandes_betweenness_centrality... ";
            #ifdef DEBUG
            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;
            remove_edge(e, graph);
            #ifdef DEBUG
                std::cerr<<"after removal the subgraph has
"<<num_edges(graph)<<" edges."<<std::endl;
            std::vector<int> component(num_vertices(graph));
            int no_of_components = connected_components(graph,
            if (no_of_components==1) //keep cutting
                #ifdef DEBUG
                    std::cerr<<"only one component, keep cutting
                cut_by_betweenness_centrality(graph, size_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;
                std::vector<Graph> vector_graph =
graph_components(graph, component, no_of_components);
                std::vector<Graph>::iterator g_iterator;
size_cutoff, conn_cutoff);
    #ifdef DEBUG
        std::cerr<<"Bad graph, too

This looks like a hard issue. I searched the mailing list and found one
similar message, (no one replied).


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