max flow min cut

graph-tool
1

hi, I'm relatively new to Python but i managed to get the build the
graph and attach the capacities to the edges and got some results from
the Maxflow algorithm. I what to used to implement the min cut and
separate the graph in two. Did anybody tried this?

Bernardo Mota

2

Hi Bernardo,

hi, I'm relatively new to Python but i managed to get the build the
graph and attach the capacities to the edges and got some results from
the Maxflow algorithm. I what to used to implement the min cut and
separate the graph in two. Did anybody tried this?

Knowing the max flow allows one to know automatically the _value_ of
minimum cut, but not the actual edges in the cut. In order to obtain the
min-cut from s to t, you have to do a slightly larger amount of work:
Just follow all vertices which are reachable from s via edges with
nonzero residual capacity. These form the s-side of the cut set.

Cheers,
Tiago