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 15:21:27

> Date: Thu, 15 Apr 2010 14:22:00 -0400
> From: jewillco_at_[hidden]
> To: boost_at_[hidden]
> Subject: Re: [boost] space complexity of push_relabel_max_flow
> 
> 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. 
Ok,  will do.
> 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.
> 
Wow, that is great to know about the maps. It calms me down as std::maps is really heavy weight. 
Dan

                                               
_________________________________________________________________
Got a phone? Get Hotmail & Messenger for mobile!
http://go.microsoft.com/?linkid=9724464