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

Subject: Re: [boost] Requesting permission to merge r61326 into release branch
From: Dan Jiang (danjiang_at_[hidden])
Date: 2010-04-17 08:16:30

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_at_[hidden]
To: boost_at_[hidden]
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_at_[hidden]> To: boost_at_[hidden]> 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