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-15 11:47:19

On Wed, 14 Apr 2010, Dan Jiang wrote:

(snip)
>> 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?

Now that you're using bundled properties, you need to use the syntax in
the URL I sent above.  In particular, you need:

property_map<BOOST_Graph, &EdgeProp::float>::type
   capacity = get(&EdgeProp::capacity, g);

and similar code for the residual map.  You will also need to add an
edge reverse map to EdgeProp and use a similar statement to get it as a
property map.

>> 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.

OK.

-- Jeremiah Willcock

PS: Could you please format your code so that it is marked as keeping
the literal spacing or something?  When I get it everything is jammed
onto one line making it hard to read.  I am reformatting it in my reply
here, but that is inconvenient.