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

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