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

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.