id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
1398,brandes_betweenness_centrality doesn't give correct result when network is large,heshan@…,Douglas Gregor,"I'm using the C++ version. My network is a 2D regular lattice. when number of nodes in the network is small, N<35*35，the betweenness returned by brandes_betweenness_centrality() is correct, but when N>35*35，the result is wrong. when N=50*50，the betweenness is at the magnitude of order 1e9, which is obviously wrong. I also use betweenness function provided by JUNG to confirm that this is a bug. But java is too slow, I decide to implement brandes algorithm on my own. To my surprise, my program has the exactly same problem as the brandes_betweenness_centrality(). This seems to be an overflow problem. I find that the variable to record the number of path between source and every other vertex should have large enough representation range. I previously use unsigned int. After I change the type to double, the problem is fixed. the simplest code to reproduce the bug are in the following:

#include <iostream>
#include <vector>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/betweenness_centrality.hpp>
using namespace std;
using namespace boost;

int main()
{
    typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, double> > graph_t;
    const unsigned int L = 50;
    const unsigned int vertexnum = L * L;
    graph_t graph(vertexnum);
    unsigned int upper, left;

    for( unsigned int vertexidx = 0; vertexidx < vertexnum; ++vertexidx ) {
        upper = ( vertexidx < L ) ? ( L * ( L - 1 ) + vertexidx ) : ( vertexidx - L );
        left = ( vertexidx % L ) ? ( vertexidx - 1 ) : ( vertexidx + L - 1 );
        add_edge( vertex( vertexidx, graph ), vertex( upper, graph ), graph );
        add_edge( vertex( vertexidx, graph ), vertex( left, graph ), graph );
    }
    
    vector<double> betweenness( num_vertices( graph ) );
    brandes_betweenness_centrality( graph, centrality_map( make_iterator_property_map(
        betweenness.begin(), get( vertex_index, graph ) ) )
    );
    copy( betweenness.begin(), betweenness.end(), ostream_iterator<double>( cout, "" "" ) );
    return EXIT_SUCCESS;
}",Bugs,closed,To Be Determined,graph,Boost 1.34.1,Problem,fixed,betweenness,