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:
> >> 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.
> 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.
Got a phone? Get Hotmail & Messenger for mobile!
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk