Hello and welcome, my name is William. Today we're going to have a look at some source code for the capacity scaling algorithm. In the previous video I explained what capacity scaling is, how it works and what it is good for. So I highly recommend you watch that video before proceeding there will be a link in the description. All the source code you see in this video can be found on github@github.com slash Williams slash algorithms. Okay, here we are on the source code written in Java.

I've laid out some instructions here in the header in case you actually want to get the code play around with it and run it yourself. Scrolling down you can see we have the familiar edge class here. This is the class used to represent an edge that connects two nodes with a certain capacity If I scroll a little further down, we have the network flow solver base, which acts as a template for all the different flow algorithms we have been implementing. I have already covered how these two classes work in the previous videos linked below, so please have a look at those before continuing. However, the class we're really interested in is the capacity scaling solver. Right here.

The capacity scaling solver is an implementation of the network flow solver base, which uses capacity scaling to find the maximum flow, you will notice that I have defined one new instance variable in this class, which is called Delta. This is the same Delta that we saw from the slides. It's the parameter we use to determine whether an edge should be accepted or rejected based on the remaining capacity relative to the value of delta. The constructor for this class simply calls the superclass constructor to initialize the flow graph and allocate some memory that will Need to actually push flow through the network. Just below is the Add edge method. The added edge method is particularly interesting.

For capacity scaling to work, we need to know the value of the edge with the largest capacity in our flow graph. Since we also need to construct the flow graph to actually do anything interesting, we can capture the largest capacity value as we build the graph. The implementation of the Add edge method is defined in the network flow solver base, which we don't actually want to change the functionality of. So inside this add edge method, which I'm overriding here, all I do as I call the super classes and edge method, and I also initialize delta to be the largest capacity we encounter as edges come through simple enough. Inside the solve method, which gets called to compute the maximum flow, the first thing we do is initialize delta to be the largest value of two less than or equal to the largest capacity One way to do this is to find the floor of the base two logarithm and then raise that value to a power of two orange Java, you can simply use the built in function highest one bit to do that for you more efficiently.

Following that, we repeatedly find augmenting paths from the source to the sink using only edges with a remaining capacity greater than or equal to delta. After each iteration we have the value of delta to allow taking smaller edges and being able to find more augmenting paths from the source to the sink until the graph is fully saturated. Inside the inner loop, we mark all the nodes as unvisited then we do a depth per search and sum over the bottleneck values to calculate the maximum flow we repeatedly do this until delta is equal to zero. Now let's have a look at the depth per search method. The depth first search method takes two arguments the current node and the minimum flow found along the path so far when we Initially call this method the source node is the current node and the flow is set to positive infinity.

This method performs the depth first search recursively. And we know we can stop searching when we have reached the sync node t. If the current node is not the sync node, then visit the current node and iterate through all the neighbors of the current node. However, here's the catch though we cannot take an edge going to a neighboring node if the remaining capacity of that edge is smaller than delta because this violates the capacity scaling heuristic, we must also ensure that the node we're going to has not already been visited we do this to avoid cycles in the flow graph. Inside the inner if statement we call the depth research method recursively passing the node or going to as the current node and the new flow as the minimum of the current flow and this edges remaining capacity. The depth for search returns the bottleneck value along the augmenting path.

So after depth first search call, we are unwinding the call stack from the sink back to the source. This is a perfect time to augment the flow of each edge along the augmenting path since we have the bottleneck value right there. So if the bombing value is greater than zero, this means we have found a valid augmenting path and we want to augment the flow, which is remember adding flow along forward edges and subtracting flow along residual edges. This is all done through the argument method in the edge class and finally, return the bottleneck value. If we scroll down even more, you can see that this is the main method right here. In here I set up an example of how to set up a flow graph.

Specifically, this is the flow graph from the slides. So I create a flow solver. I add all the edges and then I push some flow through it and get the maximum flow. I also display the resulting flow graph after the flow algorithm has been executed. So you can see what happened That's all I wanted to cover for capacity scaling. Please Like this video if you learned something and subscribe for more mathematics science videos.

Thank you