Ford-Fulkerson Python Algorithm

0

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
    
asked by anonymous 11.12.2018 / 19:38

0 answers