Re: [boost] space complexity of push_relabel_max_flow

Subject: Re: [boost] space complexity of push_relabel_max_flow
From: Dan Jiang (danjiang_at_[hidden])
Date: 2010-04-14 18:06:28

> Date: Tue, 13 Apr 2010 22:41:07 -0400
> From: jewillco_at_[hidden]
> To: boost_at_[hidden]
> 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