Boost logo

Boost :

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

> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at