Ford | Python program for implementation of Ford Fulkerson algorithm ; Returns true if there is a path from source ' s ' to sink ' t ' in residual graph . Also fills parent [ ] to store the path ; Mark all the vertices as not visited ; Create a queue for BFS ; Standard BFS Loop ; If we find a connection to the sink node , then there is no point in BFS anymore We just have to set its parent and can return true ; We didn 't reach sink in BFS starting  from source, so return false ; Returns tne maximum flow from s to t in the given graph ; This class represents a directed graph using adjacency matrix representation ; This array is filled by BFS and to store path ; There is no flow initially ; Augment the flow while there is path from source to sink ; Find minimum residual capacity of the edges along the path filled by BFS . Or we can say find the maximum flow through the path found . ; update residual capacities of the edges and reverse edges along the path ; Add path flow to overall flow ; Return the overall flow ; Create a graph given in the above diagram
from collections import defaultdict NEW_LINE INDENT def BFS ( self , s , t , parent ) : NEW_LINE INDENT visited = [ False ] * ( self . ROW ) NEW_LINE queue = [ ] NEW_LINE queue . append ( s ) NEW_LINE visited [ s ] = True NEW_LINE while queue : NEW_LINE INDENT u = queue . pop ( 0 ) NEW_LINE for ind , val in enumerate ( self . graph [ u ] ) : NEW_LINE INDENT if visited [ ind ] == False and val > 0 : NEW_LINE INDENT if ind == t : NEW_LINE INDENT visited [ ind ] = True NEW_LINE return True NEW_LINE DEDENT queue . append ( ind ) NEW_LINE visited [ ind ] = True NEW_LINE parent [ ind ] = u NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT def FordFulkerson ( self , source , sink ) : NEW_LINE DEDENT class Graph : NEW_LINE INDENT def __init__ ( self , graph ) : NEW_LINE INDENT self . graph = graph NEW_LINE self . ROW = len ( graph ) NEW_LINE parent = [ - 1 ] * ( self . ROW ) NEW_LINE DEDENT DEDENT max_flow = 0 NEW_LINE INDENT while self . BFS ( source , sink , parent ) : NEW_LINE INDENT path_flow = float ( " Inf " ) NEW_LINE s = sink NEW_LINE while ( s != source ) : NEW_LINE INDENT path_flow = min ( path_flow , self . graph [ parent [ s ] ] [ s ] ) NEW_LINE s = parent [ s ] NEW_LINE DEDENT v = sink NEW_LINE while ( v != source ) : NEW_LINE INDENT u = parent [ v ] NEW_LINE self . graph [ u ] [ v ] -= path_flow NEW_LINE self . graph [ v ] [ u ] += path_flow NEW_LINE v = parent [ v ] NEW_LINE DEDENT max_flow += path_flow NEW_LINE DEDENT return max_flow NEW_LINE DEDENT graph = [ [ 0 , 16 , 13 , 0 , 0 , 0 ] , [ 0 , 0 , 10 , 12 , 0 , 0 ] , [ 0 , 4 , 0 , 0 , 14 , 0 ] , [ 0 , 0 , 9 , 0 , 0 , 20 ] , [ 0 , 0 , 0 , 7 , 0 , 4 ] , [ 0 , 0 , 0 , 0 , 0 , 0 ] ] NEW_LINE g = Graph ( graph ) NEW_LINE source = 0 ; sink = 5 NEW_LINE print ( " The ▁ maximum ▁ possible ▁ flow ▁ is ▁ % d ▁ " % g . FordFulkerson ( source , sink ) ) NEW_LINE