Date: Tue, 13 Apr 2010 22:41:07 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] space complexity of push_relabel_max_flow
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>.
Ok, I followed that, here is my code:struct EdgeProp{ float capacity; float residual_capacity;};typedef compressed_sparse_row_graph<directedS, void, //property<vertex_index_t, DWORD32>, do I need this? EdgeProp, no_property, // Graph Property DWORD32, // Vertex Type DWORD32> // EdgeIndex Type BOOST_Graph; then I could set the capacity like so: typedef std::pair<int, int> E; E *theEdges = new E [nEdges]; EdgeProp *edgeProps = new EdgeProp [nEdges]; for (int i=0; i<nEdges/2; i++){ E e = E(from, to); E re = E(to, from); theEdges[i-1] = e; theEdges[i] = re; edgeProps[i-1].capacity = temp.cap; edgeProps[i].capacity = 0; }
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; Then need to get "capacity" map and "reverse_edge" map like below as max flow algorithm depends on them: BOOST_Graph g(edges_are_unsorted, &theEdges[0], &theEdges[0] + nEdges, &edgeProps[0], nVertices); property_map<BOOST_Graph, edge_capacity_t>::type capacity = get(edge_capacity, g); property_map<BOOST_Graph, edge_reverse_t>::type rev = get(edge_reverse, g); However, I get compile error: 'boost::get' : none of the 2 overloads could convert all the argument types Can you give me an example how to get these two property maps for CSR graph?
// 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).
As shown in the above code, I use edges_are_unsorted for now and will use edges_are_sorted later once I get those two property maps working. Dan Jiang _________________________________________________________________ Videos that have everyone talking! Now also in HD! http://go.microsoft.com/?linkid=9724465