[boost] space complexity of push_relabel_max_flow

Subject: [boost] space complexity of push_relabel_max_flow
From: Dan Jiang (danjiang_at_[hidden])
Date: 2010-04-13 07:06:10

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?
Thanks,
Dan Jiang

                                               
_________________________________________________________________
Hotmail & Messenger. Get them on your phone now.
http://go.microsoft.com/?linkid=9724463