Re: [boost] CSR graph in max flow

Subject: Re: [boost] CSR graph in max flow
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-04-16 14:10:28

On Thu, 15 Apr 2010, Dan Jiang wrote:

>> Date: Thu, 15 Apr 2010 13:26:37 -0400
>> From: jewillco_at_[hidden]
>> To: boost_at_[hidden]
>> Subject: Re: [boost] CSR graph in max flow
>>
>> On Thu, 15 Apr 2010, Dan Jiang wrote:
>>
>>> I see several replies from you. But none of them answered my question of
>>> how to setup capacity map and reverse_edge map for CSR graph (I got
>>> compile error). Did you get that email? If not I can resend it. -Thanks
>>> Dan
>>
>> I sent one with the example for how to get the capacity map -- your
>> bundled edge property didn't have a reverse map.  The capacity map is:
>>
>> boost::property_map<Graph, EdgeProp::*float>::type capacity_map
>> = get(&EdgeProp::capacity, g);
>>
>> and similar for the other maps.
>>
> Ok, I did that, but push_relabel_max_flow errors out at all lines that try to access the capacity or reverse_capacity, e.g.:     residual_capacity[*ei] = capacity[*ei];Because both capacity and residual_capacity maps in push_relabel_max_flow are keyed on edge_descriptor while the above definition is key on a "float".
> How do I fix this if possible?
> Also, I have another question regarding reverse_edge_map creation from a CSR graph.In case of adjacency list, I can use add_edge to create both forward and backward edges and then add both to reverse_edge map, i.e.,edge_descriptor e1 = add_edge(v1, v2);edge_descriptor e2 = add_edge(v2, v1);rev[e1] = e2;rev[e2] = e1;In case CSR, I am passing an array of std::pair<int, int> to CSR constructor using "unsorted_edges" flag, i.e., I can not get e1 and e2 edge_descriptors as above. So I am thinking of looping through each edge to populate the reverse edge "rev" map:  BGL_FORALL_EDGES(e, g, BOOST_Graph)   {      BOOST_Graph::vertex_descriptor src = boost::source(e, g);      BOOST_Graph::vertex_descriptor dst = boost::target(e, g);      // Here compiler errors out: term does not evaluate to a function taking 3 arguments      std::pair<edge_descriptor, bool> edge = edge(src, dst, g);             std::pair<edge_descriptor, bool> edge_rev = edge(dst, src, g); // But compiler errors ou!
 t h
> ere      rev[edge.first] = edge_rev.first;   }Can you tell me how to fix the compiler errors?

What compiler errors do you have?  Could you please post a complete piece 
of code that gives an error, as well as the errors themselves?  Also, 
please put newlines in your code so it is easier to read.

-- Jeremiah Willcock