Hello, and welcome back. My name is William and today we're going to have a look at some source code or dynex algorithm. In the previous video I explained what dynex is, how it works and why it is a great choice as the maximum flow out of them. So I highly recommend watching that video before proceeding I will place a link in the description below all the source code for this video can be found on github@github.com slash Wm is a slash algorithms. Okay, let's get started. Here we are in the source code written in Java.

I laid out some instructions here in the header in case you wanted to get the code play around with it and run it yourself. Scrolling down as before you can see the familiar edge class this class is used to represent an edge that connects two nodes with a certain capacity. It also has two important methods remaining capacity which returns the true remaining capacity of an edge along with the argument method, which updates the flow along this edge and also the residual edge by a certain amount. A little further down is also the network flow solver base, which acts as a template for all the different flow algorithms we have been implemented. I already covered how this class and the edge class work in previous videos linked below. So I won't spend too much time here but what you need to know is that this class initializes the flow graph, it allows it just be added to the flow graph.

I like to call the get max flow method which is somewhere down here, right here. Internally they get Maxwell method calls the abstract solid method which we need to implement by subclassing, the network flow software base So the part that we are really interested in is this dynex solver right here, you will notice that the didn't solver class extends the network flow solver base network flows to our base gets initialized when we call super by feeding it the three inputs n, s and t, n is the number of nodes in our graph, S is the index of the source node and T is the index of the sync node. Just after that I initialize an array instance variable called level to be a size and the level instance variable keeps track of the level of each note. Now our level graph moving on the following method is the salt method.

Recall that this is the method that we need to override and compute the maximum flow and remember what we're trying to do didn't algorithm begins by building a level graph using a breadth first search is the outer loop. And for each level graph, we need to find the blocking flow by repeating doing multiple depth first searches from the source to the sink until the level graph is saturated and the blocking flow is reached. Once that happens, rebuild the level graph and repeat the process until the graph is truly saturated. Let's have a look at the breadth first search method. So the breadth first search method really serves two purposes. One is to build the level graph and assign a level to each node in the level array.

And the other purpose is captured by the return value of the function. And that is to determine if we are able to reach the sink during the breath research phase. And if not, this means that the graph is fully saturated and the algorithm can stop. The first thing I do in this method is mark each note as unvisited by setting each entry in the level array to be minus one. Then I initialize a queue data structure that we will need when performing the breadth first search. After that I immediately add the source node to the queue.

That's because We're starting the breadth first search at the source node. Since we're already at the source node, we can mark the distance to the source node to be zero. Once we start the breadth first search loop while the queue is not empty, each iteration we remove the first node index we find in the queue and iterate through all the adjacent edges of that note, when building level graph who wants to ensure two things first that the remaining capacity of the edges we take are greater than zero and that we are selecting unvisited nodes. If both those cases hold then we can compute the level for that node we're about to visit and add it to the queue. This process continues until the queue is empty and the entire level graph is built. The last thing we do is return if we were able to reach the sync node during the breadth first search phase.

Okay, coming back to the salt method. Now we understand how the breadth first search method works and how the level graph is constructed. Now let's have a look at the depth of research method. However, before we Do that there's a key piece of information you need to know about and that is the next array in this method. The next array is part of the shaman evon optimization, and it is how we are able to prune dead ends efficiently. The idea is that since our graph is stored as an adjacency list, the list of edges going outwards from each node is indexed.

And we can use this to our advantage to get the next edge to traverse and skip all the edges which we know lead to dead ends. Say we're at node i and we take the first edge in our adjacency list for node i suppose that this turns out to lead us to a dead end well next time as in the next step per search, in which we encounter the same node we should not take the first edge in the adjacency list for that node because we know it will lead us to a dead end. The next array is a way of tracking for each node which edge we should take next iteration you want to reset the next array to allow taking pre forbidden edges. All right, so we call the depth research method and we pass in three arguments, the current node being the source, the next array and the minimum flow along the path, which starts at positive infinity, then for each augmenting path that we find sum over the bottleneck values to compute the maximum flow.

All right, let's have a look at the depth first search method itself. The depth first search method takes three arguments, the current node, the next array, and the minimum flow along the path so far, this method performs a breadth first search recursively. And we know we can stop searching when we have reached the sink node t. Then I captured the number of edges going out of this node, the for loop loops through all the edges while we have not tried taking each edge or the current node. The next edge to take is the next outgoing edge from this node at the index in the next array. The thing we have to watch out for is that we must integrate That the selected edge has a remaining capacity greater than zero and that it goes up a level. Remember that we're always trying to make progress towards the sink and taking an edge at the next level guarantees that unless of course, it leads to a dead end, but we end up pruning those so it doesn't really matter.

So if all goes well, we get to enter the inner if statement. Inside the inner if statement we call the depth first search method recursively passing in the node, we're going to as the current node and the next array and the flow as the minimum of the current flow and the edges remaining capacity. The depth for search returns the bottleneck value along the augmenting path. After the this depth research call. We are unwinding the call stack if you will, and we're going from the sink back to the wards the source. This is the perfect time to augment the flow for each edge along the augmenting path, since we already know what the bottleneck value is.

So if the bottleneck value is greater than zero, meaning we actually found an augmenting path augment the flow, which means to add flow along the forward edge and subtract flow along the residual edge. And once all that is done, simply return the bottleneck value. So, assuming we were not able to take the selected edge from the current node, because it did not have enough remaining capacity or didn't increase in level or we hit a dead end or whatever reason, we need to mark the selected edge as invalid so we can prune it in future iterations. This is exactly what the next at plus plus line does, which gets executed after the iteration of the loop. It increments the index of the edge take at the current node. If we scroll down to the main method, you see that I show you how to set up a flow graph by initializing the flow solver and pushing some flow through the graph.

In particular, this is the flow graph from the slides. Last video, so you can verify that the maximum flow we get should be 30 Wonderful. Thank you for watching. Please like this video if you learn something and subscribe for more mathematics.