I can not reproduce the problem. Maybe something in the code that you did not show?
Here, in the hope that my benchmark will help, it runs 90 random graphs of 2,000 nodes and 4,000 edges for a total of 20 seconds on my PC.
Notes:
- I calculate and show arbitrary statistics on the result, so that we know that the compiler cannot optimize the situation.
- Reduced to 200 knots / 400 ribs for Coliru, performed online in 0.6 s
Live on coliru
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/betweenness_centrality.hpp> #include <boost/graph/random.hpp> #include <boost/accumulators/accumulators.hpp> #include <boost/accumulators/statistics.hpp> #include <random> typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph; typedef boost::property_map<Graph, boost::vertex_index_t>::type VertexIndexMap; int main() { for (int i = 0; i < 90; ++i) { auto const seed = std::random_device{}(); Graph g; { std::mt19937 prng { seed }; boost::generate_random_graph(g, 200, 400, prng); } std::vector<double> centrality(boost::num_vertices(g), 0.0); { VertexIndexMap v_index = get(boost::vertex_index, g); boost::iterator_property_map<std::vector<double>::iterator, VertexIndexMap> vertex_property_map = make_iterator_property_map(centrality.begin(), v_index); boost::brandes_betweenness_centrality(g, vertex_property_map); } { namespace ba = boost::accumulators; namespace bt = ba::tag; ba::accumulator_set<double, ba::features<bt::mean, bt::variance> > acc; std::for_each(centrality.begin(), centrality.end(), std::ref(acc)); std::cout << "seed:" << seed << "\t" << "mean:" << ba::mean(acc) << "\t" << "stddev:" << ba::variance(acc) << "\n"; } } }
Exit from my car (2000 knots / 4000 ribs):
seed:1750802922 mean:4376.07 stddev:1.81521e+07 seed:2035487211 mean:4453.37 stddev:1.86408e+07 seed:2157083839 mean:4431.28 stddev:1.76926e+07 seed:877099895 mean:4397.33 stddev:1.77377e+07 seed:3204597236 mean:4437.76 stddev:1.76055e+07 seed:1683789044 mean:4366.15 stddev:1.79065e+07 seed:205823178 mean:4382.23 stddev:1.97325e+07 seed:835182347 mean:4437.69 stddev:1.99322e+07 seed:783544360 mean:4419.82 stddev:1.99628e+07 seed:1294214099 mean:4450.26 stddev:1.86657e+07 seed:133119335 mean:4474.56 stddev:1.80184e+07 seed:2431619152 mean:4398.11 stddev:1.8606e+07 seed:1846518108 mean:4487.64 stddev:1.82487e+07 seed:3215400061 mean:4487.08 stddev:1.89737e+07 seed:4195971142 mean:4366.36 stddev:1.83186e+07 seed:2877690475 mean:4387.66 stddev:1.67049e+07 seed:377384221 mean:4447.82 stddev:1.88145e+07 seed:4271065968 mean:4397.8 stddev:1.90055e+07 seed:2344426096 mean:4439.01 stddev:1.67352e+07 seed:3089481099 mean:4392.55 stddev:1.85857e+07 seed:2366154376 mean:4424.22 stddev:1.8114e+07 seed:609566395 mean:4412.17 stddev:1.83808e+07 seed:532359230 mean:4385.37 stddev:1.90363e+07 seed:1222481049 mean:4389.03 stddev:1.8123e+07 seed:4252784567 mean:4424.44 stddev:1.97951e+07 seed:3589086722 mean:4441.63 stddev:1.89086e+07 seed:3253153938 mean:4434.16 stddev:1.83747e+07 seed:3171332867 mean:4425.64 stddev:1.88349e+07 seed:1628933501 mean:4389.3 stddev:1.77686e+07 seed:2757066761 mean:4456.54 stddev:1.86788e+07 seed:253689423 mean:4457.74 stddev:1.88101e+07 seed:1044077369 mean:4437.64 stddev:1.94368e+07 seed:2010288733 mean:4335.93 stddev:1.96337e+07 seed:2827445098 mean:4404.35 stddev:1.72173e+07 seed:2983615584 mean:4451.17 stddev:1.87881e+07 seed:3263411780 mean:4352.61 stddev:1.84145e+07 seed:209486011 mean:4388.81 stddev:2.00036e+07 seed:914410356 mean:4394.58 stddev:1.8876e+07 seed:4179887676 mean:4458.33 stddev:1.79864e+07 seed:1672110941 mean:4527.26 stddev:1.88183e+07 seed:1180712876 mean:4410.68 stddev:1.77379e+07 seed:3297971268 mean:4314.57 stddev:1.76706e+07 seed:1888708924 mean:4432.68 stddev:1.81473e+07 seed:519304960 mean:4346.21 stddev:1.96675e+07 seed:989700613 mean:4404.25 stddev:1.89632e+07 seed:3290422387 mean:4424.13 stddev:1.82944e+07 seed:1248119514 mean:4449.89 stddev:1.94721e+07 seed:2609686267 mean:4495.49 stddev:1.97461e+07 seed:2169392337 mean:4506.17 stddev:1.67787e+07 seed:222259970 mean:4525.36 stddev:1.94983e+07 seed:2302951742 mean:4449.87 stddev:1.86658e+07 seed:803085249 mean:4434.22 stddev:1.90194e+07 seed:291896941 mean:4388.42 stddev:1.92467e+07 seed:3271497352 mean:4401.03 stddev:1.98458e+07 seed:119293674 mean:4441.89 stddev:1.87025e+07 seed:2067901961 mean:4444.3 stddev:1.91092e+07 seed:884669150 mean:4370 stddev:1.77506e+07 seed:2010782469 mean:4427.87 stddev:1.9524e+07 seed:2999945815 mean:4341.03 stddev:1.93057e+07 seed:1413596477 mean:4429.33 stddev:1.88379e+07 seed:2999144075 mean:4346.83 stddev:1.83441e+07 seed:52996326 mean:4479.39 stddev:1.90295e+07 seed:846523521 mean:4476.82 stddev:1.80105e+07 seed:2665690159 mean:4399.54 stddev:1.92723e+07 seed:1290757175 mean:4373.11 stddev:1.80565e+07 seed:4174263463 mean:4382.66 stddev:1.89344e+07 seed:2416968118 mean:4474.83 stddev:1.91461e+07 seed:1137975099 mean:4406.52 stddev:1.89247e+07 seed:1776900404 mean:4443.7 stddev:1.91418e+07 seed:898128099 mean:4466.54 stddev:1.87237e+07 seed:3604582552 mean:4379.01 stddev:1.73953e+07 seed:3268788789 mean:4418.29 stddev:1.83793e+07 seed:910639960 mean:4507 stddev:1.73813e+07 seed:1878704662 mean:4400.72 stddev:1.81355e+07 seed:2667792405 mean:4462.01 stddev:1.81283e+07 seed:2492001126 mean:4403.49 stddev:1.86103e+07 seed:3485479239 mean:4389.32 stddev:1.84779e+07 seed:3202616710 mean:4539.88 stddev:1.94982e+07 seed:2878361287 mean:4454.12 stddev:1.86021e+07 seed:1196553996 mean:4419.3 stddev:1.86354e+07 seed:3641446403 mean:4451.88 stddev:1.857e+07 seed:2801960787 mean:4469.33 stddev:1.89828e+07 seed:1938419870 mean:4462.89 stddev:1.82868e+07 seed:176826289 mean:4464.34 stddev:1.76994e+07 seed:2873298171 mean:4415.06 stddev:1.87784e+07 seed:2992765364 mean:4395.07 stddev:1.88507e+07 seed:2883991750 mean:4422.02 stddev:1.87585e+07 seed:2985503953 mean:4479.98 stddev:1.91894e+07 seed:3822049160 mean:4439.22 stddev:1.80799e+07 seed:2881148075 mean:4341.83 stddev:1.82921e+07