def maximum_flow(graph, source, sink, caps = None):
<EOL>if caps == None:<EOL><INDENT>caps = {}<EOL>for edge in graph.edges():<EOL><INDENT>caps[edge] = graph.edge_weight((edge[<NUM_LIT:0>],edge[<NUM_LIT:1>]))    <EOL><DEDENT><DEDENT>f = {}.fromkeys(graph.edges(),<NUM_LIT:0>)    <EOL>label = {}.fromkeys(graph.nodes(),[])<EOL>label[source] = ['<STR_LIT:->',float('<STR_LIT>')]<EOL>u = {}.fromkeys(graph.nodes(),False)<EOL>d = {}.fromkeys(graph.nodes(),float('<STR_LIT>'))<EOL>q = [source]<EOL>finished = False<EOL>while not finished:<EOL><INDENT>for i in range(len(q)):<EOL><INDENT>if not u[q[i]]:<EOL><INDENT>v = q.pop(i)<EOL>break<EOL><DEDENT><DEDENT>for w in graph.neighbors(v):<EOL><INDENT>if label[w] == [] and f[(v,w)] < caps[(v,w)]:<EOL><INDENT>d[w] = min(caps[(v,w)] - f[(v,w)],d[v])<EOL>label[w] = [v,'<STR_LIT:+>',d[w]]<EOL>q.append(w)<EOL><DEDENT><DEDENT>for w in graph.incidents(v):<EOL><INDENT>if label[w] == [] and f[(w,v)] > <NUM_LIT:0>:<EOL><INDENT>d[w] = min(f[(w,v)],d[v])<EOL>label[w] = [v,'<STR_LIT:->',d[w]]<EOL>q.append(w)<EOL><DEDENT><DEDENT>u[v] = True<EOL>if label[sink] != []:<EOL><INDENT>delta = label[sink][-<NUM_LIT:1>]<EOL>w = sink<EOL>while w != source:<EOL><INDENT>v = label[w][<NUM_LIT:0>]<EOL>if label[w][<NUM_LIT:1>] == '<STR_LIT:->':<EOL><INDENT>f[(w,v)] = f[(w,v)] - delta<EOL><DEDENT>else:<EOL><INDENT>f[(v,w)] = f[(v,w)] + delta<EOL><DEDENT>w = v<EOL><DEDENT>label = {}.fromkeys(graph.nodes(),[])<EOL>label[source] = ['<STR_LIT:->',float('<STR_LIT>')]<EOL>q = [source]<EOL>u = {}.fromkeys(graph.nodes(),False)<EOL>d = {}.fromkeys(graph.nodes(),float('<STR_LIT>'))<EOL><DEDENT>finished = True<EOL>for node in graph.nodes():<EOL><INDENT>if label[node] != [] and u[node] == False:<EOL><INDENT>finished = False<EOL><DEDENT><DEDENT><DEDENT>cut = {}<EOL>for node in graph.nodes():<EOL><INDENT>if label[node] == []:<EOL><INDENT>cut[node] = <NUM_LIT:1><EOL><DEDENT>else:<EOL><INDENT>cut[node] = <NUM_LIT:0><EOL><DEDENT><DEDENT>return (f,cut)<EOL>
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