On 21/05/14 19:36, Nick Edmonds wrote:
I think you could avoid a semaphore around the insertions for sure. Do you know the upper bound on the number of edges a priori? If so then you can guarantee that the vector doesn't realloc and just use an int-fetch-add (either an intrinsic or Boost.Atomic) to reserve indices in your vectors.
That's a good idea, thank you, Nick! In this particular case, yes, I know that the number of edges is limited to 32, so I think I will use your suggestion.
Eventually you're going to have to build a dense vector of edge weights if you want to use a CSR graph, either inside the CSR ctor or before you call it. The only way to avoid this that I can think of is to build the edge weight vector directly in your graph generation code. Whether that's more costly than using a temporary later depends on whether you have more time or memory to spare.
Mmhh, I will benchmark this option. Weights are generated by a nice O(N^3) algorithm so I guess it's quite expensive either way. Thanks!