minimum_cut.py

# Minimum cut on Ford_Fulkerson algorithm.

test_graph= [
 [0, 16, 13, 0, 0, 0],
 [0, 0, 10, 12, 0, 0],
 [0, 4, 0, 0, 14, 0],
 [0, 0, 9, 0, 0, 20],
 [0, 0, 0, 7, 0, 4],
 [0, 0, 0, 0, 0, 0],
]


defbfs(graph, s, t, parent):
# Return True if there is node that has not iterated.
visited= [False] *len(graph)
queue= [s]
visited[s] =True

whilequeue:
u=queue.pop(0)
forindinrange(len(graph[u])):
ifvisited[ind] isFalseandgraph[u][ind] >0:
queue.append(ind)
visited[ind] =True
parent[ind] =u

returnvisited[t]


defmincut(graph, source, sink):
"""This array is filled by BFS and to store path
 >>> mincut(test_graph, source=0, sink=5)
 [(1, 3), (4, 3), (4, 5)]
 """
parent= [-1] * (len(graph))
max_flow=0
res= []
temp= [i[:] foriingraph] # Record original cut, copy.
whilebfs(graph, source, sink, parent):
path_flow=float("Inf")
s=sink

whiles!=source:
# Find the minimum value in select path
path_flow=min(path_flow, graph[parent[s]][s])
s=parent[s]

max_flow+=path_flow
v=sink

whilev!=source:
u=parent[v]
graph[u][v] -=path_flow
graph[v][u] +=path_flow
v=parent[v]

foriinrange(len(graph)):
forjinrange(len(graph[0])):
ifgraph[i][j] ==0andtemp[i][j] >0:
res.append((i, j))

returnres


if__name__=="__main__":
print(mincut(test_graph, source=0, sink=5))