Date: Thu, 15 Apr 2010 14:22:00 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org 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