Having mastered computing the connected
components of undirected graph
in linear time, let's now turn our attention to
directed graphs which also arise, in all
kinds of different applications. Now the
good news is, is we'll be able to get just
a blazingly fast primitive for computing
connectivity information for directed
graphs. The bad news if you wanna call it
that, is we'll have to think a little bit
harder. So it won't be as obvious how to
do it, but by the end of this lecture you
will know a linear time algorithm with
very good constants, really just based on
depth-first search for computing
all of the pieces of a directed graph. In
fact it's not even so obvious how to
define pieces, how to define connected
components in a directed graph, Certainly
not as obvious as it was with undirected
graphs. So to see what I mean, let's
consider the following four node directed
graph. So on the one hand, this graph is
in some sense in one piece. If this was an
actual physical object made, say, of a
bunch of strings connected to each other
and we'd picked it up with our hands, it
wouldn't fall apart into two pieces. It
would hang together in one piece. On the
other hand, when you think about moving
around this network, it's not connected in
the sense that we might think about. You
cannot get from any one point A to any
other point B. For example, if you start
at the right most node in this graph,
certainly there's no directed path that
will get you to the left most node. So
what's typically studied and most useful
for directed graphs, is what you call
strong connectivity. The graph is strongly
connected if you can get from any one
point to any other point, And vice versa.
And the strongly connected components
then informally, are the maximal portions
of this graph, the maximal regions which
are internally, strongly connected. So,
the maximal regions from within which you
can get from any one point A to any other
point B along a directed graph. For the
record, let me go ahead and give you a, a
formal definition although, you know, this
intuition is perfectly valid just regions
where you can get from anywhere to
anywhere else. So we say that the strongly
connected components of the directed graph
or the SCCs for short. And as in the
undirected case, we're going to give a
somewhat slick definition, rather than
talking about maximal regions satisfying
some property, we're going to talk about
the equivalence classes of a particular
equivalence relation. But really it means
the same thing. This is just sort of the
more mathematically mature way of writing
it down. So the equivalence relation we're
going to use it on nodes of the graph and
we'll say that U, a node, is related to a
node V if you can get from U to V via a
directed path and also from V to U on some
other directed path. [sound] I'm not gonna
bore you with the verification that this
is an equivalent relation. That's
something that you can work out in the
privacy of your own home. Just remember
what it means to be in an equivalence
relation. It's reflexive. That is,
everybody's related to itself but, of
course, there is a path from every node to
itself. It also means that it's symmetric.
So if U is related to V, then V is related
to U. Well, again, by definition, we're
saying that the paths are mutually, the
vertices are mutually reachable from each
other. So that's clearly symmetric by
definition and then it has to be
transitive. And the way you prove it's
transitive, is you just paste paths
together and it just works the way you'd
expect it to. So let's illustrate this
concretely with a, a somewhat more
complicated directed graph. So here's a
directed graph and I claim that it has
exactly four strongly connected
components. There's a triangle on the
left, a triangle on the right. Has this
single node on top and then it has this
directed four-cycle with a diagonal at the
bottom. So what I hope is pretty clear is
that each of these circled regions is
indeed strongly connected that is if you
start from one node in one of these
circled regions you can have a directed
path to any other node, so that's
certainly true cause on a directed cycle you can
get from anyone starting point and the
other place and all of these have directed
cycles and there's the one strong
component that just has one node which is
obviously strongly connected. What I
also claim is true is that all of these
regions are maximal subject to being
strongly connected. That's why they're the
strongly connected components. That's why 
they're the equivalence classes of this equivalence
relation we just defined. So, if you take
any two pairs of nodes which lie in two
different circles you either won't have a
path from one... From the first one to the
second one or you won't have a directed
path from the second one back to the first
one. In fact, the structure of the strong
components in this black graph exactly
mirrors, the directed acyclic graph that
we started with in red. So in the same
way, in the red four node graph, you can't
move from right to left. Here in this
bigger graph, you can't move from any of
the circled SCC's to the right to any of
the circled SCCs to the left. So, for
example, from the rightmost nodes, there
are no directed paths to the leftmost
nodes. So that's a recap of the definition
of the strongly connected components, I've
motivated in a separate video some reasons
why you might care about computing
strongly connected components. In
particular, on extremely large graphs,
which motivates the need for blazingly
fast subroutines so for-free primitives
that will let you compute connectivity
information. So you'd love to be able to
know the pieces of a directed graph, maybe
you don't even know why they're going to
be useful, but you just compute them
because why not? It's a for-free primitive.
So that's what I'm gonna give you in this
lecture. So the algorithm we're gonna
present is based on depth-first search, and
that's gonna be the main reason why it's
going to be so blazingly fast because
depth-first search is blazingly fast. Now you
might be wondering what on earth does
graph search have to do with computing
components? They don't seem obviously
related, so let's return to the same
directed graph that I showed you on
the previous slide. And to see why something
like depth-first search might
conceivably have some use for computing
strong components. Suppose we call
depth-first search, starting from this red node
as a starting point. What would it
explore? So remember what the guarantee of
something like depth-first search or
breadth-first search, for that matter, is.
You find everything that's findable, but
naturally, nothing else. So what is
findable from this red node? Where, by
findable, I mean is you can reach it from
a directed path emanating from this red
node. Well, there's not much you can do,
so, from here, you can explore this arc,
and you can explore this arc, and then you
can go backward. And so if you do DFS
or BFS from this node you're going to find
precisely the nodes in this triangle.
All of the other arcs involved go the
wrong direction and they won't be
traversed by say a depth-first search
call. So, why is that interesting? What's
interesting is that if we invoke DFS from
this red node or any of the three nodes
from this triangle then it's going to
discover precisely this strongly connected
component. Precisely the three nodes in
this circled SCC. So that seems
really cool. It seems like maybe we just
do a DFS, and boom, we get an SCC. So
maybe if we can do that over and over
again, we'll get all the SCCs. So that's a
good initial intuition. But something can
go wrong. Suppose that instead of, an,
initiating DFS from one of these three
nodes on the triangle, we, say, initiate
it from this bottom-most node in green. So
remember, what is the guarantee of a graph
search subroutine like DFS? It will find
everything findable but of course nothing
more. So what's findable from this green
node? Well naturally, everything in its
own SCC. Right, so the four nodes here, it
will certainly find those four nodes. On
the other hand, if we start from this
green node, since there are arcs that go
from this bottom most SCC to the right
most SCC, not only will this DFS call find
the four nodes in the green node's strong
component, but it will also traverse these
blue arcs and discover the three nodes in
the red triangle. So, if we call DFS from
this green node, we'll capture all seven
of these. So the point is if we call DFS,
it looks like we're going to get a
union of possibly multiple SCCs. In fact,
in the worse case, if we invoke DFS from
the left-most node, what's it going to
discover? It's going to discover the
entire graph, and that didn't give us any
insight into the strong component
structure at all. So, what's the take away
point is, the take away point is if you
call DFS from just the right place, you'll
actually uncover an SCC. If you call it
from the wrong place, it will give you no
information at all, so the magic of the
algorithm that we're gonna discuss next is
we'll show how in a super slick
pre-processing step which ironically is
itself a call to depth-first search, we can in
linear time compute exactly where we want
to start the subsequent depth-first searches
from, so that each invocation gets us
exactly one strongly connected component, and nothing more. So
the algorithm that, that I'm going to show
you is due to Kosaraju. And it will show
the following theorem. That the strongly
connected components of a directed graph
can be computed in linear
time. And as we'll see, the constants are
also very small. It's really just gonna be
two passes of depth-first search. And again,
let me remind you that for many
problems it's natural to assume that the
number of edges is at least the number of
nodes because, if you're only interested
in cases where the graph is connected. Of
course, when you're computing connected
components, that's one of the most natural
cases where you might have a super sparse,
broken up graph. So we're not going to
assume m is at least n. So that's why
linear time is going to be m + n, because
that's the size of the input. And we don't
know, either M could be bigger than N, or
N could be bigger than M. We have no idea.
Kosaraju's algorithm is shocking in its
simplicity. It has three steps, let me
tell you what they are. First, very
mysteriously, we're going to reverse all
of the arcs of the given graph. Totally not
clear why that would be an interesting
thing to do yet. Then, were going to do
our first pass, our first depth-first search,
and we're going to do it on the reverse
graph. Now, the naive way to implement
this would be you literally construct a new
copy of the input graph, with all of the
arcs in the reverse direction. And then
just run depth-first search on it. Of
course, the sophisti--, the sort of
obvious optimization would be to just run
DFS on the original graph, but going
across arcs backward. So I'll let you
think through the details of how you'd do
that, but that just works. You run DFS,
and instead of going forward along edges,
you go backward along edges. That
simulates depth-first search on the
reverse graph. Now, I've written here, DFS
loop. And that just means the usual trick
where, to make sure that you see all of
the nodes of, of the graph, even if it's
disconnected, you have an outer loop,
where you just try each starting point
separately. If you haven't already seen
it, then you run DFS from that given node.
I'll be more detailed on the next slide.
And the third step, it's just you run
depth-first search again, but this time on
the original graph. Now at this point, you
should be thinking that I'm totally crazy,
right? So what are we trying to do? We're
trying to compute these strongly connected
components. We're trying to actually
compute real objects, these maximal
strongly connected regions. And all I'm doing is
searching the graph. And I do it once
forward, I do it once backward. I mean,
I'm not, it doesn't really seem like I'm
computing anything. So, here's the catch,
and it's a very minor catch. So we're
gonna need, to do a little bit of bookkeeping,
it's gonna be very little overhead, so we'll still
have a blazingly fast algorithm. So, but with a little bit of bookkeeping,
here's what's gonna happen. The second depth-first search, which searches the graph, will,
in its search process, discover the strongly connected components one at a time
in a very natural way, and that'll be really obvious when we do an example, which we'll do in just a second.
Now, for the second depth-first search to work in this magical way, where it just discovers the strongly connected
components one at a time, it's really
important that it executes the depth first
searches in a particular order, that it
goes through the nodes of the graph in a
particular order. And that is exactly the
job of the first pass. The depth-first
search on the reverse graph is going to
compute an ordering of the nodes, which,
when the second depth-first search goes
through them in that order, it will just
discover the SCCs one at a time in linear
time. So let me say a little bit more
about the form of the bookkeeping and then
I'll show you how that bookkeeping is
kept in as we do depth-first
search. So we're gonna have a notion of a
finishing time of a vertex and that's
gonna be computed in the first pass when
we do depth-first search in the reversed
graph. And we're going to make use of this
data in the second pass. So, rather than
just going through the nodes of the graph
in an arbitrary order, like we usually do
when we sort of have a looped
depth-first or breadth-first search, we're
going to make sure that we go through the
vertices in decreasing order of these
finishing times. Now there's still the
question in what sense does this second
depth-first search discover and report the
strongly connected components that it finds?
So we're going to label each node in this
second pass with what we call a leader and
the idea is that the nodes in the same
strongly connected components will be labeled
with exactly the same leader node. And
again all of this will be much more clear
once we do a concrete example. But I want
to have it down for the record right now.
So that's the algorithm at a high level
it's really just two passes of DFS with
some bookkeeping. But this is under
specified. You really, shouldn't,
understand how to implement the
algorithm just yet. So what do I owe you?
I owe you exactly what I mean by DFS loop
although this you've seen more or less in
the past. It's just a loop over all the
vertices the graph and then when if you
haven't seen something yet you DFS from
that starting point. I need to tell you
what finishing times are and how they get
computed. They're just gonna be integers
one to N. Which is basically when
depth-first search gets finished with one
of the nodes. And then I need to tell you
how to compute these leaders. So let me
show you all three of those things on
the next slide. So the workhorse for
Kosaraju's strongly connected components
algorithm is this DFS loop subroutine and
it takes as input in graph. Okay, so it
does not take as input a starting node,
it's gonna loop over possible starting
nodes. Now for the bookkeeping, to
compute finishing nodes, we're going to
keep track of a global variable that I'll
call T, which we initialize to zero. The
point of T is to count how many nodes we
have totally finished exploring at this
point. So this is the variable we use to
compute those finishing times in the first
pass. That magical ordering that I was
talking about. Now we're also gonna have a
second global variable to compute these
things I was calling leaders, and these
are only relevant for the second pass. So
what S is going to keep track of is the
most recent vertex from which a DFS was
initiated. So to keep the code simple I'm
just going to do all of the bookkeeping in
DFS loop, but really DFS loop gets
called twice, once in the reverse graph,
once in the forward graph and we only need
to compute these finishing times in the
first pass, on the reverse graph. And we
only need to compute these leaders of the
second pass for the forward graph. But
let's just keep them both in there, just
for kicks. Now, we're going to need to
loop through the vertices. And so the
question is, in what order are we going to
loop through the vertices? And that's
gonna happen differently in the two
different passes. But let me just use some
common notation. Let's just assume in this
subroutine, that the nodes are somehow
labeled from one to N. In our first depth-first
search it's gonna be labeled totally
arbitrary. So these are basically just the
names of the node, or their position in
the node array, whatever, you just do it
in some arbitrary order. Now the second
time we run DFS loop, as indicated on the
previous slide, we're gonna use the
finishing times as the labeling. And as
we'll see the finishing times are indeed
numbers between one and N. So now what we
do is we just iterate through the nodes in
decreasing order. And if we haven't
already seen node I, then we initiate a
DFS from it. So, as usual, we're gonna be
maintaining a local boolean to keep track
of whether we've already seen a node yet
in one of the DFS passes. Now remember,
the global variable S is responsible for
keeping track of the most recent node from
which depth-first search had been
initiated. So if I is not explored and we
initiate a depth-first search from it, we'd
better reset S. And then we do the usual
DFS in G, starting from the source node I.
So for completeness let me just remind you
what the depth-first search subroutine
looks like. So now we're given a graph and
a starting node. So the first time we see
a node, we mark it as explored. And just a
side note that once a node is marked
explored it's explored for this entire
invocation of DFS loop. Okay, so even if
this DFS from a given node I finishes and
then the outer for loop marches on, and
encounters I again it's still gonna be
marked as explored. Now
one of our bookkeeping jobs is to keep
track of, from which vertex did the DFS
that discovered I get called, so
when I is first encountered, we remember
that S was the node from which this DFS
originated, and that by definition is the
leader of I. And then we do what we always
do with depth-first search. We immediately
look at the arcs going out of I, and we
try to recursively DFS on any of those.
Although, of course, we don't bother to do
it if we've already seen those nodes. Now
once this for loop has completed, once we've
examined every outgoing arc from I and
for each node J either we already saw in
the past or we've recursively explored
from J and have returned, at that point we
call ourselves done with node I. There's
no more outgoing arcs to explore, we think
of it being finished. Remember T is the
global variable that's keeping track of how
many nodes we're done with. So we
increment T because now we're done with I and
we also remember that I was the Tth
vertex with which we finished. And that
is, we set I's finishing time to be T.
Because depth-first search first is
guaranteed to visit every node exactly
once, and therefore finish with every node
exactly once. This global counter T, well,
when the first node is finished, it'll be
value one. Then when the next node gets
finished, it'll have value two, then it'll
have value three and so on. When the final
node gets finished with, it'll have value
N. So the finishing times of the nodes are
gonna be exactly the integers from one to
N. Let's make this much more concrete by
going through a careful example. In fact,
I think it will be better for everybody if
you yourself trace through part of this
algorithm on a concrete example. So let me
draw a nine-node graph for you. So to
be clear let's assume that we've already
executed step one of the algorithm.
That is, we've already reversed the
graph. So that is. This blue graph that
I've drawn on the slide. This is the
reversal. We've already reversed the arcs.
Moreover the nodes are labeled in some
arbitrary way from one to nine. Just
assume these are how they show up in the
node array for example. And remember in
the DFS loop routine we're supposed to
process the nodes, from the, from top to
bottom. From N down to 1. So my
question for you then is, in the second
step of the algorithm when we run DFS loop
and we process the nodes from the highest
name 9 in order down to the lowest name
1. What are the finishing times that
we're going to compute as we run DFS loop?
Now, it is true that you can get different
finishing times depending on the different
choices that the DFS loop has to make about
which outgoing arc to explore next. But
I've given you four options for what the
finishing times of the nodes one, two,
three, all the way up to nine respectively
might be, and only one of these four could
conceivably be an output of the finishing
times of DFS loop on this graph. So, which one is it?
Alright. So the answer is the
fourth option. That is the only one of
these four sets of finishing times that
you might see being computed by DFS loop
on this blue graph. So let's go ahead and
trace through DFS loop and see how we
might get this set of finishing times. So
remember in the main loop we start from
the highest node, nine, and then we
descend down to the, to the lowest node,
one. So we start by invoking DFS from the
node nine. So now, from here there's only
one outgoing arc we have to go to, so we
mark nine as explored. And then there's
only one place we can go. We can go to six
so we mark six as explored. Now there's
two places we can go next. We can either
go to three or we can go to eight. And you
know, in general DFS could do either
one. Now to generate this fourth set of
finishing times, I'm going to need to
assume that I go to three first. Okay, so
again, what DFS does, what we're
assuming it does is it starts at nine,
then it has to go to six. It marks those
as explored. Then it goes to three. It
does not go to eight first. It goes to
three first. Now from three there's only
one outgoing arc which goes to nine but
nine you've already marked as explored. So
it's not going to re-explore nine, it's
going to skip that arc. Since that, that's
3's only outgoing arc, then that for loop completes.
And so three is the first node to finish.
So when we finish with three we increment
T. It started at zero, now it's one. And
we set the finishing time of three to be
one. Just like we said it was in the
example. So now we go back. Now we
backtrack to six. Now we have another
outgoing arc from six to explore, so now
we go to eight. From eight, we have to go
to two. From two, we have to go to five.
From five, we have to go to eight. Eight,
we've already seen, so then we're gonna be
done with five, because that was its only
outgoing arc. So then we increment T. Now
it's two, and the finishing time of five
is going to be two. As promised. So now we
backtrack to two. There's no more outgoing
marks from two. So 2's gonna be third one
that we finish, as promised. Then we
finish with eight. So the finishing time
for eight is gonna be the fourth node to
be done, as promised. Now we backtrack to
six, we're done with six. That's the fifth
node to be completed, as promised. And
finally we got all the way back to where
we started at nine and nine is the sixth
node to be completed, as promised. Now if
we were computing those leaders, all of
these nodes would get the leader nine. But
again the leaders are only relevant for
the second pass, so we're just going to
ignore the leaders as we're doing this
trace. We're just going to keep track of
the finishing times. So now we're not
done, so all we did is we finished with
the DFS that is invoked from the node nine
and we found six of the nodes total in
that depth-first search. So now we return
to the outer for loop and we decrement I,
so it started at nine, we're done with
that, now we go down to eight, we say that
we've already seen eight. Yes, eight's
already explored. So we skip it. We go, we
decrement I down to seven, we say have we
already seen node seven. No we have not.
Okay, seven is not yet explored, so we
invoke DFS now from node seven. Seven has
two outgoing arcs. It can either go to
four or it can go to nine. Let's say it
checks the outgoing arc to nine first. Now
nine we already explored. Granted that was
in an earlier part of the for loop, but
we remember that. We, we're going to
keep track of who got explored on previous
iterations of the for loop. So we don't
bother to re-explore nine. So we skip
that. So now from seven we have to go
to four. From four we have to go to one.
From one we have to go back to seven. 7's
already been explored, so we backtrack,
now we're down to, we're done with one. So
one is the next one we're completed with.
And the finishing time of one is going to
be seven, as promised. We backtrack to
four. There's no more outgoing arcs from
four to explore, so that's going to be the
eighth one to finish as promised. And then
the last one to finish is poor node seven.
It is last. So that would be an example of
how the DFS loop subroutine computes
finishing times on a reversed graph. So
now let's work through the second pass on
the forward version of the graph using the
same example. Now remember the point of
the first pass is to compute a magical
ordering. And the magical ordering is
these finishing times. So now we're going to
throw out the original node name and we're
going to replace the node names in blue by
the finishing times in red. We're also
going to work with the original graph
which means we have to reverse the arcs
back where they were originally. So, those
are the two changes that you're going to
see when I redraw this graph. First of
all, all the arcs will reverse
orientation. Second of all, all the nodes
will change names from their original
ones to the finishing times that we just
computed. So here's our new graph with the
new node names and all the arcs with their
orientation reversed. And now we run DFS
again on this graph. And again we're going
to process the nodes in order from the
highest label nine down to the lowest
label one. Moreover we don't need to
compute finishing times in the second
pass. We only need to do that in the first
pass. In the second pass we have to keep
track of the leaders. And remember the
leader of a vertex is the vertex from
which DFS was called. That first, that
first discovered that node. Alright, so
what's going to happen. Well, in the outer
for loop, we're going to start with I
equal to nine. And we invoke DFS from the
node nine. So that's gonna be the current
leader. Cause that's, where the current
DFS got initiated. Now from nine
there's only one choice. We have to go to
seven. From seven there's only one choice.
We have to go to eight. From eight there's
only one choice. We have to go back to
nine. And then nine's already been seen
so we backtrack. We go back to eight. We
go back to seven. We go back to nine and
that's it. So when we invoke DFS
from node nine the only things that we
encounter are the nodes seven, eight and
nine. And these are all going to be given
the leader vertex nine. You will notice
that this is indeed one of the strongly
connected components of the graph. We just
sort of found it with this invocation of
DFS from the node nine. So now we go back
to the outer for loop. And we say, okay,
let's go to node eight. Have you already
seen eight? Yes. What about seven? Have
you already seen seven? Yes. What about
six, have you already seen six? We have
not, we have not yet discovered six. So we
invoke DFS from node six, we reset
the global source vertex s to six. From
six we can go to nine or we can go to
one. So let's say we explore nine first.
Well we already saw nine in the earlier
iteration of the for loop so we don't
explore it again. So we don't discover
nine now. So we backtrack to six. We go to
one. From one we have to go to five. From
five we have to go to six and then we
start backtracking again. So the only new
nodes that we encounter when we invoke DFS
from the node six are the vertices six,
one, and five. And all of these will have
a leader vertex of six. Because that's
where we called DFS from, when we first
discovered these three nodes. And you'll
notice this is another SCC of this
directed graph. So we invoke DFS again
now from a new node, the new node six, and
what it discovered, the new nodes
discovered, is exactly an SCC of the
graph; nothing more, nothing less. So now
we return to the outer for loop. We go to
net five. Have we already seen five? Yes.
Have we already seen four? No. We haven't
seen four yet. So now we invoke DFS from
four. Again, we could try to explore five,
but we've already seen that before, we're
not going to explore it again. So from
four then, we have to go to two. From two,
we have to go to three. From three, we
have to go back to four, and then after
all the back tracking, we're done. So the
final call to DFS will be from the node
four. And that DFS will discover
precisely, newly discover precisely the
nodes 2,3 and 4. They will all have the
leader vertex four because that was where
this DFS was called from. It's true we
will go back to the for loop and we will
check, have we seen three yet, yes, have
we seen two yet, yes, have we seen one
yet, yes, and then the whole thing
completes. And what we see is that using
the finishing times computed from that
first depth-first search pass, somehow the
strongly connected components of this
graph just showed up and presented
themselves to us, one at a time, on a
silver platter. Every time we invoked DFS,
the nodes we discovered newly were
precisely one of the SCCs. Nothing more,
nothing less. And that's really what's
going on in this algorithm. It turns out
this is true in general. The first pass,
DFS on the reverse graph, computes
finishing times so that if you then
process nodes according to decrease ordering
of finishing times in the second
pass, each invocation to DFS will discover
one new SCC and exactly one SCC. So
they'll just present themselves to you one
per DFS call in that second pass's for
loop. This is, of course, merely an
example. You should not just take a single
example as proof that this algorithm
always works. I will give you a general
argument in the next video. But hopefully
there's at least a plausibility argument.
No longer does this three step algorithm
seem totally insane, and maybe you could
imagine perhaps it works. At least there's
some principles going on where you first
compute the right ordering to process
the nodes, and, and then the second pass
peels off SCCs one at a time like layers
from an onion. One thing that I hope is
pretty clear is that this algorithm
correct or not, is blazingly fast. Pretty
much all you do is two depth-first searches.
And since depth-first search, as we've seen
in the past runs in time linear in the
size of the graph so does Kosaraju's two-pass
algorithm. There are a couple of
subtleties and I encourage you to think
about this so you'll be forced to think
about this in the programming project for
week four. So for example, in the second
pass how do you process the nodes in
decreasing order of finishing time? You
don't want to sort the notes by their
finishing time cause that would take
n log n time, so you need to make sure that
you remember in the first pass that you
sort of remember the nodes in a way that
you can just do a linear scan through them
in the second pass. So there are some
details but if your intuition is that this
is really just double DFS properly
implemented that's pretty much exactly
right. So having spelled out the full
implementation, argued that it's
definitely a linear time algorithm, and
given at least a plausibility argument via
an example, that it might conceivably be
correct, let's now turn to the general argument.