def BFS(C, F, source, sink):
queue = [source] # the BFS queue
paths = {source: []} # 1 path ending in the key
while queue:
u = queue.pop(0) # next node to explore (expand)
for v in range(len(C)): # for each possible next node
# path from u to v? and not yet at v?
if C[u][v] - F[u][v] > 0 and v not in paths:
paths[v] = paths[u] + [(u,v)]
if v == sink:
return paths[v] # path ends in the key!
queue.append(v) # go from v in the future
return None
def max_flow(C, source, sink):
n = len(C) # C is the capacity matrix
F = [[0] * n for i in range(n)] # F is the flow matrix
# residual capacity from u to v is C[u][v] - F[u][v]
while True:
path = BFS(C, F, source, sink)
if not path: break # no path - we're done!
edge_flows = [C[u][v]-F[u][v] for u,v in path]
path_flow = min( edge_flows )
print "Augmenting by", path_flow
for u,v in path: # traverse path to update flow
F[u][v] += path_flow # forward edge up
F[v][u] -= path_flow # backward edge down
return sum([F[source][i] for i in range(n)])
if __name__ == "__main__":
# make a capacity graph
# node A B C D E F
C = [ [ 00, 16, 13, 00, 00, 00 ], # A
[ 00, 00, 10, 12, 00, 00 ], # B
[ 00, 04, 00, 00, 14, 00 ], # C
[ 00, 00, 9, 00, 00, 20 ], # D
[ 00, 00, 00, 7, 00, 4 ], # E
[ 00, 00, 00, 00, 00, 00 ] ] # F
print "C is", C
source = 0 # A
sink = 5 # F
max_flow_value = max_flow( C, source, sink )
print "max_flow_value is", max_flow_value