Goldberg Tarjan Push Relabel Algorithm Technische Universität München

The maximum s-t flow has a value of 6

The maximum flow problem

Suppose that we have a communication network, in which certain pairs of nodes are linked by connections; each connection has a limit to the rate at which data can be sent. Given two nodes on the network, what is the maximum rate at which one can send data to the other, assuming no other pair of nodes are attempting to communicate? (source)

This is a typical instance of a maximum flow problem: given an underlying network, where the edge weights denote the maximum possible capacity per edge, one wants to find out how much can be transerred over the edges from the source node s to the target node t.

This applet presents Goldberg Tarjan's Push Relabel algorithm with the FIFO selection rule which calculates the maximum s-t flow on a directed, weighted graph in $O(|V|^3)$ . This is much faster than the older Edmonds-Karp or Dinic's algorithm, which are based on the Ford-Fulkerson method.

What do you want to do first?

maxflow-graph-editor.svg

Legende

Which graph do you want to execute the algorithm on?

Start with an example graphs:

Select

Modify it to your desire:

To create a node, make a double-click in the drawing area.
To create an edge, first click on its start node and then on its end node. Alternatively, you may (single-)click on the drawing field to create a new node as end node.
Right-clicking deletes edges and nodes.

Maxflow specific:

The maximum capacity of an edge can be changed by a double-click on the edge or its weight.

Download the modified graph:

Download

Upload an existing graph:

What next?

Graph G maxflow-graph-algorithm-graph.svg

Legende

Residual Graph G' with axis: fixed maxflow-graph-algorithm-height.svg

Legende

Algorithm status

fast forward

Goldberg-Tarjan Push-Relabel maximum flow algorithm

Source and target node have been selected and are filled with green. Per default, these are the nodes with lowest and hightest id. If you want to change the target node, go back with prev.

Edges are annotated with preflow/capacity, where the latter corresponds to the thickness of the gray line.

Now the algorithm can begin. Click on next to start it

Last operation:

selected node 3 as target t

Variable status:

v	Q	e'	e*
-	{}	-	-

s ← pick(v)

t ← pick(v)

BEGIN

(* Initialize the preflow *)

FORALL e=(u,w) ∈ E

f(e) ← (u == s) ? c(e) : 0

IF u == s AND w ≠ t THEN Q.add(w)

(* Initialize the height function *)

h(s) ← |V|

FORALL v ∈ V\{s}

h(v) ← #arcs on shortest v-t path

(* Main Loop *)

WHILE Q ≠ ∅

v ← Q.pop()

WHILE e(v)>0 AND ∃ e'=(v,w)∈E'|h(v)==h(w)+1

(* PUSH *)

push min(e(v),c'(e')) flow from v to w

IF w ≠ s,t AND w ∉ Q THEN Q.add(w)

IF e(v)>0

(* RELABEL *)

h(v) ← 1+min({h(w)|e*=(v,w)∈E'})

Q.add(v)

END

Graph $G=(V,E)$ with capacities $c(e)\geq0 \forall e\in E$

Maximum Flows

In many applications one wants to know how much flow of a certain resource can simultaneously be transferred over a network from a to b. Depending on the context, flow can mean different things: The amount of water in a water pipe system in your city or the bandwidth of a computer network. However, the links in the network on paths from a to b can only handle flow up to their maximum capacity. One now seeks an assignemt of flow values to edges that fulfills all the capacity constraints of the edges and the flow conservation property on all the inner nodes, meaning we don't want leaks in our pipe system.

In general we speak of a flow. Therefore one assigns a flow value to each edge in our network, the graph

The Push-Relabel Algorithm of Goldberg and Tarjan computes the maximum s-t flow on a graph

Flow in graphs

digraph $G = (V, E)$

A flow network

$N=(G,c,s,t)$

capacity $\forall e \in E: c(e) \geq 0$
source and sink $s,t \in V$

A flow on N:

$f : E \rightarrow \mathbb{R}_o^+$

feasability / capacity constraints: $\forall e \in E : f(e) \leq c(e)$
flow conservation: $\forall u \in V \setminus \{s,t\} : \sum_{v \in V} f(u,v) = \sum_{v \in V} f(v,u)$

flow conservation:

$\forall u \in V \setminus\{s,t\}: e(u) = 0$

The residual network

create the residual network

For a (not necessarily feasible) flow

$f : E \rightarrow \mathbb{R}$ in

$G = (V,E)$ we can construct the so called residual network

$G' = (V, E')$ : Create the graph G0 from G by copying all nodes of G and adding edges to G0 under the following rules.

Idea of the algorithm

preflow

preflow:

$\forall u \in V \setminus\{s,t\}: e(u) \geq 0$

height function

height

$h(u), u \in V$

excess

exess

$e(u) = \sum_{v \in V} f(u,v) - \sum_{v \in V} f(v,u), u \in V$

What is the pseudocode of the algorithm?


Input:  a directed graph G=(V,E) with source node s, target node t.
        edge capacities c(e)>=0 for all edges
Output: A feasible maximum s-t flow f(e) satisfying:
        capacity constraints : 0<=f(e)<=c(e) for all edges
        flow conservation : f(u,v) == f(v,u) for all nodes except s,t
        The flow value of f(e) is maximized along all feasible flows

s ← pick(v)

t ← pick(v)

BEGIN

(* Initialize the preflow *)

FORALL e=(u,w) ∈ E

f(e) ← (u == s) ? c(e) : 0

IF u == s AND w ≠ t THEN Q.add(w)

(* Initialize the height function *)

h(s) ← |V|

FORALL v ∈ V\{s}

h(v) ← #arcs on shortest v-t path

(* Main Loop *)

WHILE Q ≠ ∅

v ← Q.pop()

WHILE e(v)>0 AND ∃ e'=(v,w)∈E'|h(v)==h(w)+1

(* PUSH *)

push min(e(v),c'(e')) flow from v to w

IF w ≠ s,t AND w ∉ Q THEN Q.add(w)

IF e(v)>0

(* RELABEL *)

h(v) ← 1+min({h(w)|e*=(v,w)∈E'})

Q.add(v)

END

How fast is the algorithm?

The running time of the generic Goldberg and Tarjan's push relabel algorithm (1988) is

$O(|V|^2|E|)$ .

This is the same asymptotical performance as that of Dinic's algorithm (1970), itself a tuned version of Edmonds–Karp algorithm $O(|V||E|^2)$ . These two classical maximum flow algorithms, emerging from the Ford-Fulkerson method (1956) are based on augmenting s-t paths and preserve the flow conservation property at inner nodes (e.g no excess) even during the course of the algorithm.

So why did we even need another method if it is not asymptotically faster than the existing ones and adds additional complexity? It turns out that we can further tune the generic algorithm by specifiing the order in which we choose the active nodes which we apply push and relabel operations to.

In particular, the variant implemented in this applet chooses the FIFO rule when selecting active nodes from the queue Q, which has a running time of $O(|V|^3)$ , which is better than the previous bound, especially on dense graphs (it is actually independend on the number of edges).

Certain modifications of the generic algorithm are among the fastest algorithms known today to solve maximum flow problems. For a comparison, please refer to this table.

The maximum flow problem

This applet presents Goldberg Tarjan's Push Relabel algorithm with the FIFO selection rule which calculates the maximum s-t flow on a directed, weighted graph in $O(|V|^3)$ . This is much faster than the older Edmonds-Karp or Dinic's algorithm, which are based on the Ford-Fulkerson method.

What do you want to do first?

Legende

Which graph do you want to execute the algorithm on?

Start with an example graphs:

Modify it to your desire:

Download the modified graph:

Upload an existing graph:

What next?

Legende

Legende

Algorithm status

First choose a source node

Then choose a target node

Goldberg-Tarjan Push-Relabel maximum flow algorithm

Initializing the preflow

Initializing the height function

Main loop

Check for admissible push operations

Push

Check for an admissible relabel operation

Relabel

Finished

Last operation:

Variable status:

Maximum Flows

Flow in graphs

The residual network

Idea of the algorithm

preflow

height function

excess

What is the pseudocode of the algorithm?

How fast is the algorithm?

When does the algorithm terminate?

Goldberg and Tarjan about the History of Efficient Maximum Flow Algorithms algorithms (video)

References

Literature

Web resources

The maximum flow problem

This applet presents Goldberg Tarjan's Push Relabel algorithm with the FIFO selection rule which calculates the maximum s-t flow on a directed, weighted graph in O(|V|3)O(|V|^3). This is much faster than the older Edmonds-Karp or Dinic's algorithm, which are based on the Ford-Fulkerson method.

What do you want to do first?

This applet presents Goldberg Tarjan's Push Relabel algorithm with the FIFO selection rule which calculates the maximum s-t flow on a directed, weighted graph in $O(|V|^3)$ . This is much faster than the older Edmonds-Karp or Dinic's algorithm, which are based on the Ford-Fulkerson method.