min_st_cut does not compute the minimum s-t cut
Currently, min_st_cut() labels all vertices reachable from the source by edges whose residual capacity is larger than zero. The labeled nodes are taken to be source side of the cut.
Unfortunately, this is incorrect.
The correct thing to do is to label all vertices reachable from the source in the residual graph. The difference is that the residual graph, in addition to the edges with nonzero residual capacity, also contains reversed edges for all edges whose flow nonzero.
A simple example is a graph with four vertices S, A, B, and T, with capacities:
c(S,A)=2, c(S,A)=3, c(S,B)=1, and C(B,T)=2
The maximum flow is 2. If the max flow chosen is S->A->B->T, then min_st_cut() finds the cut between {S,B} and {A,T}, which has capacity 4 instead of the minimum cut of size 2 between {S,A,B} and {T}.
A simple example program:
from graph_tool.all import *
G = Graph()
s, a, b, t = G.add_vertex(4)
cap = G.new_edge_property('int')
edges = [ (s,a,2), (s,b,1), (a,b,3), (b,t,2) ]
for u,v,c in edges:
e = G.add_edge(u, v)
cap[e] = c
res = push_relabel_max_flow(G, s, t, cap)
mc, par = min_st_cut(G, s, res)
for e in G.vertices():
print par[e]
The output is 1 0 1 0, standing for the cut {S,B}.
Baruch