Re: [boost] space complexity of push_relabel_max_flow

Subject: Re: [boost] space complexity of push_relabel_max_flow
From: Tim Keitt (tkeitt_at_[hidden])
Date: 2010-04-15 11:48:48

On Tue, Apr 13, 2010 at 6:06 AM, Dan Jiang <danjiang_at_[hidden]> 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?  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?  3) Does push_relabel_algorithm dynamically allocates lots of memory (besides the ram required by the input graph, i.e., adjacency_list)?  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?

Dear Dan,

I have implemented a set of prototype graph classes that use
PostgreSQL to store edge lists. The graph classes do not store data,
only prepared queries. The code is at
https://code.launchpad.net/postgraph

I would actually love some help with this code. Implementing your own
graph classes in the BGL is I found non-trivial. I never got
push-relabel max-flow to compile with my classes.  I probably need to
implement concept checking. Unfortunately, I've largely run out of
time to work on this. If anyone is interested in the code, I will be
happy to assist their efforts in anyway I can.

I've looked at push-relabel max-flow a lot and I can say the
implementation is not particularly space efficient. One of the issues
is that you have to store both forward and backward edges in the
graph. That is how the algorithm was designed, but I think one could
modify it to only use a single edge with forward and backward capacity
maps.

Cheers,
Tim

> Thanks,
> Dan Jiang
>
>
> _________________________________________________________________
> Hotmail & Messenger. Get them on your phone now.
> http://go.microsoft.com/?linkid=9724463
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Timothy H. Keitt
http://www.keittlab.org/