(graph, source, sink, caps = None)
return (f,cut)
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
Find a maximum flow and minimum cut of a directed graph by the Edmonds-Karp algorithm.
Find a maximum flow and minimum cut of a directed graph by the Edmonds - Karp algorithm .
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)
def maximum_flow ( graph , source , sink , caps = None ) : #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 )