The Ford-Fulkerson algorithm is an algorithm that tackles the max-flow min-cut problem. That is, given a network with vertices and edges between those vertices that have certain weights, how much "flow" can the network process at a time? Flow can mean anything, but typically it means data through a computer network.
It was discovered in 1956 by Ford and Fulkerson. This algorithm is sometimes referred to as a method because parts of its protocol are not fully specified and can vary from implementation to implementation. An algorithm typically refers to a specific protocol for solving a problem, whereas a method is a more general approach to a problem.
The Ford-Fulkerson algorithm assumes that the input will be a graph, , along with a source vertex, , and a sink vertex, . The graph is any representation of a weighted graph where vertices are connected by edges of specified weights. There must also be a source vertex and sink vertex to understand the beginning and end of the flow network.
Ford-Fulkerson has a complexity of where is the maximum flow of the network. The Ford-Fulkerson algorithm was eventually improved upon by the Edmonds-Karp algorithm, which does the same thing in time, independent of the maximum flow value.
The intuition behind the algorithm is quite simple (even though the implementation details can obscure this). Imagine a flow network that is just a traffic network of cars. Each road can hold a certain number of cars. This can be illustrated by the following graphic.
The intuition goes like this: as long as there is a path from the source to the sink that can take some flow the entire way, we send it. This path is called an augmenting path. We keep doing this until there are no more augmenting paths. In the image above, we could start by sending 2 cars along the topmost path (because only 2 cars can get through the last portion). Then we might send 3 cars along the bottom path for a total of 5 cars. Finally, we can send 2 more cars along the top path for two edges, send them down to bottom path and through to the sink. The total number of cars sent is now 7, and it is the maximum flow.
Why could we only send 2 cars in the last augmenting path in the previous example?We had already sent two cars along the top path for the first augmenting path. That means that the first two edges along that top path are already at capacity. So, those edges can't fit any more than 2 cars, so they are the limiting factors in the last augmenting path.
This is why calculating augmenting paths gets tricky for larger and more complicated flow networks. To handle this, residual graphs are generated after each augmenting path is found and maximized. Residual graphs show the differences between various paths' capacity and their current flow and allow future augmenting paths to be calculated accurately.
The pseudo-code for this method is quite short; however, there are some functions that bear further discussion. The simple pseudo-code is below.
This pseudo-code is not written in any specific computer language. Instead, it is an informal, high-level description of the algorithm.
Ford-Fulkerson Algorithm Graph , source , sink
1 2 3 4 5 6 7
Basically, what this simplified version says is that as long as there is a path from the source to the sink that can handle more flow, send that flow. Here is a version of the pseudo-code that explains the flow augmentation more in depth:
1 2 3 4 5 6 7 8 9 10 11 12
This algorithm is more well-defined. The only ambiguous point is the 'foward edge' terminology on line 8. When a residual graph, , is created, edges can be created that go in the opposite direction when compared to the original graph. An edge is a 'forward edge' if the edge existed in the original graph, . If it is a reversal of an original edge, it is called a 'backwards edge.'
Residual graphs are an important middle step in calculating the maximum flow. As noted in the pseudo-code, they are calculated at every step so that augmenting paths can be found from the source to the sink. To understand how these are created and how they are used, we can use the graph from the intuition section.
However, one important attribute is important to understand before looking at residual graphs. Residual capacity is a term used in the above pseudo-code, and it plays an important role in residual graph creation. Residual capacity is defined as the new capacity after a given flow has been taken away. In other words, for a given edge , the residual capacity, is defined as
However, there must also be a residual capacity for the reverse edge as well. The max-flow min-cut theorem states that flow must be preserved in a network. So, the following equality always holds:
With these tools, it is possible to calculate the residual capacity of any edge, forward or backward, in the flow network. Then, those residual capacities are used to make a residual network, .
Taking the original intuition network and adding labels to the vertices, we now have this:
It was shown that 2 units of flow can be pushed along the top-most path initially. When this happens, only three edges are affected: (S, A), (A, B), and (B, T). (S, A) and (A, B) are affected in the same way because they have the same capacity. Two things happen:
- In the forward direction, the edges now have a residual capacity equal to . The flow is equal to 2, so the residual capacity of (S, A) and (A, B) is reduced to 2, while the edge (B, T) has a residual capacity of 0.
- In the backward direction, the edges now have a residual capacity equal to . Because of flow preservation, this can be written as . And since the capacity of those backward edges was initially 0, all of the backward edges (T, B), (B, A), and (A, S) now have a residual capacity of 2.
When a new residual graph is constructed with these new edges, any edges with a residual capacity of 0—like (B, T)—are not included.
Now, a new augmenting path must be found the top-most path can never be used again because the edge (B, T) was erased The bottom path can be chosen and flow of 3 can be sent along it. The resulting graph is as follows:
Finally, a flow of 2 can be sent along the path [(S, A), (A, B), (B, C), (C, D), (D, T)] because the minimum residual capacity along that path is 2. The final residual graph after this is done is as follows:
There are not more paths from the source to the sink, so there can be no more augmenting paths. Therefore, the loop is complete. The flow, 7, is a maximum flow.
The Ford-Fulkerson algorithm is straightforward to implement once the concept of the residual graphs is understood. As noted in the introduction to this wiki, this algorithm is often called a method because the method of finding augmenting paths in a residual graph is not fully specified. This implementation is one way of doing this.
The following implementation is not battle-tested, and is only meant to be a learning tool.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
The class defined on line
1 is a simple
Vertex class. It only has a name, which we use for edge creation (and debugging), whether or not the vertex is a source or a sink. On line
Edge class is defined. This class has a starting vertex (just the name of the vertex, not the class instance), an ending vertex, a capacity, a flow, and a pointer to the return edge which is used in the residual graph. The capacity of an edge is the total weight it can carry whereas an edge's flow is the weight it is currently carrying.
FlowNetwork class defined on line
15 has two attributes. The
vertices attribute is a list of all of the instances of vertices in the graph. This list holds entire objects, linking a vertex's name to its source and sink attributes. The
network dictionary is a data structure that maps every vertex's name to all of the edges coming out of the corresponding vertex. By simply having the vertex's name act as the dictionary key, we can easily switch back and forth between 'vertices' and 'network' to suit the needs of the algorithm.
20-48 contain various helper functions that make later functions easier and help reduce code duplication. For example, the function on line
getVertex() takes in a vertex name and goes to find the entire
Vertex object in
addVertex() on line
50 adds a vertex to the graph after it checks various error cases to make sure the vertex can be added. It adds the entire vertex to the
vertices list on line
62 and adds the vertex name to an empty list of edges on line
addEdge() on line
65 first checks that the starting and ending vertices are both in the graph and that they are not the same vertex. Then, it creates the new edge and a corresponding returning edge with capacity 0. It then adds the new edge to the network map on line
77 and adds the return edge to the same map on line
The 'getPath()' function on line
81 does the important work in this class. It is a recursive function that walks through the flow network starting at a given vertex and calculates residual capacity for each edge. This residual capacity is used to decide how much flow to send along a given path in the next function. The path is grown until it reaches the end of the flow network; at that point the base case for the recursion is called on line
82 and the function ends.
calculateMaxFlow() on line
91 is what calls
getPath with the correct parameters and adds up the max flow. It first finds the source and sink of the network. Then, it calculates an initial augmenting path on line
96. Then, we start the important Ford-Fulkerson method and continue to calculate flow while there still is a path. While there is a path, an augmenting capacity is in each edge of the path, so a flow can be calculated on line
98. That flow is added to the forward edges and subtracted from the reverse edges. Then, another path is calculated and the process resumes. Finally, we only need to calculate the total flow coming out of the source because this is the exact amount of flow through the entire network (since we only have one source).
1 2 3 4 5 6 7 8 9 10 11
The flow network is created, so its
network can be inspected. However, these attributes contain full objects—the
vertices attribute contains
Vertex objects and the
network attribute contains
Edge objects. So we need to clean it up a little.
1 2 3 4
Remember that the edges in
getEdges() also contains all of the reverse edges. Now, this class can calculate its own maximum flow.
This is the same answer we found by inspection earlier.
What happens to the 'capacity' and 'flow' attributes of the edges in 'getEdges()' when 'fn.calculateMaxFlow()' is called?
Hint: This answers for forward edges and backward edges are a little different.Once this procedure has been completed, all forward edges are filled up as much as they can be, and the reverse edges reflect that filled-up status. As the max-flow min-cut theorem states, the total flow of the network must be preserved. So, for a given edge with endpoints , the flows of the forward and backward edges will sum to 0, just as when the process began.
Here is the difference before and after calling
1 2 3 4 5 6
>>> ['%s -> %s; %s/%s' % (e.start, e.end, e.flow, e.capacity) for e in fn.getEdges()] ['a -> s; -4/0', 'a -> b; 4/4', 'c -> s; -3/0', 'c -> d; 5/6', 'c -> b; -2/0', 'b -> a; -4/0', 'b -> t; 2/2', 'b -> c; 2/3', 'd -> c; -5/0', 'd -> t; 5/6', 's -> a; 4/4', 's -> c; 3/3', 't -> b; -2/0', 't -> d; -5/0'] >>> fn.calculateMaxFlow() 7 >>> ['%s -> %s; %s/%s' % (e.start, e.end, e.flow, e.capacity) for e in fn.getEdges()] ['a -> s; -4/0', 'a -> b; 4/4', 'c -> s; -3/0', 'c -> d; 5/6', 'c -> b; -2/0', 'b -> a; -4/0', 'b -> t; 2/2', 'b -> c; 2/3', 'd -> c; -5/0', 'd -> t; 5/6', 's -> a; 4/4', 's -> c; 3/3', 't -> b; -2/0', 't -> d; -5/0']
If you draw out all of the edges, you will see that the graph you've created is the same that was made in the residual graphs section.
The analysis of Ford-Fulkerson depends heavily on how the augmenting paths are found. The typical method is to use breadth-first search to find the path. If this method is used, Ford-Fulkerson runs in polynomial time.
If all flows are integers, then the while loop of Ford-Fulkerson is run at most times, where is the maximum flow. This is because the flow is increased, at worst, by 1 in each iteration.
Finding the augmenting path inside the while loop takes where is the set of edges in the residual graph. This can be simplified to . So, the runtime of Ford-Fulkerson is