Max Flow Ford Fulkerson | Network Flow | Graph Theory

Key Takeaways

[Music] hello and welcome my name is William and today we're going to start tackling the field of network flow by understanding what max flow is and in particular how we can use the ford-fulkerson method to find it finding the maximum flow begins with having what's called a flow graph this is a graph where edges have a certain maximum capacity which cannot be exceeded edges also have a flow value which is how many units of flow are passing through that edge initially the flow is 0 for all edges everywhere until we run a max flow algorithm on it there are also two special types of nodes in the flow graph the source node and the sink node usually denoted as s and T respectively the maximum flow problem asks with an infinite input source how much flow can we push through the network without exceeding the capacity of any edge and it's not all obvious how one should figure that out maximum flow can be used in numerous situations where edges and nodes can represent any number of things for instance suppose the edges are roads cars or pipes of water wires with electric current and so on each of those has a certain capacity value we can associate with the maximum flow on the other hand would represent the volume of water that can flow through the pipe so the number of cars the roads can sustain and traffic or the net electric current that your system can sustain effectively the maximum flow is a bottleneck value for the amount of traffic your network can handle and that is going from the source to the sink under all those constraints the maximum flow for this particular network is 7 and you can tell because after the maximum flow algorithm the sum of the flows attached to the sync node is seven running a maximum flow algorithm is used to determine how much flow each edge should receive to achieve the overall maximum flow note that there might be multiple ways of achieving the maximum flow by giving each edge different flow values but overall solutions will have the same maximum flow value let's dig deeper into how to find the maximum flow to begin with you will need a flow graph which consists of directed edges which are also called arcs each directed Edge has a certain capacity which can receive a certain amount of flow at all times the flow running through an edge must be less than or equal to the capacity this intuitively makes sense because if we allow more flow than what the capacity permits it means something has to go wrong when an edge becomes over capacitated in some manner it means that we've pushed the system past its limit in the context of edges representing pipes with water it means your pipe broke or it leaked if your edge is a wire with electric current it means your wire literally fried or melted exploded or something bad happened to it because there was too much electric current this is not good so this is why we don't allow more flow than capacity each edge in the flow graph has a certain flow and capacity specified by the two values separated by a slash adjacent to each edge originally the flow through each Edge is zero and the capacity is a non negative value to find the maximum flow and also the min cut as a by-product the ford-fulkerson method repeatedly finds augmenting paths through the residual graph and arguments the flow until no more augmenting paths can be found so you're probably asking yourself at this moment what is an augmenting path what the heck is a residual graph and what do you mean by augment the flow alright let me explain we'll do them one by one an augmenting path is a path of edges in the residual graph with capacity greater than zero from the source s to the sink T in orange here I have highlighted a possible argument aqui thing to remember about an augmenting path is that it can only flow through edges which aren't fully saturated yet in fact you know you've achieved the maximum flow when there are no more augmenting paths left to be found how to actually find an augmenting path is a detail left unspecified by the ford-fulkerson method for flexibility for now let's assume that we're using a depth-first search something else to know is that every achtung path will have what I call a bottleneck value which is the smallest edge along the path you can find the value of the bottleneck by taking the difference between the capacity and the current flow of an edge for this ah cumin ting path the bottleneck value is 6 we can use the bottleneck value to argument the flow along the path augmenting the flow simply means to update the flow values of the edges along the augmenting path here you can see that I've increased the flow of each edge along the augmenting path by exactly 6 units however we're not done augmenting the flow we not only need to increase the flow along the forward edges but also decrease the flow along the backwards edges which are called a residual edges the residual edges are the dotted edges going backwards in the reverse order of the augmenting path the logic behind having residual edges is to undo bad choices of augmenting paths which do not lead to a maximum flow effectively we don't know which are the best or even correct augmenting paths to take so this mechanism enables us to freely find any augmenting paths without having to worry about whether or not we'll be able to achieve the maximum flow it should be mentioned that residual edges become valid edges to take when finding an augmenting path in late iterations so if we take a step back you can think of every edge in the original graph as having a residual edge with a flowing capacity of zero which is not usually shown now that we know what residual edges are the term residual graph simply means the graph which also contains residual edges not just the original edges given in the flow graph so generally speaking when I mentioned the flow graph I usually mean the residual graph so here's a good question you might have at this point the residual edges shown have a capacity of zero aren't those forbidden how does that work so here's the thing with this method of augmenting the flow you have to think of the remaining capacity of an edge e residual or not as the difference between the capacity and the flow of that edge that is the difference between the capacity and the flow is the true remaining capacity for that edge this ensures that the remaining capacity of an edge is always non-negative even if the flow can be negative for example in the residual edges we have right now 0 minus minus 6 is 6 so we know that all our residual edges actually have a remaining capacity of 6 so the algorithm proceeds and the ford-fulkerson method continues to repeatedly find augmenting path after augmenting paths and to augment the flow until no more augmenting paths from s to T can be found the key realization to make at this point is that the sum of the bottleneck values that we acquire with each augmenting paths will result in the maximum flow and that's the whole premise of this algorithm it doesn't matter so much how you find augmenting paths but so long as you keep summing the bottleneck values which they produce you'll find the maximum flow so let's keep finding augmenting paths remember that we can only select edges whose remaining capacity is greater than 0 to be part of the arc path so the bottleneck for this augmenting path is 4 since 4 is the minimum of all the remaining capacities along this documented path here's another augmenting path from the source to the sink you'll notice that we're actually using one of the residual edges we created earlier in this path you'll also notice that there are two purple edges in this slide this is just a coincidence since both of those edges have the same bottleneck value of 6 then we argument the flow as we do I'll let the animation play for this next one and at the end we can see that if we sum all our bottleneck values 6 4 6 & 4 we're able to achieve the maximum flow which is 20 in terms of the time complexity the ford-fulkerson method derives its complexity from how we actually find those augmenting paths which as we know is left as an unspecified detail if you assume that finding augmenting paths are found by doing a depth-first search then the algorithm runs in a time complexity of a Big O of F being the maximum flow times e the number of edges in the graph here's a graph where we can derive the time complexity suppose that the side edges have very high capacity values of 100 and the middle Edge has a capacity of 1 you can clearly tell that the maximum flow should be 200 because you can run two augmenting paths with flow values of 100 on the top and the bottom of the graph from the source to the sink however recall that a depth-first search traversal is essentially random so it's possible for you to pick that middle edge with a capacity of 1 every single time and what that will do is it'll limit flow you can push from the source the sink to be 1 so 1 is always going to be your bottleneck value so you're never going to be able to augment the flow by more than one unit this results in flipping back and forth between the same two alternating paths for 200 iterations which really kills your time complexity luckily much faster algorithms and better heuristics exist to find the maximum flow value one example is edmonds-karp which is ford-fulkerson but instead using a depth-first search use a breadth-first search to find the shortest augmenting path from the source to the sink in every iteration there's also capacity scaling which is the idea of picking larger paths first to reduce the number of paths you need to find overall and this turns out to work really well at least from my empirical tests then there's dynix which uses a combination of a breadth-first search to first find a layered graph that guides edges towards the sink which you then use a depth-first search to actually find the augmenting path there's also this idea of push reliable algorithms which work differently than the algorithms we've discussed here which try and find augmenting paths instead push we label algorithms maintain this concept of a free flow if you will to find the maximum flow of a network please be mindful that the time complexity is posted here are very pessimistic in practice running maximum flow kennedys operates much faster so it's very hard to compare the performance of two flow algorithms solely based on the complexity awesome thank you for watching in the next video we'll be going over some source code and learning how to set up and actually code one of these max flow algorithms probably ford-fulkerson with a depth-first search so guys thank you again for watching please like this video if you learned something please subscribe and five [Music]