Re: [boost] space complexity of push_relabel_max_flow

Subject: Re: [boost] space complexity of push_relabel_max_flow
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-04-15 11:41:19

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", 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?

-- Jeremiah Willcock