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.