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