Re: [boost] space complexity of push_relabel_max_flow

Subject: Re: [boost] space complexity of push_relabel_max_flow
From: Dan Jiang (danjiang_at_[hidden])
Date: 2010-04-15 12:05:22

> Date: Thu, 15 Apr 2010 11:41:19 -0400
> From: jewillco_at_[hidden]
> To: boost_at_[hidden]
> Subject: Re: [boost] space complexity of push_relabel_max_flow
> 
> On Wed, 14 Apr 2010, Dan Jiang wrote:
> 
> (snip)
> 
> >> How do you define "relevant"?  Are they local in terms of the grid of
> >> voxels?  Is there any regular structure at all, such as linking to all
> >> neighbors within a certain distance that have a certain weight or
> >> something?  What are you able to say about the conditions for which edges
> >> are put in?  Can any of the data used to create edges be reused for
> >> computing capacities?
> >>
> > "relevant" is parameterized on a formula which means, # of arcs from a 
> > node is a variable whose value ranges from 5 to 150. So there is really 
> > no patten because the parameter used to compute "relavency" is 
> > user-defined. I think CSR would work better in terms of memory 
> > requirement. However, I do not know how much as push_relabel_max_flow 
> > (or anall max flow algorithms in BOOST) requires "capacity" map and 
> > "reverse_edge" map which seem not provided by the CSR graph (in fact, I 
> > do not even know how to get these two maps from a CSR if possible at 
> > all, see my reply in another email).
> 
> The reason I'm asking these questions is to see if there is some property 
> like "all relevant voxels to a particular voxel are within a certain 
> distance", 
No they are not. An arc can be constructed between neighbouring nodes and between distant nodes. It depends on a user-specified parameter.
> even if not all voxels within that distance are considered 
> relevant by your criteria.  That may allow some compression of the graph's 
> topology, plus possibly make the reverse map easy to compute implicitly. 
> Also, is there any simple formula to compute the capacities?  Do those 
> need to be stored explicitly?

Capacities for each arc are user-defined as well. 
I think CSR would save memory. But I do not know if the max flow algorithms can operate on them. It seems not based on the source code as CSR does not seem to provide reverse_edge map.
I have another question on the max flow algorithms: why does BOOST use map to store edge capacities and reverse edges? Map requires lots of ram, cannot array of list do the trick? I also took a look at Golberg's original implementation of the push_relabel_max_flow algorithm (hipr), it seems he does not use maps at all.
-Thanks,
Dan Jiang

                                               
_________________________________________________________________
Videos that have everyone talking! Now also in HD!
http://go.microsoft.com/?linkid=9724465