Hello, and welcome back. My name is William. Today we're going to have a look at some source code for the Edmonds Karp algorithm. In the previous video, I explained what Edmonds Karp is, how it works and why you want to use it. So I highly recommend you watch that video before proceeding. I'll leave a link to it in the description.

All the source code presented in this video can be found on github@github.com slash William fuzzer slash algorithms also link in the description. All right, here we are in the source code written in Java. I've laid out some instructions here in the header in case you wanted to download the code, play around with it and run it yourself. If I scroll down, you can see that we still have the same setup as before with the edge class right here, and the Network flow base solver, but there is one important change I have made since the fourth Fulkerson video. And that is I have added three new methods. If we scroll down, you can see that the three new methods are right here.

The three methods I added abstract away visiting nodes and marking all nodes says unvisited. Now, this is all done efficiently internally, through the network flow based solver class using a visited token you don't have to worry about it also helps readability for anybody who's new to the code. All right, now let's have a look at the Edmonds Karp solver which is the only thing different in this file. First, notice that the Edmonds Karp solver extends the network flow solver base. In doing so we get a whole bunch of things for free, including the ability to construct a flow graph before we push flow through it in the constructor for the Edmonds Karp. solver, all I do is call the superclass constructor.

This performs various initializations, including allocating memory for the flow graph and registering which nodes are the source and the sink. The most important method in the Edmonds Karp solver is the solve method right here. The sole method is called just before we get the maximum flow, this method is a really short, all we do is repeatedly find augmenting paths from the source to the sink until the flow we get is zero, at which point we know that the graph is fully saturated and no more augmenting paths can be found. line by line what we do is mark all nodes as unvisited before each iteration, run a breadth first search and get the bottleneck value and then some overall bottleneck values to calculate the maximum flow. Now let's take a closer look at the breadth first search method. First thing I do is initialize an empty queue data structure.

Because I know that we're going to need one to do a breadth first search after the creation of the queue. What I do is I visit the source node and add it to the queue so that the breadth first search starts at the source. Then do your standard breadth first search loop. While there are still nodes in the queue, remove the first node found in the queue. If it's the sink, stop, otherwise iterate through all valid adjacent neighbors. We can add a node to the queue if it is not already visited and the edge leading to the node has a capacity greater than zero.

However, before we add the node to the queue, be visited and track where it came from by placing an edge in the prep array to rebuild the augmenting path later on. Alright, so moving on, we know that the breadth first search did not actually make it to the sink if we have no entry At the index of the sink in the prep array, so we can return early after this point, we know that there exists an augmenting path. Since we know an augmenting path exists, we can find the bottleneck value that is the smallest remaining edge capacity along the path. We do that by starting at the sink and reconstructing the augmenting path going backwards by repeatedly reaching into the periphery until we are back at the source, then we need to update the flow along the augmenting path to adjust the flow values. So once again, loop through the edges forming the augmenting path, then the augment method takes care of increasing the flow along the four edges and decreasing the flow along the residual edges.

The very last thing to do is to return the bottleneck value so that we can sum the max flow and the solve method. And that's basically it for Edmonds Karp. actually build a flow graph. Have a look at the example right here in the main class. It sets up the flow graph from the previous video and pushes flow through it. You can see down here where we actually create the solver and run the solver to get the maximum flow and then finally display the resulting graph after the maximum call has been pushed through it.

So this is really handy to understand. So please have a look at this in more detail if you're struggling to understand it, and scarp Awesome. Thank you for watching. Please like this video if you learned something and subscribe for more mathematics and computer science videos. Thank you