0:03

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

1:38

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.

7:47

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.