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