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@gmail.com To: boost@lists.boost.org Subject: Re: [boost] space complexity of push_relabel_max_flow
On Tue, Apr 13, 2010 at 6:06 AM, Dan Jiang <danjiang@live.ca> 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