Re: [Boost-users] [graph] boykov_kolmogorov_max_flow and reverse edges capacity

Subject: Re: [Boost-users] [graph] boykov_kolmogorov_max_flow and reverse edges capacity
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-12-21 17:42:42

On Fri, 20 Dec 2013, Olivier Tournaire wrote:

> Hi,
> 
> I am trying to use boykov_kolmogorov_max_flow algorithm to find a minimum cut of some graph.
> To build the graph, I first create source and sink vertices. I then add some vertices, and connect them. Each time I create
> and edge, I also create the reverse edge:
> 
>     edge_descriptor_bool e01 = add_edge(v0, v1, _graph);
>     edge_descriptor_bool e10 = add_edge(v1, v0, _graph);
>     reverse[e01.first] = e10.first;
>     reverse[e10.first] = e01.first;
> 
> where reverse is:
> 
>     boost::property_map<Graph, boost::edge_reverse_t>::type   reverse = get(boost::edge_reverse , _graph);
> 
> I then fill edge capacity:
> 
> capacity[e10.first] = this->getEnergy(fh, fh_v0); // Use policy to compute energy
> capacity[e01.first] = this->getEnergy(fh, fh_v0); // Use policy to compute energy
> 
> My question is how capacity of reverse edge has to be computed. The doc states that reverse edge can carry capacities
> different than 0, but should they be the same as their parallel edge?

They should be 0 unless they have a separate capacity (i.e., would still 
exist with non-zero capacity even if reverse edges weren't required).

-- Jeremiah Willcock