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 14:22:00

On Thu, 15 Apr 2010, Dan Jiang wrote:

(snip)

>> 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.

OK.

>> 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.

I do not believe any of the graph types have a reverse edge map -- you 
need to create one.  The Boost property maps are not necessarily (or 
usually) std::maps, which do have high overhead as you say.  The usual 
property map created for internal use is an std::vector whose size is the 
number of vertices or edges in the graph, indexed using the graph's vertex 
or edge index maps.

-- Jeremiah Willcock