I did some further experiment. edges_are_unsorted doubles ram when graph is created. push_relabel_max_flow does not really consume any extra RAM once CSR is created. This is a really good news to me: it means that I can potentially cut the ram usage by up to 50% if I could construct the graph in place using my own container. Is there such an CSR constructor? Would the one mentioned below does the trick? Many thanks, Dan From: danjiang@live.ca To: boost@lists.boost.org Subject: RE: [boost] Requesting permission to merge r61326 into release branch Date: Fri, 16 Apr 2010 23:03:40 -0400
Date: Fri, 16 Apr 2010 21:40:42 -0400> From: jewillco@osl.iu.edu> To: boost@lists.boost.org> Subject: Re: [boost] Requesting permission to merge r61326 into release branch> > 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).Ok. Then I'll try edges_are_unsorted_multi_pass_t first. But I have hard time to find which data structure's start() and end() returns a MultiPassInputIterator which is required if multi-pass unsorted edges are used. MultiPassInputIterator seems to be BOOST specific and I could not find an example online.> 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. Do you meant to use this constructor? template <typename Source> compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, std::vector<Source>& sources, std::vector<vertex_descriptor>& targets, std::vector<edge_bundled>& edge_props, vertices_size_type numverts, const ProcessGroup& pg = ProcessGroup(), const GraphProperty& prop = GraphProperty());> 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.Using qsort can do this easily. But I'd prefer unsorted_multi_pass work if I can figure out how to get MultiPassInputIterators. Dan
Got a phone? Get Hotmail & Messenger for mobile! _________________________________________________________________ Got a phone? Get Hotmail & Messenger for mobile! http://go.microsoft.com/?linkid=9724464