Re: [boost] Requesting permission to merge r61326 into release branch

Subject: Re: [boost] Requesting permission to merge r61326 into release branch
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-04-16 21:40:42

On Fri, 16 Apr 2010, Dan Jiang wrote:

> Then does unsorted_multi_pass use extra memory than sorted? If yes, how 
> much? If I sort myself, I guess I have to sort the bundled property map 
> of the edges along with the edges array.

Only for the input data -- unsorted_multi_pass copies from an input buffer 
into the internal graph data structures while sorting, while unsorted does 
the copy first and then sorts in place (which is slower).  Starting with 
sorted data means that the CSR graph needs to copy in the edge targets and 
properties (and accumulate counts from the sources).  If you are really 
crunched for memory while building the graph, you may also want to 
consider starting with separate vectors of sources, targets, and 
properties; this is slower but can recycle the input buffers you give with 
targets and properties directly into the graph data structure.  In regards 
to your last point, yes, it is easier to not need to sort properties 
yourself; std::sort can't do that and so you would need to write that code 
manually.

-- Jeremiah Willcock