Push-Relabel Discharge Step

Problem

Run the discharge loop of push-relabel on a single active node u.

While excess[u] is positive, push along the smallest-index neighbor v with residual capacity and height[u] == height[v] + 1; if no admissible edge exists, relabel height[u] = 1 + min height over residual neighbors. capacity and flow are n by n matrices, height and excess are arrays. Return [flow, height, excess] after the loop stops; a node with no residual edges keeps its excess.

Hint

Relabeling only fires when no neighbor sits one level below u.

Test cases

case 1

in: [4,[[0,3,2,0],[0,0,5,2],[0,0,0,3],[0,0,0,0]],[[0,0,0,0],[0,0,3,0],[0,-3,0,0],[0,0,0,0]],[4,1,0,0],[0,0,5,0],1]

expected: [[[0,0,0,0],[0,0,3,0],[0,-3,0,0],[0,0,0,0]],[4,1,0,0],[0,0,5,0]]

case 2

in: [3,[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]],[0,0,0],[0,1,0],1]

expected: [[[0,0,0],[0,0,0],[0,0,0]],[0,0,0],[0,1,0]]

case 3

in: [3,[[0,0,0],[0,0,5],[0,0,0]],[[0,0,0],[0,0,2],[0,-2,0]],[0,6,5],[0,0,2],1]

expected: [[[0,0,0],[0,0,2],[0,-2,0]],[0,6,5],[0,0,2]]

case 4

in: [4,[[0,4,1,0],[0,0,0,2],[0,0,0,3],[0,0,0,0]],[[0,0,0,0],[0,0,0,2],[0,0,0,0],[0,-2,0,0]],[5,1,0,0],[0,2,1,2],1]

expected: [[[0,0,0,0],[0,0,0,2],[0,0,0,0],[0,-2,0,0]],[5,1,0,0],[0,2,1,2]]

Starter codePython

def push_relabel_discharge(n, capacity, flow, height, excess, u):
    # Your code here
    pass

4 test cases · run your code against them in the editor