I'm doing a college job where I need to implement the Ford-Fulkerson algorithm in Python. But I'm having a hard time finding a way up in the residual graph (path function). I do not know if it is the recursion that is not working, or the for. I'm still a beginner in python, however it can be a problem in logic.
graph={}
graphIni={}
caminho=[]
graphresidual={}
s = 0
t = 2
def criaGrafo():
lista = input().split(' ')
nVertice = int(lista[0])
nAresta = int(lista[1])
s = int(lista[2])
t = int(lista[3])
graph[s]= {}
for x in range(0,nVertice):
if(x!=t and x!=s):
auxl={}
graph[x]=auxl
graph[t]= {}
for x in range(0,nAresta):
lista=input().split(" ")
v1 = int(lista[0])
v2 = int(lista[1])
capMax = int(lista[2])
graph[v1].update({v2:capMax})
graphIni[s]= {}
for x in range(0,nVertice):
if(x!=t and x!=s):
auxl={}
graphIni[x]=auxl
graphIni[t]= {}
for x in graph:
for y in graph[x]:
graphIni[x].update({y:0})
def minimo(u, v):
if(u < v):
return u
else:
return v
def Graforesidual(graph, graphIni):
for x in graph:
aux = {}
graphresidual[x] = aux
for x in graph:
for y in graph[x]:
graphresidual[x].update({y:(graph[x][y] - graphIni[x][y])})
if(graphIni[x][y] != 0):
graphresidual[y].update({x:graphIni[x][y]})
return graphresidual
def Caminho(graphresidual, u, t, caminho):
if(u == t):
return caminho
else:
for x in graphresidual[u]:
caminho.append(x)
Caminho(graphresidual, x, t, caminho)
if caminho[-1::] == t:
return caminho
if(caminho[-1::] != t):
print("nao tem caminho")
criaGrafo()
Graforesidual(graph, graphIni)
graphresidual = Graforesidual(graph, graphIni)
print(graphresidual)
print(Caminho(graphresidual, s, t, caminho))
An example input would be:
6 9 0 5
0 1 15
0 3 20
1 2 10
1 4 5
2 4 15
2 5 10
3 1 5
3 4 8
4 5 20