Push-relabel gap heuristics

Question

I don't understand how to implement gap heuristics with push relabel. Wiki described it like this:

"In gap relabeling heuristic we maintain an array A of size n, holding in A[i] the number of nodes for each label (up to n). If a label d is found, such that A[d] = 0, then all nodes with label > d are relabeled to label n."

Use a gap heuristic. If there is a 'k' such that for no node height(u) =k, you can set height(u) = max(height(u), height(source) +1) for all nodes except source, for which height(u) >k. This is because any such 'k' represents a minimal cut in the graph, and no more flow will go from the nodes S={u where height(u) > k} to nodes in T={v, where height(v)0. But then height(u) > height(v)+1 , contradicting height(u) > k and height(v) < k.

Can someone explain to me in pseudocode how to add the gap heuristic to a FIFO push-relabel as shown in wiki's sample code?

Thanks, Vince

Answer 1

It might be a little late but here is a link to a Stanford University notebook where you can find a push-relabel maximum flow using a Gap Heuristic in C. I hope it helps you.

http://www.stanford.edu/~liszt90/acm/notebook.html#file3