On Wed, May 21, 2014 at 4:39 AM, Sensei <senseiwa@gmail.com> wrote:
On 20/05/14 23:12, Nick Edmonds wrote:

There is an in-place constructor to the CSR graph, but you'll need three
separate vectors (sources, targets, properties) rather than a vector of
tuples.  See the in-place ctors here
<http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/compressed_sparse_row.html>.


Thanks Nick, I know about the in-place constructor, and that is what I used before I needed a weighted graph.

But now I need to have weights on arcs, and since the arcs are chosen among N^2 node couples (and there is no way I can avoid checking N^2 node pairs), I opted for Intel's TBB.

It is convenient to use a TBB concurrent vector of tuples since push_back is guaranteed to work, and that is just what I need. However, if I switch to a concurrent vector for arcs and another one for weights, I might need a semaphore, hurting performances.

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.
 
Moreover, I've been thinking about using a concurrent vector and a hash map from pairs to weights, but I don't know if this can be useful in a boost CSR constructor.
 
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.

I really hope I could get rid of these temporaries!



Thanks!
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users