Date: Thu, 15 Apr 2010 11:41:19 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org 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