0 Replies - 16524 Views - Last Post: 20 December 2012 - 08:19 PM Rate Topic: -----

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10387
  • View blog
  • Posts: 38,438
  • Joined: 27-December 08

Data Structures- Graph Theory: Ford-Fulkerson

Posted 20 December 2012 - 08:19 PM

This tutorial will introduce the concept of network flow, including optimizing the flow through a network. The Ford-Fulkerson algorithm will be used to accomplish this.

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:
Attached Image

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:
Attached Image

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)


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)


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)


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:
Attached Image

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


Is This A Good Question/Topic? 1
  • +

Page 1 of 1