3
$\begingroup$

I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues.

I have a specific instance of the problem here to illustrate my questions 1: enter image description here

a) For this problem instance, the "current preflow" is a state that is reached by my implemented max flow algorithm [[ even without global relabeling heuristic we reach this state ]]. Without applying any heuristics the algorithm proceeds to completion from this state giving the correct result.

b) The distance labels (in green) at this state represent a valid labeling as for every (u, v) \belong to E_{residual} d_u <= d_v + 1

Q1: The distance label (or height) is supposed to be a lower bound on the distance from the sink. However for several nodes in the residual graph (eg: 6, 7) this is not true. Eg. Node 7 has a distance label of 14...but clearly has a distance of 1 from the sink in the residual graph.

Q2: On running the global relabel at this stage, we get a labeling as seen in the extreme right. From this point on (depending on how frequently you do the global update), the algorithm can get stuck [[ deadlock ]] -- eg. nodes 6, 3 keep circulating flow between them as they each get relabeled to a higher height. If you run the global update before the reach the final height, you will reset the heights and the process repeats.

I am reasonably sure I am making a very trivial error but am unable to put my finger on it. Can someone help me with this issue? I am happy to provide a code snippet if that would help.

A couple more points that may be relevant:
-> I am implementing a single phase version of the push-relabel algorithm (ie. do not stop when you have a min. cut, but continue till you obtain a valid flow).
-> I am processing active vertices in FIFO order in the current problem instance. But I have a highest label first [3] implementation as well. I do not think this affects the two questions I have.

Thank You!

[[ This question has also been posted on programmers stackexchange -- I was unsure which forum is better for this question ]]

[2] A new approach to the maximum flow problem; A.Goldberg, R.Tarjan; JACM, Vol 35. Iss 4, 1988

[3] On implementing the push-relabel method for the maximum flow problem; B.V.Cherkassky, A.Goldberg

Improve this question
$\endgroup$
1
  • $\begingroup$ I assume s = 9, t = 10 in your example? $\endgroup$
    – Jo So
    Jul 4, 2015 at 18:55

1 Answer 1

Reset to default
1
$\begingroup$

Q1: The invariant goes the other way around: height[n1] <= height[n2] + 1 for all edges (n1,n2) in the residual graph.

As the sink (10) is not adjacent from (7) in the residual graph, the configuration height[7] == 14, height[10] == 0 is perfectly fine.

The other way around, (7) is adjacent from (10) in the residual graph, and indeed height[10] <= height[7] + 1.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.