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

Subject: Re: [Boost-users] [Graph] CSR from list of tuples
From: Nick Edmonds (nicholas.g.edmonds_at_[hidden])
Date: 2014-05-21 13:36:45

On Wed, May 21, 2014 at 4:39 AM, Sensei <senseiwa_at_[hidden]> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>