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-13 12:53:45

On Tue, 13 Apr 2010, Dan Jiang wrote:

> Hi All, I am a new BOOST user and like it very much. I have a question 
> regarding space complexity of push_relabel_max_flow. The 
> push_relabel_max_flow is very efficient compared to Edmond's and Karp. 
> In my application, I need to deal with half a million nodes and half a 
> billion arcs. It requires lots of ram (>= 6gb). Two questions:

> 1) How do I find out space used per node and per arc?

I do not know off hand for adjacency_list; it is probably reasonable (one 
integer per edge, some per vertex, plus properties).  However, remember 
that dynamically allocated vectors can have up to a 100% space overhead. 
I would recommend using compressed_sparse_row_graph and then changing the 
EdgeIndex and Vertex types to uint32_t (since you have fewer than 2^32 of 
each).  That will use 4 * (nedges + nvertices + 1) bytes of space, plus 
properties; accesses will also likely be faster than for adjacency_list.

> 2) My network does not need any reverse edge (currently I set the 
> capacity of reverse edge to 0), is there anyway to not supply reverse 
> edges to save space?

It does not appear so, because of the residual capacities that need to be 
stored.  If you can find an algorithm description that doesn't need 
reverse edges, though, it might be possible to change the algorithm to 
remove them.

> 3) Does push_relabel_algorithm dynamically allocates lots of memory 
> (besides the ram required by the input graph, i.e., adjacency_list)?

It looks like there is a bunch of that.  I see six vectors and a queue in 
there, and one of those vectors is a vector of std::lists.

> 4) Is it possible to implement custom file-based edge lists so that I 
> could explicitly page to disk when not enough ram is available? How 
> slower would it be?

It would probably be quite a bit slower.  If you need to go beyond your 
system's memory, why not let the OS's swap mechanism do the disk accesses? 
That would take care of all of the caching and such that you would need, 
and I'm not sure writing your own would provide much benefit.

How much memory do you have, and what type are you using for your edge 
capacities?  I have some ideas for how to shrink things, but I would first 
like to see a baseline of how bad things are now.  If you switch to 
compressed_sparse_row_graph and try to run the algorithm (possibly on 
scaled-down graphs), how much memory does it use?  Running that for a few 
data sizes might give an idea of how much actual space per vertex and edge 
the algorithm uses.

BTW, is there any regular structure in your graph?  For example, is it a 
grid graph like some computer vision algorithms use?

-- Jeremiah Willcock