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

Subject: [Boost-users] [graph] boykov_kolmogorov_max_flow and reverse edges capacity
From: Olivier Tournaire (olitour_at_[hidden])
Date: 2013-12-20 09:14:07

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?

Note that I use the algorithm with this method:

_minEnergy = boykov_kolmogorov_max_flow(_graph, _source, _sink);

Any help would be appreciated.

Regards,

Olivier