On Wed, May 21, 2014 at 4:39 AM, Sensei
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