As our final digraph processing algorithm, we'll take a look at computing strong
components. So the definition two vertices, v and w,
in a digraph are strongly connected if there's a directed path from v to w and
another directed path from w to v. And the thing about strongly connected is
that it's unequivalence relation. That is each vertex is strongly connected to
itself. If v is connected to w, strongly, and w is
strongly connected to, to, then w is strongly connected to v.
That just means that paths, directed paths connecting them.
And it's also transitive. If v is connected to w and w to x,, then v
is strongly connected to x. How to get from v to x? You go from w, v
to w and w to x, And get from x to v, you go from x to w
and w to v. So, that means that since it's an
equivalence relation, it divides the digraph up into components, into sets
called strongly connected components that have the property that there's directed
paths connecting each pair of vertices in the set.
So, for example nine and twelve are strongly connected,
There's a path from twelve to nine, Another one from nine to twelve and so
forth. So the,
Our challenge is to compute the strong components in diagraphs.
And it's worth comparing this to what we did for connected components in undirected
graphs. So, this is just a quick review.
In an undirected graph, if there's a path between two vertices that are connected,
that's an equivalence relation, divides them up into connective components.
And what we did was, our design pattern is to build our graph processing algorithm as
a constructor that takes a graph and does the pre-processing to create a table like
this one which assigns a unique ID to all the vertices in each given component.
So, that we can have a constant time client query to check whether two given
vertices are in the same connected component or not.
So, linear time processing, pre-processing in the constructor to build the table,
constant time client queries. And that's as good performance as we can
expect to have for a graph for a graph processing algorithm.
Remarkably, now, we're able to do the same thing for strong connectivity.
It's a, it's a much more sophisticated algorithm but the design pattern and the
bottom line for the client is the same. There's a constructor, it processes the
graph in linear time. And it assigns a unique ID to each one of
the strongly connected components in the graph.
So, once in the component by itself, Zero, two, three, four, and five six, and
eight, seven, and nine, ten, and twelve, There's five different strongly connected
components in this graph. The constructor builds that array and the
client gets to in constant time, know whether two vertices are strongly
connected or not. It's quite amazing that we can solve this
problem in this way. And as I'd mentioned it's got an
interesting history that we'll talk about in a second.
So, here's an example of strong component application.
So, the food web graph, This is a very small subset of that graph.
The vertices are all the, species and an edge goes from producer to consumer.
So, if animal a eats animal b, there's an edge from a to b.
And what a strong component corresponds to in this graph is a kind of a subset of
species that, have a common energy flow. They naturally eat each other.
And that's extremely important in ecological studies.
Another example is again, in processing software big software is made up of
modules. And the vertices are, are, are, are the
modules. And edges is if one depends on another.
And so a strong component in this graph is a subset of mutually interacting modules.
And in a huge program like Internet Explorer you want to know what the strong
components are so that you can package them together and maybe improve the
design. So again, software you know, can, these
graphs can be huge. And this kind of graph processing can be
extremely important in improving the design of software.
Now again this algorithm has an interesting history,, it along with
scheduling and other things that's a core problem in operations research that was
widely studied, but really not understood how difficult it was.
In Tarjan's paper in 1972 was a big surprise that this could be solved in
linear time with depth research. Now this algorithm had a couple of other
data structures and this I guess, A diligent student in this class could
understand it with quite a bit of work. But it really demonstrated the importance
of depth-first search in great graph processing.
Now, the algorithm that we're going to talk about today actually was invented in
the 80s' by Kosaraju and, and independently by Sharir.
The story goes that Kosaraju had to go lecture about Tarjan's algorithms and he
forgot his notes. And he had taught it a number of times, he
was trying to figure out what Tarjan's algorithm did and he developed this other
algorithm that's extremely simple ro implement.
That's what we're going to look at today, today.
And actually in the 1990s Gabow and Mehlhorn and particularly, Melhorn had to
implement this algorithm for a big software package and he found another
simple linear time algorithm. Now, so, this story indicates even from
fundamental problems in graph processing there's algorithms out there still waiting
to be discovered and this, this algorithm is a good example of that.
So we give the intuition in the code and you see how the algorithm works fully
convincing yourself or proving why it works is a bit more of a challenge.
Now, we'll leave that mostly for the book. But let's describe what it is.
So, the first idea is to think about the reverse graph.
So if we take a graph and we reverse the sense of all the edges we're going to get
the same, strong components. We need edges in both directions.
So, if we switch the directions, we're still going to have edges in both
directions. The, the second concept is called the,
the, the kernel DAG. And what that does, is it kind of, you
think about contracting each strong component into a single vertex.
And then, just to worry about the edges that go from one strong component to
another. So the digraph that you get that way,
turns out to be a cyclic. If it was cyclic, it would involve, it
would create a bigger strong component, a couple of strong components into one.
So if we think about that processing that kernel DAG, that's the edges that go
between strong components and we get a DAG and we know how to deal with a DAG So, the
idea of the algorithm is to go ahead and compute the topological order or the
reverse post order in the kernel DAG. At least put up the edges of the original
digraph in order so that all the edges in the kernel DAG point from right to left,
That's like a topological sort. And then we run DFS but instead of
considering the vertices in, in numerical order for the DFS, we consider them in
that reverse topological order. So it's extremely easy to implement this
algorithm. Of course, we're going to use DFS.
So let's look at a demo at how the algorithm works., okay, so, this is a
digraph, and our goal is to compute the strong components.
And we're going to do it in two phases, two DFSs.
One is to compute the reverse post order and the reverse of the graph.
And the other is to run the DFS but for the other in which we visit the vertices,
we use that reverse post order that we've computed. so here goes.
So, first, we'll do the DFS and the reverse graph.
So that's the graph, that's the reverse graph.
Remember, these two has the same strong component.
So, there's our marked array. We will do the DFS, and reverse post order
means that when we are done with the vertex, we'll put it out.
So checked six unmarked, checked eight unmarked checked six, it's marked. so
we're done with a answer, that's the reverse post order. and again, as before,
put it on a stack and but we'll just list them in reverse order in this demo.
So, eight is done. So, six lots of places to go from six.
So, let's check seven. That's unmarked, so we go to seven.
No place to go from seven, so we're done with seven.
We put it on the reverse post order list. We're also done with six.
Cuz four and nine are coming in, in this example, so I put it on the list.
Next place to go from zero is two, so we checked two
That's unmarked so we mark it and recurse and we checked the vertices adjacent to
two. First, four, that's unmarked.
So, then we recurse and go to four. We gotta got to, to eleven first and
recurse so now we're at eleven. And, and from eleven, we go to nine, which
is unmarked. So we have a pretty long recursive stack
right here. So, from nine, there's we have to check a
bunch of things, we'll check twelve first and then visit twelve.
It's unmarked from twelve, we checked eleven which is marked, nowhere to go.
Then, we checked ten. That's unmarked, so we go to ten.
Visit ten it's, it's unmarked so we recurse and then go to nine.
And that's marked and that's everywhere we get from ten.
So, we're done with ten, so we put it on the list and return. And now, where done
with twelve, so we put it on the list and return.
And now, at nine, we have to check seven, which is marked, and six, which is marked.
And then, we're done so we put it on the list.
Then, we're done with eleven we put it on the list.
Then we're finished with four, so we checked six which is marked, then we
checked five, which is unmarked so we recurse to five.
From five, we checked three which is unmarked so we recurse.
Then, we checked four which is mark, we checked two which is mark.
And then we're done with three, so we put it on the list.
And then from five we checked zero it's marked so we're done with five, we put it
on the list. And that means that we're now done with
four. And then, we're also done with two, after
checking three. And then, we go to zero and put it on the
list. So, that's all the vertices that, you
know, you get through from zero. So, we look for more vertices and it's one
and it's marked so that's the last one in the reverse post order.
So, that's a reverse post order of the reverse graph.
And all we're going to do is take that order and use that order to check vertices
at the top level in the depth-first search of our regular graph.
We have to check all the other vertices to make sure we are done.
So, that's phase one. So now, we'll just do a DFS in the
original graph, using that order that we just computed. So, we don't start with
zero, the way we always have, now we start with one. we visit one, its unmarked and
now all the vertices that we visit during that DFS are going to be in that same
strong component, that's the theorem that makes this algorithm work, in this case,
this is only the one, so vertex one is its own, is in its own strong component with
label zero. So now, we've got to start, once all done,
so now, we have to start with looking for another vertex to search from.
In this case, it's zero that's second on the list.
So that's where we start, With zero.
And now, all the vertices that we can reach from zero are going to have strong,
in this graph, are going to have strong component label one.
So, we do the DFS. So, first, we get to five.
That's in the same strong component we checked four.
And it's unmarked. So, we label it.
We checked three, it's unmarked. We checked five, which is marked.
We checked two, which is unmarked. So now we have shown that zero, two,
three, four, and five are all in the same strong component.
And now we're going to find both vertices we can get three from two or mark.
So we're done with two then we're done with three.
Four, we have to check two, which is marked.
And then, we're done with four and five. From zero we can check one but that's
already marked so that's not relevant for this search and then we're done with zero.
And we've established that zero, two, three, four, and five are all in the same
strong component. , So that's the second one.
So now, we continue and we check all of those and they're all marked. so, the next
vertex in the reverse post order of the reverse graph is eleven so we visit
eleven. Checked four,
It's already marked. Checked twelve,
It's not so aj. we mark it, and these are the third strong component.
They get labeled with two. Then, we get to nine. from nine, we check
eleven and nowhere to go. Then, we checked ten, and so that's seems a strong
component. from ten, we checked twelve, which is marked. We're done with ten, were
done with nine, were done with twelve, and were done with eleven. so, that's our
second strong or third strong component nine, ten, eleven and twelve.
So we're done with those and now we go through the list to find another unmarked
vertex. Nine is marked, twelve is marked, ten is
marked. we get to six from six nine is already marked. four is four is already
marked. Eight is not marked so we go there. from
eight, we get to six and that's it. Zero is already marked so we can only get
to eight from six at this point, and so that's a strong component.
And then finally, we finish up by doing seven.
So the end of the computation gives us the strong component array, which is a unique
ID for each of the vertices so that two vertices in the same strong component have
the same ID. And that supports constant time strong
connectivity checks for clients. And so, the bottom line is that this
algorithm is a very simple even though it might be mysterious algorithm for
computing the strong component. First, run DFS on the reverse graph to
compute the reverse post order. Then, run DFS on the original graph
considering the vertices in the order given by the first DFS.
And so these, these diagrams give a summary of the computation.
I'm not going to spend too much time explaining why and how it works in this
lecture. But these kinds of diagrams give the
detail that can give some intuition about how and why the algorithm works.
The for the proof it requires some mathematical sophistication and find it in
the book. But the programming of it is quite simple
and proved that it's efficient is and all it does is run DFS twice but to really see
the correctness proof you want to look a the second printing of the textbook. we
got it wrong in the first printing. And, but look at the implementation so,
this is connected components and in the undirected graph with DFS that we did last
time and I'm sure many of you thought that it was one of the simplest algorithms that
we looked at. We just marked the vertices and do
recursive and that's the end of it. If you take that code and just had I'll
change the names. And then just instead of going for the
vertices from zero through v minus one if you first compute the depth-first order
that you get by running doing that first search of the reverse graph and then you
iterate through the vertices in that order, you get an algorithm for strong
connectivity. It's really remarkable that just changing
that one line will perform this computation that was thought to be
difficult for,, for many years, and, and people were learning quite difficult codes
for, for many, many years. So, that's a quick summary of digraph
processing. We talked about single source reachability
getting the paths from a vertex to any vertex that can be reached from that
vertex with a directed path. We talked about topological sort in graphs
that have no cycles and that uses DFS. And we talked about computing strong
components in a digraph with two DFSs. Digraph processing is really h, a
testimony to the ingenuity that's possible in algorithm and graph processing.