Re: [boost] space complexity of push_relabel_max_flow

Subject: Re: [boost] space complexity of push_relabel_max_flow
From: Dan Jiang (danjiang_at_[hidden])
Date: 2010-04-16 06:41:47

Hello Tim,
Thanks for the offering. You project looks very interesting. For now, I am trying to get CSR graph working with push_relabel_max_flow. Failing that, I'll look into using your library. I have a feeling, even if I get it working, I may still need to go with a database based approach eventually.
You said you never got push_relabel_max_flow working for your custom graph. Is your graph based on CSR or adjaceny_list? The problem I am facing with CSR is lack of a simple working example for setting with push_relabel_max_flow. I have been at it for 4 days straight and still fighting with it. I have been a long time C++ developer with ATL/COM and hence template to me is not a new thing, but I found learning curve with BOOST is still pretty steep due to lack of examples in some areas. (Do not get me wrong, it is an excellent library) 
Cheers,
Dan

> Date: Thu, 15 Apr 2010 10:48:48 -0500
> From: tkeitt_at_[hidden]
> To: boost_at_[hidden]
> Subject: Re: [boost] space complexity of push_relabel_max_flow
> 
> 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/
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
                                               
_________________________________________________________________
Videos that have everyone talking! Now also in HD!
http://go.microsoft.com/?linkid=9724465