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