Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at