Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 20:45, 26 November 2013

Revision as of 20:51, 26 November 2013

Line 112:

===Discharge===

In ''relabel-to-front'', a ''discharge'' on a node ''u'' is the following:

# While <math>\mathrm{excess}(u) > 0</math>:

Function Discharge(u):

## If there are still neighbours in the neighbour list since the last ''relabel'':

while excess(u) > 0:

### Try to ''push'' flow to the next neighbour.

if (u.currentNeighbour != NIL):

## Else:

push(u, u.currentNeighbour);

### ''Relabel'' ''u''

u.currentNeighbour = u.nextNeighbour;

### Move pointer to head of neighbour list

else:

relabel(u);

u.currentNeighbour = u.headOfNeighbourList; //start again at the beginning of the neighbour list

===Relabel-to-Front===