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