- [Instructor] Hello there.
Okay, now we're gonna do network flows.
An important application of graph algorithms
is what's called network flow,
and the first example that we usually see
when talking about network flows
is in finding the maximum flow through a network.
Well, what's a network?
Well, there are all kinds of networks.
There are transportation networks
like the London Underground,
or global fiber optic networks,
or national electric grids, natural gas pipelines,
or chemical reaction networks.
And in each case, it's a natural question to ask,
and often a very useful question to ask,
what's the maximum flow through the network?
What's the maximum flow that the network can support,
whether that's of trains, of data packets, of amps,
of cubic meters of natural gas, of reactions, whatever?
So it's reasonable to ask,
what's the maximum flow of trains
between Bond Street and Whitechapel?
How many megabits per second can flow
between Jacksonville here and Mumbai over here?
How much electricity can flow from Louisiana to Chicago?
How many cubic meters of gas can flow per day
between natural gas fields in Siberia
and consumers in Amsterdam?
And given some precursor chemical,
at what rate can we produce some reaction product?
And so on.
So let's start with a really simple network.
This is a really simple network.
So here we have a directed graph,
and let's call s the source,
and we'll call t the sink.
And a flow through the network originates at the source
and ends up at the sink.
Again, this flow could be trains or data packets
or electricity or natural gas or water,
anything that can flow through a network,
although it is common for us to think of network flows
by using an analogy with the flow of fluid, okay?
And each edge in the network has weight,
and that's called its capacity.
So here we have a capacity of two units
from the source s to this node x,
and a capacity of one unit from this node x to the sink t.
So what exactly is a flow, then?
Let's make this a little more precise.
We write f sub u, v to be the flow from u to v.
So if we have two nodes, one labeled u, one labeled v,
F sub u, v is the flow between those two, okay?
And we have some constraints on flows.
So the flow here between u and v can't be greater
than the capacity from u to v.
We see that the flow is always less than
or equal to that of the capacity.
This is the flow.
That's the capacity.
The flow across an edge cannot exceed
the capacity of the edge,
We have another constraint,
and that is that, excluding the source and the sink,
that the flow into every node
equals the flow out of that node.
And so here we have some notation that is giving us
the sum of all the flows into node v
through all of these edges u, v
for all u, v in the edge set, E is the edge set.
And we have all of the flows out of v through edges v, w
where all the v, w's are in the edge set.
So the flow out of a node
has to equal the flow into the node.
That's the flow into the node, that's the flow out,
and for all of them except for the source and the sink,
they have to be equal.
Given those constraints, what constitutes a valid flow?
Given our example, we have this capacity, two,
the capacity from s to x,
and we have this capacity, one,
which is the capacity from x to t, what's a valid flow?
We want to come up with numbers
that satisfy these constraints.
And one and one is a simple example here.
So we have the flow from s to x equals one,
and the flow from x to t equals one.
Let's just check to make sure
that the constraints are satisfied.
The flow on edge u, v, where u is s and v is x, is one.
The capacity on that same edge is two.
One is less than two, so we're okay there.
For this one, the capacity is one and the flow is one,
so they're equal,
but that's still satisfies this constraint here.
And notice that we have one unit of flow going into x
and one unit of flow going out of x,
so this constraint is satisfied.
Of course, we only have one edge.
If we had multiple edges,
we'd have to sum the flows into x
and we'd have to take all the flows out of x.
This is a simple example, but the constraints are met,
and so this flow of one to one
where we have one unit flowing through our network
is a valid flow.
This is a trivial example.
Flow could be zero.
And this certainly meets all the constraints,
but it's not very interesting.
Now, if we allowed real-valued flows,
like we might have for electricity or water or gas,
this would also be a valid flow,
because 0.5 is less than two,
0.5 is less than or equal to one,
and we have 0.5 going into x, 0.5 going out of x,
0.5 leaving the source, 0.5 arriving at the sink,
and that would also be a valid flow.
Now, of course, this wouldn't work for trains.
You can't have half a train.
And all the remaining examples that we'll give
in this video will be limited to integral solutions.
So we're only gonna deal
with weights and flows that have integer values.
But they could be real-valued as well.
So let's expand a little bit,
take a look at a slightly bigger example.
Here's one where the flow equals the capacity.
So the flow here and the capacity are the same.
And let's make sure that this satisfies the constraints.
Notice that we have three units going into x.
We have two here and one here into x
and three units going out of x.
So we're good here.
And we have two units flowing into y
and two units flowing out of y,
and so this constraint is satisfied.
Since the capacity equals the flow,
we know we're not exceeding the capacity,
so we're good there.
And notice also that we have four units flowing out of s
and four units flowing into t.
So that's the flow out of the source
equals the flow into the sink.
And so this is a valid flow, all right?
Now let's look at an example
where we have some capacity constraints.
So here the edges out of s
have a combined capacity of six, three and three,
but the edges into t, two and two,
have a combined capacity of four.
So clearly this network can not support a flow of six, okay?
It can't support a flow greater than four.
So we know whatever flow that this network might support,
it has to be four or less.
Here on the right, we have a solution,
a valid flow for the network that we see here on the left.
And again, all of our constraints are met.
The flow out of the source equals four.
The flow into the sink equals four.
The flow into x equals two.
We have one from here and one from here.
And two out, so the flow out of x equals the flow into x.
We have three units going into y
and three units coming out of y.
So all of our constraints are met,
and so this is a valid flow.
This too is a valid flow.
All the same constraints are met and the flow is the same.
It's still four, but we take slightly different routes
and we don't use this edge in the middle.
That's fine that we have zero flow along a given edge.
So we have flow of four here,
we have a flow of four here,
we have two into x, two out of x,
two into y, two out of y, and we're good.
So that is a valid flow.
And this is in fact the maximum flow
for this particular network is four.
Now let's take a look at a bigger example.
Let's say we have this directed graph, okay,
and we have these edge weights indicating the capacities,
and we want to know what is the maximum flow
through this network from node s over here to node t.
Now, having seen the previous example,
it's likely that it occurs to you
that clearly the network can not exceed flow
equal to the sum of the edges out of s
or the sum of the edges into t.
And if you thought that, you'd be right,
that's a good intuition to have.
So the maximum flow out of node s is 23 plus 18 is 41,
and the maximum flow into t is 14 plus 25, that's 39.
So we know that the maximum flow
through the network can not exceed 39.
It might be lower, but we know it can't exceed 39.
And notice I've drawn these as dotted lines here.
These are called cuts, and a cut
is a removal of edges from a graph
that separates components of the graph.
And here, the components that we're interested in
are the source and the sink.
So if I were to make this cut and remove these two edges,
s would be separated from t.
There would no longer be a path from s to t.
Or considering the cut on the right over here,
if we were to remove these two edges,
we would disconnect t from the rest of the network.
And again, there would be no path from s to t.
That's what it means to make a cut.
We say the cut on the left has a weight of 41
and the cut on the right has a weight of 39.
Now, there are many, many, many other cuts in this network,
as you might suspect.
So we have a cut like this.
There's this one that goes this way
and cuts through all of these edges that it crosses.
They have weights 18, four, six, 19, seven, four, and 16.
So the sum of those weights is 74.
We've got this cut, let's see,
this cuts through nine, 10, seven, five, and 15, that's 46.
We've got this one, this one here.
I'm not gonna go through all of them, but you get the idea.
This is nine, 17, six, five, and two, that's 39.
And here we have a cut through 14,
three, nine, 19, and two, that's 38.
So it looks like the smallest, this one is 39,
so it looks like the smallest cut
that we've seen so far is 39, or 38, sorry.
So we found a smaller cut.
And now we know that the maximum flow
through this network can not exceed 38.
Because this cut separates s and t,
we know that any flow through this network from s to t
has to pass through at least some of the edges of this cut.
And so if we have a weight here of 38,
we know that there can be no greater flow
through this network than 38.
It's got to pass somewhere through this cut.
It turns out that the maximum flow through the network
and the minimum cut through the network
are two sides of the same coin.
So finding the minimum cut
amounts to finding the maximum flow, and vice versa.
So finding the minimum cut
amounts to finding the maximum flow, and vice versa.
Now, we want an algorithm that will find
the maximum flow or the minimum cut through a network.
Now, Ford-Fulkerson algorithm originated in 1956
in a joint paper by, surprise, Ford and Fulkerson.
And yes, that's the same Ford
as in the Bellman-Ford algorithm.
Edmonds-Karp is an adaptation
of the Ford-Fulkerson algorithm that was published in 1972,
though essentially the same algorithm
was published independently
by poor Yefim Dinitz in Israel in 1970.
So unfortunately his name is not attached to the algorithm,
and we know it by the name Edmonds-Karp.
Karger-Stein is a later algorithm
first published by Karger in 1993
and then improved by Karger and Stein in 1996.
It's a completely different algorithm
than what we'll demonstrate here.
So we're just gonna focus on these two.
And Ford-Fulkerson and Edmonds-Karp
work to find the maximum flow,
and by doing so, they find the minimum cut.
Karger-Stein is designed to find the minimum cut first.
So they function very differently.
But in case you're curious, Karger-Stein is kind of cool.
So how do we do this?
Well, let's start with a graph that has,
you know, it's a directed graph.
It's got a source and a sink
and it's got some directed edges,
and it's got weights on those edges
which are the capacities, and so I've written capacity here.
And we want to find the maximum flow through this network.
As we saw before, clearly the flow can't exceed seven,
because we know we have seven flowing out of s,
we've got nine flowing into t.
I shouldn't say that, I'm gonna take a step back.
We have a capacity of seven out of s
and we have a capacity of nine into t.
So we know, because the flow cannot exceed the capacity,
that the flow cannot exceed seven through this network.
So we know that's a limitation right there.
But is that the maximum flow?
So to solve this algorithmically,
and for purposes of demonstration,
I'm just gonna draw two auxiliary graphs.
And there are more concise ways of doing this,
but this will make it easy to demonstrate.
So we have one auxiliary graph that's the flows,
and we initialize that auxiliary graph
so that all the edges are initialized to zero.
So right now we have zero flow through the graph.
And we have what's called a residual graph,
and we're gonna initialize that to all the same capacities
that we have in the in the original graph.
So we have the flow graph and the residual graph.
And again, this is a perfectly reasonable flow.
It's zero, but that's not very interesting.
We want to find the maximum flow through this network.
So the residual graph is used
to keep track of unused capacity.
And since the flows here are zero,
all of our capacities are gonna
equal the original capacities here
because we haven't used any of them yet, all right?
And the idea is to find paths in the residual graph
and find the maximum flow through each path that we find,
and add the flows to the flow graph
and subtract the flows from the residual graph.
And we keep doing this until we can find no more paths
that can carry flow from the source to the sink.
And we call these paths augmenting paths
because once discovered, we will use them
to augment the flow in the flow graph.
So let's take it step by step.
So just recall, the first thing we're gonna do
is look for a path from s to t in this graph.
And so we found one.
Here's one such augmenting path.
Now, how much flow can this path carry?
This capacity is three, this capacity is three, this is six,
so the maximum this path can carry is three.
So we add three units to the flow graph,
adding three to each one
of the corresponding edges in the flow graph,
and we deduct three units each
from the edges in the residual graph.
So now this one was three, it's now zero;
was three, now zero; was six, now it's three.
And we have three, three, and three over here.
So we have this flow of three units now in our flow graph.
Are we done yet?
Well, can we find another augmenting path
through the residual graph?
So let's look, and, yep, we can find another.
Here's another augmenting path from s to t
that goes through b and c.
And what's the maximum flow this path can carry?
Well, the capacity here is four,
the capacity here is one,
and this is the leftover capacity
after consuming three over here.
So we have three remaining units of capacity here.
But the bottleneck is in this edge from b to c.
This edge can only carry one unit of flow.
And so what we're gonna do
is we're gonna add one unit of flow
to the corresponding edges in the flow graph
and we're going to deduct those units
from the residual graph,
from the edges in the residual graph, right?
So this was four, now it's three;
this was one, now it's zero;
this was three, now it's two.
And we have one, one, and four.
This had been three before, we added one.
And so now we have a flow of four through our network.
Are we done?
Nope, we're not done.
So we've gotta go back and we've gotta see
if we can find another augmenting path.
And yep, there's another one.
So what's the maximum flow for this path?
It's two, 'cause we have capacity three, two, and three.
So the most we can flow through this path is two.
So we add two to the corresponding edges in our flow graph
and we deduct two from the edges in our residual graph.
And so now what do we have?
Now we hunt for another augmenting path.
Is there another augmenting path?
No, there's not.
There's no way we can get through the residual graph, now,
from s to t along any path
that has a capacity greater than zero.
This is zero, this is zero, this is zero, this is zero.
So all of our routes are blocked.
We can't find any more augmenting paths.
And since we can find no more augmenting paths, we're done.
And on the left, we have, again,
our original graph showing the capacities of each edge.
In the middle, we have a graph indicating
a maximum flow through the network.
This is a solution,
not necessarily the only solution, it's a solution.
And when our algorithm has terminated,
the residual graph shows the remaining unused capacities,
and it also gives us a hint as to the minimum cut here.
You have these three zeros.
Let's just double-check.
Are all of our constraints met?
And we just do an edgewise comparison and make sure.
Three is less than or equal to three,
three is less than or equal to four,
zero is less than or equal to two,
you can do the rest of them, but trust me,
all of these values in the flow graph
are less than or equal to the values
of the corresponding edges in the capacity graph.
So this one is satisfied, this constraint is satisfied.
Is the flow excluding the source and the sink?
Is the flow into each node
equal to the flow out of each node?
And here we have three going into a
and three going out of a, so we're good at a.
We have three going into b
and one plus two is three going out of b,
so we're good there.
We have four going into c and four going out of c,
so we're good there.
And we have two going into d and two coming out of d,
so we're good there.
And, final check, is the flow out of the source
equal to the flow into the sink?
And here we have three plus three is six,
four plus two is six.
So all of our constraints are met and this is a valid flow.
So we found a solution and we verified.
So all of our constraints are met.
The flow along each edge is less than
or equal to that of the edge's capacity.
Apart from the source and the sink,
all the flows into a node equal the flows out.
And we're good, it's a valid flow.
And we can also see that the maximum flow, which is six,
equals the weight of the minimum cut, six.
And here's the minimum cut through this graph.
See, it cuts through an edge three, one, and two.
Those sum to six.
It should come as no surprise that that cut
goes through values of zero here in the residual graph.
And so here's our minimum cut.
Here's our maximum flow.
And like I said before,
they are two sides of the same coin.
So is this a greedy algorithm?
Yep, sure is.
This is a greedy algorithm.
This algorithm adds flows
to the solution as they're discovered
and never removes a flow once it's been added.
Okay, when we went through all those steps,
we never deducted anything from our flows.
What's the complexity?
Well, assuming we have only integer weights and flows,
like I said, the complexity is big O
of the cardinality of the edge set times the flow.
Well, why times the flow?
Well, in the worst case, we'll augment the flow by one
for each augmenting path that we find.
But we can only do this f times
if the maximum flow is a f units.
So in the worst case, every edge could be part
of each augmenting path we find,
and so we get a worst case of big O
of the cardinality of the edge set times the flow.
Now, how do we find the augmenting paths?
We looked at a small example and we found three,
and then we found there were no more.
But the answer here is it depends.
And Ford-Fulkerson does not precisely specify this.
As a matter of fact,
some people call it the Ford-Fulkerson method
because they don't believe
that it quite achieves the title of algorithm.
I think that's a little nitpicky.
But the Edmonds-Karp algorithm does specify
how we find the augmenting paths.
So at least in the case of Ford-Fulkerson,
what we've seen here is a certain arbitrariness
regarding the order in which we find the augmenting paths.
And depending on the graph,
a different order of discovery
may yield different solutions.
The solutions will all be the same,
they'll still yield the same maximum flow,
but the flow may occur differently
through all the different edges in the network.
So again, this algorithm doesn't find
all the possible maximum flows,
it finds a maximum flow.
And so that's all for this video
and we will continue in a subsequent video.
Thanks, bye.