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 zero 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 sync node. usually denoted as s and t respectively. The maximum flow problem asks with an infinite input source, how much low can we push through the network without exceeding the capacity of any edge and it's not at 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 in traffic or the net electric current that your system can sustain. Effectively, the maximum flow is a bottleneck value for the amount of time 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 seven. And you can tell because after running 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. I don't 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 minimum as a byproduct, the Ford Fulkerson method repeatedly finds augmenting paths through the residual graph and augments 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? All right, 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 as to the sink t in orange here I have highlighted a possible augmenting path. The key 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 specified 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 augmenting 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 augmenting path, the bottleneck value is six, 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 six 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 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 later iterations. So if we take a step back can think of every edge in the original graph as having a residual edge with a flow and 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 IE 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. Zero minus minus six is six. So we know that all our results edges actually have a remaining capacity of six. 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 SDT can be found. The key realization to me at this point is that the some 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 zero to be part of the augmenting path. So the bottleneck for this augmenting path is four since four is the minimum of all the rooms Meaning capacities along this augmenting 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 the slide. This is just a coincidence, since both of those edges have the same bottleneck value of six, 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, 646 and four, we're able to achieve the maximum flow which is 20. In terms of the time complexity, the portfolio Kherson method derives its complexity from how we actually find those augmenting paths, which as we know is left as an uncensored If I detail if you assume that finding augmenting paths are found by doing a depth per search, then the algorithm runs in time complexity of big O of F being the maximum flow times IE 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 one, you can clearly tell that the maximum flow should be 200. Because you can run two augmenting paths with low values of 100 on the top and the bottom of the graph from the source to the sink. However, recall that a depth or search traversal is essentially random. So it's possible for you to pick that middle edge with a capacity of one every single time. And what that will do is it'll limit low you can put From the source the sync to be one, so one 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 exists to find the maximum flow value. One example is Edmonds Karp, which is Ford Fulkerson. But instead of 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 dynex, which uses a combination of breadth first search to first find a layered graph that guides edges towards the sink which you then use a depth or search to actually find the augmenting paths.

There's also this idea of push relabel algorithms which were differently than the algorithms we've discussed here which try and find automatic paths. Instead push reliable algorithms maintain this concept of a pre 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 hundred these 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 portfolio person with a depth first search So guys, thank you again for watching please like this video. If you learned something, please subscribe and I'll catch you next time.