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
edges.
A simple way to arrange for this is to
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.
And then, when we add an edge even though
it's kind of a directed network to handle
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.
So we have our standard edge to in marked
arrays and so we already have a queue
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.