4.6. The labelling algorithm

The above algorithm works if we want get a maximal flow, but the efficiency of the algorithm is not too good. The first efficient algorithm for the max flow problem was investigated by L. R. Ford and D. L. Fulkerson in 1957. It was the labelling method. To understand this method we need to introduce some definitions.

Let be an arc in a directed graph and, be the capacity of this edge and let be the flow in the arc. Then we call a

- f-zero if ,

- f-positive if ,

- f-unsaturated if ,

- f-saturated if .

We recall the definition of ε:

Let be a directed graph and let f be a flow in , and let a be an arc in a path . Then

then

From the above definition it is clear that is the largest value by which the flow along P can be increased without violating the condition .

We will say that the path P is f-saturated if and f-unsaturated if . An f-incrementing path is an f-unsaturated path from the source s to the sink t.

The existence of an f-incrementing path P implies that f is not a maximum flow. Therefore, by sending an augmenting flow along P one can obtain a new flow defined by

Clearly, , and the following theorem is true.

Theorem 4.15. A flow in a directed graph is a maximum flow iff the graph contains no f-incrementing path.

The following example shows a graph with an actual flow. In this graph we consider an incrementing path: .

The starting flow value is . For the arcs the ε values are: , , , .

Therefore . The right-hand side graph shows the revised flow which based on the path P. Here the flow value is .

 

 

Figure 4.5. An incrementing-path and the revised flow.

So, we can construct an algorithm: let us start with a known flow, for instance the zero flow, and the algorithm recursively constructs a sequence of flows of increasing value, and terminates with a maximum flow.

How can we find an incrementing-path?

A tree T in a directed graph is an f-unsaturated tree if

-

-for every vertex v of T, the unique path in T is an f-unsaturated path.

The search for an f-incrementing path involves growing an f-unsaturated tree in .

- Initially, T consists of just the source s.

- At any stage, there are two ways in which the tree may grow:

- If there exists an f-satureted arc a in , where , then both a and its head are adjoined to T.

- If there exists an f-positive arc a in , then both a and its tail are adjoined to T.

It is clear, that the resulting T either reaches the sink t, or stops growing before reaching t.

- If the sink has been reached, then the -path in T is our desired f-incrementing path.

- If T stops growing before reaching t, then f is a maximum flow.

As an unsaturated tree has been found, we need to choose an incrementing-path. To do that we will use the "first-labelled, first-scanned" procedure that was investigated by Edmonds and Karp (1972). The labelling procedure:

- Assign to the source s the label .

- If a is an f-unsaturated arc whose tail u is already labelled but whose head v is not, then v is labelled .

- If a is an f-positive arc whose head u is already labelled but whose tail v is not, then v is labelled .

In the above cases v is said to be labelled based on u.

To scan a labelled vertex u is to label all unlabelled vertices that can be labelled based on u.

The labelling procedure is continued until either the sink t is labelled (breakthrough) or all labelled vertices have been scanned and no more vertices can be labelled (implying that f is a maximum flow).

 Figure 4.6. The algorithm "first-labelled, first-scanned"