First, let's introduce the concept of a network. It is a type of Graph, specifically a directed graph, with capacities on the flow volumes through edges. The flow originates at a vertex called the source and travels to a destination vertex known as a sink. There can be many sources and sinks, but for the sake of this tutorial, networks with only a single source and sink will be examined. Applying this to real life, pipes can carry only certain amounts of water and computer networks have transfer and bandwidth limits. So network flow optimization has a very practical application.

An example of a network is shown below:

Next, let's discuss the idea behind Network Flow Optimization. The initial state of the network contains capacities and initial flow values. The idea is to find paths from the source to the sink along which additional flow can be provided. Such paths are known as augmenting paths. Once no additional augmenting paths can be found, the algorithm terminates. It is important to note as well that flow can be "pushed back" or rerouted from incoming edges. For example, if Vertex C has incoming flow from D, it can push some of the flow from D back (or re-route it) along a different path.

Now that there is a basic understanding of network flow optimization, let's examine specifically how the Ford-Fulkerson algorithm solves this problem. Each iteration of the Ford-Fulkerson algorithm finds a single flow augmenting path. When finding the augmenting path, a greedy approach is used, adding as much flow as possible. However, the amount of flow that actually reaches the sink is then added to edges where flow is pushed forward, and subtracted from edges where flow is pushed back or re-routed. The updated network is then re-evaluated. This process continues until no more augmenting paths can be found.

Flow is added initially from the source. It then tries to push flow forward or backwards to adjacent vertices in a breadth-first order, ignoring vertices that have already been evaluated. Those vertices that can accept additional flow do so and are added to a Queue, and then evaluated using the same process until an augmenting path is found or the queue is empty. When pushing flow, there is the constraint that no additional flow can be moved forward than came from the previous vertex. The source is not subject to this constraint.

The last path found by the Ford-Fulkerson algorithm is not an augmenting path. Instead, it outlines the boundaries for the minimum cut, which ensures that the flow from the source is equal to that received from the sink. A cut has two complementary vertex sets separating the source and sink. The last path found by the Ford-Fulkerson algorithm comprises one vertex set in the minimum cut.

Some Pseudo-Code:

fordFulkerson(Network graph(Source, Sink)) flowIncrease <-- 0 do flowIncrease <-- augmentFlow(graph) while flowIncrease > 0 end fordFulkerson augmentFlow(Network graph(Source, Sink)) queue <-- new vertex queue for each adjacent vertex from Source If the direction is Source -> vertex slack <- vertex.capacity - vertex.flow If slack > 0 label <-- (forward, slack, Source) vertex.setLabel(label) queue.push(label) Else slack <-- vertex.flow If slack > 0 label <-- (backwards, slack, Source) vertex.setLabel(label) queue.push(label) end for while the queue isn't empty AND the Sink has not been reached temp <-- queue.poll for each unlabeled adjacent vertex from temp If the direction is temp -> vertex slack <- vertex.capacity - vertex.flow If slack > 0 label <-- (forward, slack, temp) vertex.setLabel(label) queue.push(label) Else slack <-- vertex.flow If slack > 0 label <-- (backwards, slack, temp) vertex.setLabel(label) queue.push(label) end while temp <-- Sink //if the sink hasn't been reached, //then there is no augmentation if Sink.getLabel() is NULL return 0 augmentation <-- temp.getLabel().getSlack() while temp != Source label <-- temp.getLabel() parent <-- label.getParent() if label.getDirection() == forward increase the flow between temp and parent by augmentation else decrease the flow between temp and parent by augmentation temp <-- parent end while return augmentation end augmentFlow

Now, let's work through an example:

Here, let Vertex A be the source and Z be the sink.

The only vertex A can send flow to is vertex B, which can accept at most 5 units of flow. So create a label for B, denoting its parent, flow increase, and direction; and add it to the Queue:

Quote

Queue (Vertex, Direction, Flow Increase, Parent):

-(B, +, 5, A)

-(B, +, 5, A)

Next, let's evaluate B. Its adjacent vertices are D and E. Vertex D can re-route its 5 units of flow from B to another vertex, so add it to the Queue. Vertex E accepts forward flow from B; but since it is at capacity, it cannot accept additional flow. Therefore, ignore it.

Quote

Queue (Vertex, Direction, Flow Increase, Parent):

-(D, -, 5, B)

-(D, -, 5, B)

Next, let's evaluate D. Its only viable adjacent vertex is F, where it can push forward 3 units of flow, which is less than the 5 it received. Veretex F has a capacity of 7 and currently has 4 units of flow coming from D before augmentation. Now push F onto the Queue.

Quote

Queue (Vertex, Direction, Flow Increase, Parent):

-(F, +, 3, D)

-(F, +, 3, D)

Continuing along this process, the following flow pushes are made:

-F pushes 2 units back to E, as it cannot push back or re-route more flow than is coming in.

-E then pushes 2 units of flow to the sink Z, which is still below capacity.

The Augmenting Path is: A -> B <- D -> F <- E -> Z, with a flow increase of 2. The revised network is below:

When we evaluate the network using the algorithm again, we are stuck at F. So since no augmenting path can be created, the minimum cut is ({A, B, D, F}, {E, Z}), and the maximal flow that can reach the sink is 15.

This post has been edited by **macosxnerd101**: 20 December 2012 - 10:00 PM

Reason for edit:: Added pseudo-code per request