Find a maximum flow and minimum cut of a directed graph by the Edmonds-Karp algorithm.

    @type graph: digraph
    @param graph: Graph

    @type source: node
    @param source: Source of the flow

    @type sink: node
    @param sink: Sink of the flow

    @type caps: dictionary
    @param caps: Dictionary specifying a maximum capacity for each edge. If not given, the weight of the edge
    will be used as its capacity. Otherwise, for each edge (a,b), caps[(a,b)] should be given.
    
    @rtype: tuple
    @return: A tuple containing two dictionaries
        1. contains the flow through each edge for a maximal flow through the graph
        2. contains to which component of a minimum cut each node belongs

def maximum_flow(graph, source, sink, caps = None):
    """
    Find a maximum flow and minimum cut of a directed graph by the Edmonds-Karp algorithm.

    @type graph: digraph
    @param graph: Graph

    @type source: node
    @param source: Source of the flow

    @type sink: node
    @param sink: Sink of the flow

    @type caps: dictionary
    @param caps: Dictionary specifying a maximum capacity for each edge. If not given, the weight of the edge
    will be used as its capacity. Otherwise, for each edge (a,b), caps[(a,b)] should be given.
    
    @rtype: tuple
    @return: A tuple containing two dictionaries
        1. contains the flow through each edge for a maximal flow through the graph
        2. contains to which component of a minimum cut each node belongs
    """

    #handle optional argument, if weights are available, use them, if not, assume one
    if caps == None:
        caps = {}
        for edge in graph.edges():
            caps[edge] = graph.edge_weight((edge[0],edge[1]))    
    
    #data structures to maintain
    f = {}.fromkeys(graph.edges(),0)    
    label = {}.fromkeys(graph.nodes(),[])
    label[source] = ['-',float('Inf')]
    u = {}.fromkeys(graph.nodes(),False)
    d = {}.fromkeys(graph.nodes(),float('Inf'))
    #queue for labelling
    q = [source]

    finished = False
    while not finished:
        #choose first labelled vertex with u == false
        for i in range(len(q)):
            if not u[q[i]]:
                v = q.pop(i)
                break

        #find augmenting path
        for w in graph.neighbors(v):
            if label[w] == [] and f[(v,w)] < caps[(v,w)]:
                d[w] = min(caps[(v,w)] - f[(v,w)],d[v])
                label[w] = [v,'+',d[w]]
                q.append(w)
        for w in graph.incidents(v):
            if label[w] == [] and f[(w,v)] > 0:
                d[w] = min(f[(w,v)],d[v])
                label[w] = [v,'-',d[w]]
                q.append(w)

        u[v] = True

        #extend flow by augmenting path        
        if label[sink] != []:
            delta = label[sink][-1]
            w = sink
            while w != source:
                v = label[w][0]
                if label[w][1] == '-':
                    f[(w,v)] = f[(w,v)] - delta
                else:
                    f[(v,w)] = f[(v,w)] + delta
                w = v
            #reset labels
            label = {}.fromkeys(graph.nodes(),[])
            label[source] = ['-',float('Inf')]
            q = [source]
            u = {}.fromkeys(graph.nodes(),False)
            d = {}.fromkeys(graph.nodes(),float('Inf'))

        #check whether finished
        finished = True
        for node in graph.nodes():
            if label[node] != [] and u[node] == False:
                finished = False

    #find the two components of the cut
    cut = {}
    for node in graph.nodes():
        if label[node] == []:
            cut[node] = 1
        else:
            cut[node] = 0
    return (f,cut)