Re: [boost] space complexity of push_relabel_max_flow

Subject: Re: [boost] space complexity of push_relabel_max_flow
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-04-13 22:41:07

On Tue, 13 Apr 2010, Dan Jiang wrote:

> Hi, I am trying to use compressed_sparse_row_graph with 
> push_relabel_max_flow. But I am stuck as a newbie to BOOST. I could not 
> find any example using compressed_sparse_row_graph with the algorithm. 
> Can anyone help? Here is my code with adjacency_list:

> typedef adjacency_list< vecS, vecS, directedS, no_property, 
> property<edge_capacity_t, float, property<edge_residual_capacity_t, 
> float, property<edge_reverse_t, Traits::edge_descriptor> > >, 
> no_property, vecS > BOOST_Graph;

To use the CSR graph, you will need to use bundled properties or external 
properties.  Just create a struct for the three edge properties (one field 
for each property), following the instructions at 
<URL:https://svn.boost.org/svn/boost/trunk/libs/graph/doc/bundles.html>.

> property_map<BOOST_Graph, edge_capacity_t>::type capacity = 
> get(edge_capacity, g);property_map<BOOST_Graph, 
> edge_residual_capacity_t>::type residual_capacity = 
> get(edge_residual_capacity, g);Traits::vertex_descriptor s, 
> Traits::vertex_descriptor t;

> // Code to set up s, t, capacity and reverse_capacity is omited...
> // Now find max flowfloat flow = push_relabel_max_flow(g, s, t);

For CSR, you'll need to have your graph structure in advance (or be able 
to compute it on the fly).  Look at the different constructors in the 
documentation and see which one matches your input data structures best. 
Prefer the ones that take sorted inputs first, then if you can't do that 
use edges_are_unsorted_multi_pass, and (least preferably) the 
edges_are_unsorted and construct_inplace_from_sources_and_targets 
versions.  If you don't have sorting or the ability to do multiple passes 
over your input, though, you will need to use the later ones to save 
memory (don't sort the data or copy it into a temporary buffer for 
multi-pass capability yourself -- CSR has various tricks to do those 
things more efficiently).

-- Jeremiah Willcock