[Boost-bugs] [Boost C++ Libraries] #1398: brandes_betweenness_centrality doesn't give correct result when network is large

Subject: [Boost-bugs] [Boost C++ Libraries] #1398: brandes_betweenness_centrality doesn't give correct result when network is large
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2007-11-01 11:05:44

#1398: brandes_betweenness_centrality doesn't give correct result when network is
large
--------------------------------+-------------------------------------------
 Reporter:  heshan_at_[hidden]  |       Owner:  dgregor
     Type:  Bugs                |      Status:  new    
Milestone:  To Be Determined    |   Component:  graph  
  Version:  Boost 1.34.1        |    Severity:  Problem
 Keywords:  betweenness         |  
--------------------------------+-------------------------------------------
 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;
 }

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/1398>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.