push_preflow.py

def Push_Relabel(graph,s,t):

    if s < 0 or t < 0 or s > len(graph) - 1 or t > len(graph) - 1:
        return "Error input"
    if len(graph) == 0:
        return "No graph to process"
    
    n = len(graph)

    h = [0] * n
    h[s] = n
    maxh = [0] * n

    f = []

    for i in range(0,n):
        if len(graph[0]) != n:
            return "Wrong dimension of graph"
        f.append([0] * n)
    
    e = [0] * n

    for i in range (0,n):
        f[s][i] = graph[s][i]
        if f[s][i] != 0:
            f[i][s] = -f[s][i]
        e[i] = graph[s][i]
    
    
    sz = 0

    while True:
        print("HEIGHT",h)
        print("EXCESS",e)

        if sz == 0:
            for i in range(0,n):
                if i != s and i != t and e[i] > 0:
                    if sz !=0 and h[i] > h[maxh[0]]:
                        sz = 0
                    maxh[sz] = i
                    sz+=1
                    
        if sz == 0 :
            break
            
        
        while sz != 0:

            i = maxh[sz - 1]
            pushed = False

            j = 0

            while j < n and e[i] != 0:
                
                if h[i] == h[j] + 1 and graph[i][j] - f[i][j] > 0:
                    df = min(graph[i][j] - f[i][j], e[i])
                    f[i][j] += df
                    f[j][i] -= df
                    e[i] -= df
                    e[j] += df
                    if e[i] == 0:
                        sz-=1
                    pushed = True

                j+=1
        
            if not pushed:
                h[i] = float('inf')
                for j in range(0,n):
                    if h[i] > h[j] + 1 and graph[i][j] - f[i][j] > 0:
                        h[i] = h[j] + 1
            
                if h[i] > h[maxh[0]]:
                    sz = 0
                    break
    flow = 0

    for i in range(0,n):
        flow+=f[s][i]
        
    return flow