Next, we're going to look at Java code for solving the max flow problem. This is the most complex. Graph processing algorithm we have seen so far but it's relatively a small amount of curve that builds upon the mechanisms that we have been studying for the last couple of lectures. So now, the graph that we are working with little more complicated because we have to associate with each edge not just the capacity but also a flow. So, we'll build a slightly more complicated data type for edges called a flow edge. Where, for each edge, we can keep track of that information. So, we not only have to keep the from vertex V and the to vertex W. The weight or the capacity C, associated with the edge but, and also the flow cuz that's a flow edge. And then the flow network. Since we're going to go through edges in the wrong direction we're going to have to put every flow edge, kind of like an undirected graph in both adjacency lists. And then we're going to test whether we're going, which direction we're going through an edge. It's kind of like using an undirected graph. But the flow network, anyway, has to have edges in both places so it can do backward compute for the edges what's called the residual capacity, and that's just what we're going to use to compute the bottleneck value, the only max amount of flow we can pull through. So for the backward edge, we'll assign the residualCapacityTo be the amount of flow. And for the forward edge, it'll be the capacity minus the flow. So, that's the maximum amount of stuff we can get through the edge when we're augmenting its residual capacity. so and to actually do the augmentation, you will have a value which is your maximum that you're going to, that you're going to augment and so if you are on the forward edge, you add it and if you're on a backward edge, you subtract it. And so, that's the basic idea and its just quite natural from the graph representation we've been using and the way that the codes focus on how algorithm woks. So one way to think of this is to little bit closer to the representation that we're using, is to consider what's called a residual network that for every edge every forward edge in the network, it has the, the in, forward edge going that has the amount of flow left and a backward edge with the amount of flow that's there. And if you have a, a full forward edge, or a, or an empty backward edge then you only have one such. So this an example of the residual network for this amount of flow. You can't put any more flow through from this vertex to this vertex, so there's no edge going that way. But you can remove four units of flow going that way. So, that's because of the backward edge. So and in this case we have a full forward edge. So, there's no edge going this way, cuz we can't put any more flow through. But there's nine going that way, That's another example of a full forward edge. This empty one you can put eight units of flow that way, so we have an edge in the residual network going that way. But no way to go that way, because there's no flow, there's no backward edge. And so this network is just a natural way to look at the network while the flow is being computed cause it's a digraph that we're going to search to find the augmenting path. If a directed path in this network that's from s to t, that's an augmenting path. And that's a simple mechanism that helps us write compact and elegant code. So that's an augmenting path in the original network and that just turns out to be a directed path in the residual network. So then, we can just use our algorithms that we've already studied for finding directed paths in the residual network. Alright, so here's the API for flow edges. And they just have the few extra methods to allow us to compute and make decisions based on the amount of flow and capacity in the edge. These are the computations that we need to implement the forward focus in algorithm. So every edge has a from and a to. If you have one point, it gives you the other one which we need just as we did in undirected graphs. Every edge has capacity and a flow and a residual capacity, which we compute from a capacity in flow, then we want to be an addResidualFlow to any edge, and its added and if its forward, and it gets subtracted if it's forward. So those are the basic methods in the API for a flow edge and, and the implementation of all of them is straightforward. So notice that one thing that's a little different from many othe, you know, classes is that actually the goal of our computation is to fill in these values flow. So, they're not final variables that's what we're computing. Now. we do it through addResidualFlow but still it's not a final. So, create an edge, just with a V to W given capacity, just fill in the instance variables and all these other ones are just getters. Others just like in an undirected graph. And then, residualCapacity and addResidualFlow are also easy to implement. So, residualCapacity if it's on the from edge, you return the flow, if it's on the to edge or it's the backward edge, you return capacity minus flow, just as we said. And addResidualFlow makes the same test to decide whether to add or subtract the flow. So very simple implementations of all those operations for our flow edges in a flow network. So, what about the floor network, API? it's again going to be our standard API, just that floor graph, flow networks are built from flow edges. And they're going to be built for the client which is going to be the max flow algorithm. it's going to have a method that gives an interval for every vertex of all the forward and backward edges instant on that vertex and sh, so that client is going to use these basic things. And given everything we've seen this implementation is pretty straightforward. It's pretty much just like edge-weighted graph, except we use low edges now. flow and forward and backward edges, We add every edge to both adjacency lists. But simple code, quite similar to what we've seen before. So we'll, again network is usually huge and sparse. So, we use a vertex index array and each entry associated with each vertex will contain references to all the edges that are incident on that vertex whether they're forward or backwards. So, just like an un-directed graph, you might have to, you'll have two references to the same edge. One and it's a from and the other and it's to and then rather than just to wait, they have a flow and a capacity. So from zero to two, it's got capacity three and one unit of flow in it. So, that's an example of, of how to represent that edge. So, flow network has got flows in it, that's the grey and it's got capacities, and that's the white. And otherwise, it's kind of similar to our undirected graph representation. I've got one more processing, the,, processing the graph. We use residualCapacity to make that kind of work in the residual path in natural way. So, this is the implementation of the forward focus in algorithm. And again h, pretty straightforward to given the description that we've done, and the graph processing code that we've written up to this time. So it's got you have an array of vertices that we've been to. It's got an edge two array which is the how do we get to each vertex so we can provide the client with the flow so that we can process paths in the graph you know, it's got the value of the flow. So, let's look at the code, it's kind of self-documenting. So what we'll do is we'll set the value of the flow to zero. So we're going to find out if it has a augmenting path and we'll look at that method in a minute. As long as it has an augmenting path then when we call, it has augmenting path, basically what that's going to do is that's going to do a graph search and mark the verticies that it visits and if it gets to this target, it's going to leave that path and now the edge to array in the standard way. the edge to of t contains the, the edge that, that contains the vertex that took us to t and so forth. And so we'll use that edge to, to go back through the path and to figure out the bottleneck capacity, Which is the minimum of the bottleneck capacity and the residual capacity in the high edge that we're processing. So that's the, the maximum amount of flow that we can push through the network does go through the path and find the minimum of either the unused capacity in some forward edge or the available flow in some backward edge. So once we have the bottleneck capacity, then we just go back through the path again and addResidualFlow to every edge in that path. So that's augment the flow. And then, once we've augment the flow, then we update the value. Notice that, when this terminates it terminated because we couldn't find an augmenting path, and we couldn't find an augmenting path meant that, essentially, we did a graph search that got stuck with finding all full-forward edges or empty backward edges before getting to the target and that's precisely the computation that we needed to do to compute the cut. So to tell whether a vertex is reachable from s. We just checkmarked v so we can tell the client which vertices are in the cut. And then we can find the, the edges that leave that vertex with the edges that comprise the cut. so now, all we have to do to finish is to look that it has augmenting path, which is the graph search in the residual network. And for this example we'll use breadth-first search although the other search algorithms that we've studied can be adapted in the same way depth-first search or using a priority queue as in Prim's algorithm or Dijkstra's algorithm. which is going to contain the vertices that we've encountered but not yet visited. We'll put the source on there while the queue is not empty, we'll take a vertex off. And so, we'll go through everybody associated that's connected to that vertex, that's a flow edge. And then, you check the residual capacity. And if, if it's bigger than zero that means h, you have a way to get to w, and if it's not marked, You haven't been there yet then you go ahead and go there and mark it. It's essentially a breadth-first search. So that's the code for has augmenting path. And that essentially completes the implementation of breadth-first search. And mark t tells the, tells the returns true or false. If you can get from t to s after that search is gone, then t will be marked, and you can return true. This method can return true. That's a Java implementation of the max flow.