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
MultiQuote
| 