Push-relabel maximum flow algorithm

From Wikipedia, the free encyclopedia

The push-relabel algorithm is one of the most efficient algorithms to compute a maximum flow. The general algorithm has O(V2E) time complexity, while the implementation with FIFO vertex selection rule has O(V3) running time, the highest active vertex selection rule provides O(V^2\sqrt{E}) complexity, and the implementation with Sleator's and Tarjan's dynamic tree data structure runs in O(VElog(V2 / E)) time. In most cases it is more efficient than the Edmonds-Karp algorithm, which runs in O(VE2) time.

Contents

[edit] Algorithm

Given a flow network G(V,E) with capacity from node u to node v given as c(u,v), and source s and sink t, we want to find the maximum amount of flow you can send from s to t through the network. Two types of operations are performed on nodes, push and relabel. Throughout we maintain:

  • f(u,v). Flow from u to v. Available capacity is c(u,v) − f(u,v).
  • height(u). We only push from u to v if height(u) > height(v)
  • excess(u). Sum of flow to and from u.

After each step of the algorithm, the flow is a preflow, satisfying:

  • \ f(u,v) \leq c(u,v). The flow between u and v, does not exceed the capacity.
  • \ f(u,v) = - f(v,u). We maintain the net flow.
  • \ \sum_v f(u,v) = excess(u) \geq 0 for all nodes u \neq s. Only the source may produce flow.

Notice that the last condition for a preflow is relaxed from the corresponding condition for a legal flow in a regular flow network.

We observe that the longest possible path from s to t is | V | nodes long. Therefore it must be possible to assign height to the nodes such that for any legal flow, height(s) = | V | and height(t) = 0, and if there is a positive flow from u to v, height(u) > height(v). As we adjust the height of the nodes, the flow goes through the network as water through a landscape. Differing from algorithms such as Ford-Fulkerson, the flow through the network is not necessarily a legal flow throughout the execution of the algorithm.

In short words, the heights of nodes (except s and t) is adjusted, and flow is sent between nodes, until all possible flow has reached t. Then we continue increasing the height of internal nodes until all the flow that went into the network, but did not reach t, has flowed back into s. A node can reach the height 2 | V | − 1 before this is complete, as the longest possible path back to s excluding t is | V | − 1 long, and height(s) = | V | . The height of t is kept at 0.

[edit] Push

A push from u to v means sending a part of the excess flow into u on to v. Three conditions must be met for a push to take place:

  • excess(u) > 0. More flow into the node than out of it so far.
  • c(u,v) − f(u,v) > 0. Available capacity from u to v.
  • height(u) = height(v) + 1. Can only send to lower node.

We send an amount of flow equal to min(excess(u),c(u,v) − f(u,v)).

[edit] Relabel

Doing a relabel on a node u is increasing its height until it is higher than at least one of the nodes it has available capacity to. Conditions for a relabel:

  • excess(u) > 0. There must be a point in relabelling.
  • height(u) \leq height(v) for all v such that c(u,v) − f(u,v) > 0. The only nodes we have available capacity to are higher.

When relabelling u, we set height(u) to be the lowest value such that height(u) > height(v) for some v where c(u,v) − f(u,v) > 0.

[edit] Push-relabel algorithm

Push-relabel algorithms in general have the following layout:

  1. As long as there is legal push or relabel operation
    1. Perform a legal push, or
    2. a legal relabel.

The running time for these algorithms are in general O(V2E) (argument omitted).

[edit] Discharge

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

  1. As long as excess(u) > 0:
    1. If not all neighbours have been tried since last relabel:
      1. Try to push flow to an untried neighbour.
    2. Else:
      1. Relabel u

This requires that for each node, it is known which nodes have been tried since last relabel.

[edit] Relabel-to-front algorithm, ie. using FIFO heuristic

In the relabel-to-front algorithm, the order of the push and relabel operations is given:

  1. Send as much flow from s as possible.
  2. Build a list of all nodes except s and t.
  3. As long as we have not traversed the entire list:
    1. Discharge the current node.
    2. If the height of the current node changed:
      1. Move the current node to the front of the list
      2. Restart the traversal from the start of the list.

The running time for relabel-to-front is O(V3) (proof omitted).

[edit] Sample implementation

Python implementation:

def relabel_to_front(C, source, sink):
    n = len(C) # C is the capacity matrix
    F = [[0] * n for _ in xrange(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]

    height = [0] * n # height of node
    excess = [0] * n # flow into node minus flow from node
    seen   = [0] * n # neighbours seen since last relabel
    # node "queue"
    list   = [i for i in xrange(n) if i != source and i != sink]

    def push(u, v):
        send = min(excess[u], C[u][v] - F[u][v])
        F[u][v] += send
        F[v][u] -= send
        excess[u] -= send
        excess[v] += send

    def relabel(u):
        # find smallest new height making a push possible,
        # if such a push is possible at all
        min_height = height[u]
        for v in xrange(n):
            if C[u][v] - F[u][v] > 0:
                min_height = min(min_height, height[v])
                height[u] = min_height + 1

    def discharge(u):
        while excess[u] > 0:
            if seen[u] < n: # check next neighbour
                v = seen[u]
                if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
                    push(u, v)
                else:
                    seen[u] += 1
            else: # we have checked all neighbours. must relabel
                relabel(u)
                seen[u] = 0

    height[source] = n   # longest path from source to sink is less than n long
    excess[source] = Inf # send as much flow as possible to neighbours of source
    for v in xrange(n):
        push(source, v)

    p = 0
    while p < len(list):
        u = list[p]
        old_height = height[u]
        discharge(u)
        if height[u] > old_height:
            list.insert(0, list.pop(p)) # move to front of list
            p = 0 # start from front of list
        p += 1

    return sum([F[source][i] for i in xrange(n)])

Note that the above implementation is not very efficient. It is slower than Edmonds-Karp algorithm even for very dense graphs. To speed it up, you can do at least two things:

  1. Make neighbour lists for each node, and let the index seen[u] be an iterator over this, instead of the range 0..n − 1.
  2. 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(s) + 1) for all nodes except s 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 | height(u) > k} to the nodes T = {v | height(v) < k}. If (S,T) was not a minimal cut, there would be an edge (u,v) such that u \in S, v \in T and c(u,v) − f(u,v) > 0. But then height(u) would never be set higher than height(v) + 1, contradicting that height(u) > k and height(v) < k.

[edit] References

Languages