Boost Users :
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:
> 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
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net