Hello, everybody, welcome back. My name is William and today we're taking a look at the source code for the Ford Fulkerson method implemented with a depth first search. If you have not already done so please go watch my last video explaining the Ford Fulkerson method. There you'll find everything you need to know about augmenting paths, residual edges and flow argumentation. The goal of this video is to show you how to set up the following flow graph and find the maximum flow through it. So after we run the maximum flow algorithm we should get a graph similar to this one with flow running through some but not all of the edges and achieving the maximum flow of 23, the source code and the example I have lined up for you today can both be found on GitHub.

There's a link in the description for today. I encourage you to check that out and also play along as we're going over the source code. All right, here we are in the source code written in Java. This program has three main supporting classes and edge class, a network flow solver base and the Ford Fulkerson depth first search solver. However, before we get into any of those, I want to take a look at the main method where I actually use the classes above to solve the flow problem we just saw. I know a lot of people struggle setting up the flow graph, which is usually somewhat of a mystery.

So I want to clear that up. The first thing I recommend you do every time you set up a flow problem is initialize three variables and the number of nodes in your graph that is including the source and the sink nodes. And then what I recommend you do is you actually label the source and the sink nodes. and assign them indices. And what I usually end up doing is I say, the source node equals index n minus one, and the sink equals n minus two, the rest of the nodes in your graph should then have indices between zero and n minus three inclusive. I've always found this to be the easiest way to set up your flow graph.

Next, I create the flow solver by providing the three variables and s and t as inputs to the solver so it knows how many nodes there are and which nodes are labeled the source and a sink. Then I use the solver to actually create the flow graph by adding edges with different capacities. The next step is to hook up the edges to the source. Those would be the ones shown in this picture. Then I carefully hook up all the middle edges and lastly, the edges leading into the sink. It's usually always these three steps, and for most of the time your graph is bipartite.

So the mill edges are even simpler to set up. After this I call the get max flow method on the solver which actually runs the Ford Fulkerson max flow depth first search and returns an integer value for this graph, we're expecting a maximum of 23 followed by printing the max flow, I also display all the interesting edges of the residual graph. First, I get the residual graph from the solver after executing the max flow and iterate over all the edges and just display the flow on each edge. Let's actually run this program and see what the output looks like. So I just popped open a terminal and for those of you who also have a terminal open and want to play along first, you can just clone the GitHub repo by typing get clone followed by the repo URL which is github.com slash Willie Is slash algorithms, you see that I've already cloned the repo so I don't need to do it again, then just change directory into the algorithms folder.

So the file that we're working with is called the horrible the person example dot java file. And it's in the graph theory network flow examples package. And luckily for us, it doesn't have any dependencies yet. So we can just compile it on its own with jetpack. So if you type Java c followed by comm Williams algorithms graph the network flow examples, and then you find that file Ford Fulkerson example, Java, you compile it, it'll produce a dot class file in that directory. So you can execute it by typing Java and then the name of the class and then pressing Enter and then you get this beautiful output.

So this principle of interesting information, notably it prints the max flow of 23 and all of the edges plugged four columns. The first column represents the starting end nodes of the directed edge, then the amount of flow running through the edge, the capacity of the edge. And lastly a boolean value indicating whether the edge is a residual edge or not, which is quite handy for debugging. So let's go back to the code. So let's scroll back up the code and take a look at the first of the three classes which is the edge class. The Edge class is composed of a few instance variables in particular, every edge has a start node called from and an end node called to each edge in the flow graph has a certain amount of flow and capacity, the capacity of the edge is constant and does not change the flow is dynamic and adjusts as we argument the flow when you create a new edge, it should have a start and an end node plus an initial capacity.

The flow defaults to Zero, you might notice that the residual edge instance variable does not get initialized here or through the constructor. The reason is that I initialize the residual edge together with the forward edge and hook them up together in a helper method, which we'll see later. The next method is the is residual method, which determines whether an edge is a residual edge or not. Because forward edges are not permitted to have a capacity of zero, you know an edge is residual if the capacity is zero pretty easy. There's also the remaining capacity method which can be used to determine the maximum amount of flow that we can push through this edge. This method works whether the flow is positive or negative.

Next is the augment method which augments the flow for this edge alone. All it does is it increases the flow on the Ford Edge by the bottleneck value we found along the augmenting path. And it also decreases the flow along the residual edge. lastest the to string method which is responsible for displaying those nice columns we saw in the terminal. The next class we're going to take a look at is the network flow solver base. This class is a generic base for Maximo solvers, which all solvers should extend to gain access to reuse variables and setup methods and so on.

For example, a simple task like adding an edge to a flow graph should be the same whether the max flow algorithm is Edmonds Karp dynex, some capacity scaling algorithm, it shouldn't matter. Therefore, it makes sense to abstract that behavior and capture it in a base class. So there are many variables in this class. The first one is in short for infinity which is just a handy large constant that doesn't overflow if you add numbers to it, or at least it can handle having large numbers added to it, then there are the three input variables. And the number of nodes in the graph is the index of the source node and T the index of the sync followed by this are two special variables I usually end up using because they greatly help boost performance. So the rationale behind using the visited token in combination with an integer array that tracks the visited state of a node is that when we're finding augmenting paths, whether the depth first search or breadth first search or whatever graph traversal method you want to use, you generally want to ensure that your augmenting path doesn't visit the same node twice.

Otherwise that could result in a cycle which we don't want. The way to check if node AI is visited is to check if the state in the visited array at index eyes To the visited token, this is super handy because in the next iteration, when we yet again want to find another augmenting path, we can simply reset all the visited states of every node simultaneously by simply incrementing. The visited token, I know it's kind of hacky, but it's super efficient and really handy to have. The alternative is actually to maintain a Boolean visitor array, and you fill that with false values every time just before you find an automatic path. That's not great because it requires an additional order and work every time you want to find an augmenting path. Next is a boolean variable called solved, which indicates whether or not we have actually run the network flow solver.

The solver only needs to run once because that always yields the same result. So for example, if the user calls, get max flow method Multiple times the server only needs to run once. The next value that we have right here is the max flow variable, which is the value we're actually trying to calculate. And finally is the adjacency list representing the flow graph itself. Looking at the constructor, we require the user to specify the number of nodes along with the index of the source and the sink nodes. Then inside this method, I also take the opportunity to initialize the flow graph.

And as well allocate some memory for the visited array we'll be making use of later. In the initialize empty flow graph method. All I do is initialize an empty array list of edges for each node index so that we don't get a null pointer exception when we try and add an edge to the graph. Talking about adding edges to the graph. Let's have a look at the Add edge method here. need to provide the start node and the end node of the directed edge and also provide a positive capacity for that edge.

If the capacity is negative or zero, we throw an exception because that is an illegal argument, then what we do is we actually create the forward edge and the residual edge who noticed that the residual edge actually has a capacity of zero, then what we do is we make the forward edges residual edge, the residual edge and the residual edges residual edge, the forward edge and finally, we add them both to the flow graph. So in fact, each edge is each other's inverse. And this is exactly what we want. We want a pointer that we can simply access when we need to access and that is residual edge. The remaining methods here are simply client facing methods can be used to get the residual graph after the solver has been excellent And to obtain the maximum flow of the graph, you'll notice that there's also this one special method down here, which is the salt method.

And this is the method that the subclass needs to override. This is the method which actually solves the network flow problem and actually pushes the flow through the network. And you can see that every time the client goes and calls on these methods like get graph or get max flow, it calls the execute method, and the execute method will run the solver. So we will call this method if it hasn't been executed already, so it's got that smart logic built in. Now let's take a look at the Ford Fulkerson cursor solver, which you can see actually extends the network club a solver so we know it actually implements the solve method that we need for the get Maxwell method. Awesome.

Let's let's have a look at this. So the first thing you'll notice is that this means It also takes the inputs and SMT. And all we do here is we call the superclass constructor in the network flow based solver, which does all that nice initialization that we know about. Next is the most important method, which is that solve method I was talking to you about. And you can see that it actually overrides the method in the superclass. So in this method, you can see that I'm repeatedly calling the depth first search method returns as output the bottleneck value found along the augmenting path, store that value as F and increase the max flow by F in each iteration, because we know that the sum of the bottleneck values equals the max flow.

We do this until the bottleneck value is zero. At which point we know that no more augmenting paths exist and the algorithm can terminate in between finding each augmenting path you can see the increment the visited token This is used to make the state of s every node unvisited. The depth first search method itself takes two arguments, the node ID and the flow. Initially, the starting node is passed in as the node index, and the flow is set to be infinity. As we progress through the flow graph, the flow value eventually becomes the bottleneck value as we find smaller and smaller edges with more restricting capacities, and we stopped the algorithm once the node index equals the sink. So that's actually our base case right here.

Afterwards, since we know that the current node is not the sink, what we do is we explore it by marking the current node as visited. We do this by assigning the current index or the current node index to be equal to the visit token then comes the interesting part. First, we get all the outgoing edges of this node residual otherwise and then loop over them if the remaining capacity is greater than zero. Meaning we can push flow through that edge and the next know that we're going to is unvisited meaning we don't risk creating a cycle then we can enter this inner if block right here, inside the if block. The first thing I do is call the depth first search method recursively. What I do is I pass in the index of the next node we want to go to and the new flow value which should equal the minimum of the current flow or the current edges remaining capacity.

Remember that that flow parameter is trying to capture the bottleneck value that intuitively makes sense. It's saying either keep the previously found bottleneck value or if this new edge is even smaller than it should be the new bottleneck value. This process continues recursively until a base case is hit and the sink was reached. This returns the bottleneck of the augmenting path we can then use that value to augment the flow of our augmenting path. However, first check that the bottleneck value is greater than zero, it could be the case that we never actually made it to the sink, and we hit a dead end. assuming that's not the case, simply augment the flow by increasing the flow in the forward edge by the bottleneck value and decreasing the flow in the residual edge by the bottleneck value.

After that, simply return the bottleneck value. This propagates it up the stack so that all the other edges along the augmenting path can also be augmented. This also ensures that the bottleneck value is returned to the solve method where the max flow is actually calculated. So that's about everything I want to cover for the Ford Fulkerson method implemented with a depth for search. Thank you so much for watching. I sincerely hope that you learned something.

Please do like this video and subscribe for more Mathematics and Computer Science. videos. I'll catch you next time.