ford_fulkerson.py

def add_edge(a,b,x):
    graph[a][b]+=x


n=5 
graph=[[0]*(n+1) for _ in range(n+1)]
seen=[False]*(n+1)
path=[]
result=[]
found=False
min_weight=10**9
# add_edge(1,3,4)
# add_edge(1,2,3)
# add_edge(2,4,8)
# add_edge(3,4,2)
# add_edge(4,5,3)
##############
add_edge(1,2,4)
add_edge(1,3,6)
add_edge(2,3,8)
add_edge(2,4,3)
add_edge(3,5,4)
add_edge(4,5,6)

def print_graph(graph):
    for i in range(1,len(graph)):
        print(graph[i][1:])

print_graph(graph)

def dfs(x,z):
    global found, result
    if seen[x]:
        return
    path.append(x)
    seen[x]=True
    if x==z and not found:
        found=True
        result=path[:]
    for i in range(1,n+1):
        if graph[x][i]>0:
            dfs(i,z)
    path.pop()
    


def augment_paths():
    global min_weight,graph,result,seen,found,path
    while True: #!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        dfs(1,5)
        print(result)
        print_graph(graph)
        if not found: #!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            break
        path=[]
        seen=[False]*(n+1)
        found=False
        result=[]
        for i in range(len(result)-1):
            #print(result[i],result[i+1],graph[result[i]][result[i+1]])
            min_weight=min(min_weight, graph[result[i]][result[i+1]])

        for i in range(len(result)-1):
            graph[result[i]][result[i+1]] -=min_weight
            graph[result[i+1]][result[i]] +=min_weight
        
    


augment_paths()
print('--')
print_graph(graph)
print(path)
# dfs(1,5)
print(found)
print(result)
    
# print(min_weight)
# print_graph(graph)
# print(graph)