Implementing and optimizing a simple graph metric

[Joseph Rushton Wakeling]

On Wednesday, 18 September 2013 at 17:13:28 UTC, bearophile wrote:
> How many times or how often do you need to call betweenness()? 
> If it's called only few times or once in a while then using the 
> GC is good enough. But if you have to call it many millions of 
> times, all those GC array allocations could cost some time, 
> even if they are small arrays. In this case allocating them on 
> the stack (or not allocating them, using externally allocated 
> buffers) helps.

I think millions of times is excessive. In my test code I have an 
example with a 50-node network calculating betweenness centrality 
10000 times, which takes under 1.5 seconds. So obviously if you 
scale up to millions, small improvements could make a difference, 
but it's not going to be on such a scale that it's worth 
prioritizing, at least for now. I think even 10000 calculations 
is excessive for any practical case I can think of.

You're right to call for the opportunity to pass a buffer, 
though, and I've enabled that. In the current test code it 
doesn't seem to improve anything, but that may be simply a matter 
of scale.