Re: [Boost-users] [Graph] CSR from list of tuples

Subject: Re: [Boost-users] [Graph] CSR from list of tuples
From: Sensei (senseiwa_at_[hidden])
Date: 2014-05-23 05:49:08

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!