Source: https://www.coursera.org/lecture/algorithms-graphs-data-structures/topological-sort-yeKm7
Timestamp: 2019-04-18 15:45:33+00:00

Document:
the arcs, the directed edges of the graph, only go forward in the ordering.
the vertices with the numbers one through n.
This is just to encode the position of each vertex in this ordering.
maps them to integers between 1 and n.
Each of the numbers 1 through n should be taken on by exactly one vertex.
Here n is the number of vertices of G.
every directed edge of G goes forward in the ordering.
then it should be that the f value of the tail is less than the f value of the head.
Let me give you an example just to make this more clear.
So suppose we have this very simple directed graph, with four vertices.
totally legitimate topological orderings of this graph.
is you could label s1, v2, w3 and t4.
except you can swap the labels of v and w.
So if you want, you can label v 3 and w 2.
what these labelings are really meant to encode is an ordering of the vertices.
the ordering in which we put s first then v then w and then t.
the nodes except with w coming before v.
cases, and in particular all of the edges go forward in this ordering.
So in either case we have s with edges from s to v, and s to w.
then symmetrically there are edges from v and w to t.
all four of these edges go forward in each of these orderings.
from s to v would be going backward if v preceded s.
you would not have a topological ordering.
these are the only two topological orderings of this directed graph.
I encourage you to convince yourself of that.
Now, who cares about topological orderings?
Well, this is actually a very useful subroutine.
This has been come up in all kinds of applications.
By precedence constraint I mean one task has to be finished before another.
major like a computer science major.
course B, if you have to take it first.
courses so that you always take a course after you've taken its pre-requisite.
And that's exactly what a topological ordering will accomplish.
how do we get our grubby little hands on it?
a graph to have a topological ordering, which is it had better be a cyclic.
then there is certainly no way there is going to be a topological ordering.
So I hope the reason for this is fairly clear.
consider any purported way of ordering the vertices.
Well, now just traverse the edges of the cycle, one by one.
You already know that this ordering is not topological.
No edges can go backward.
So evidently, the first edge of this cycle has to go forward.
eventually you come back to where you started.
So if you started out by going forward, at some point you have to go backward.
violating the property of the topological ordering.
directed cycles exclude the possibility of topological ordering.
Now the question is what if you don't have a cycle?
the obvious one of having circular precedence constraints?
you don't have any directed cycles, you're guaranteed a topological ordering.
But we can even compute on in linear time no less via depth-first search.
topological orderings of depth-first search.
intuition about directed acyclic graphs and their topological orderings.
So for the straightforward solution, we're going to begin with a simple observation.
Every directed acyclic graph has what I'm going to call a sink vertex.
That is a vertex without any outgoing arcs.
there's exactly one source of sink vertex, and that's this right-most vertex here.
the other three vertices all have at least one outgoing arc.
Now why is it the case that a directed acyclic graph has to have a sink vertex?
Well, suppose it didn't, suppose it had no sink vertex.
That would mean every single vertex has at least one outgoing arc.
So what could we do if every vertex has one outgoing arc?
Well, we can start in an arbitrary node.
We know it's not a sink vertex, because we're assuming there aren't any.
So there's an outgoing arc, so let's follow it.
We get to some other node.
there's an outgoing arc, so let's follow it.
That also has an outgoing arc, let's follow that, and so on.
because every vertex has at least one outgoing arc.
Well there's a finite number of vertices, right this graph has say N vertices.
So if we follow N arcs, we are going to see N+1 vertices.
So by the pigeon-hole principle, we're going to have to see a repeat.
we're going to see some vertex twice.
I get back to this one that I saw previously.
Well, what have we done?
What happens when we get a repeated vertex?
we have exhibited a directed cycle.
And that's exactly what we're assuming doesn't exist.
We're talking about directed acyclic graphs.
we just prove that a vertex with no sink vertex has to have a directed cycle.
So a directed acyclic graph therefore has to have at least one sink vertex.
ordering of a directed acyclic graph.
Well let's do a little thought experiment.
Suppose in fact this graph did have a topological order.
Let's think about the vertex which goes last in this topological ordering.
Remember, any arc which goes backward in the ordering is a violation.
So we have to avoid that.
We have to make sure every arc goes forward in the ordering.
we better put somewhere other than in the final position, right?
are going to wind up going backward in the topological ordering.
There's no where else they can go, this vertex is last.
that final position in the ordering are the sink vertices.
That's all that's going to work.
We put a non-sink vertex there, we're toast, it's not going to happen.
Fortunately, if it's directed acyclic, we know there is a sink vertex.
if there's many sink vertices, we pick one arbitrarily.
if there's n vertices we're going to put that in the nth position.
And now we just recurse on the rest of the graph, which has only n-1 vertices.
So how would this work in the example on the right?
the only sink vertex is this right most one, circled in green.
So there's four vertices, so we're going to give that the label 4.
we delete that vertex and all the edges incident to it.
that would be the left-most three vertices plus the left-most two edges.
So both this top vertex and this bottom vertex are sinks in the residual graph.
So now in the next recursive call, we can choose either of those as our sink vertex.
Because we have two choices, that generates two topological orderings.
Those are exactly the ones that we saw in the example.
we choose this one to be our sink vertex, then that gets the label 3.
Then we recurse just on the northwestern most two edges.
This vertex is the unique sink in that graph, that gets the label 2.
And then it recurs on the one node that we graph, and that gets the label 1.
So, why is this algorithm work?
Well, there's just two quick observations we need.
that we can assign in the final position that's still unfilled.
you're still going to have a directed acyclic graph, right?
You can't create cycles by just getting rid of stuff.
You can only destroy cycles, and we started with no cycles.
our first observation is always the sink.
it goes forward in the ordering.
That is the head of the arc is given a position later than the tail of the arc.
And this simply follows because we always use sink vertices.
So consider the vertex v which is assigned to the position i.
v is the sink vertex.
what property does it have in the original graph?
to go to vertices that were already deleted and assigned higher positions.
it's a sink and it only has incoming arcs from the as yet unsigned vertices.
positions, and got deleted previously from the graph.
computing a topological ordering of a directed acyclic graph.
then of course there's no way there's a topological ordering.
a cycle, it guarantees the topological ordering does indeed exist.
constructive argument, that gives an algorithm.
populating the ordering from right to left, as you keep peeling off these sinks.
and actually if you implement it just so, you can even get it to run in linear time.
of a topological ordering of a directed acyclic graph.
components of an undirected graph.
single vertex a label, we'd better look at every vertex at least once.
have multiple components, we'll just make sure to invoke DFS as often as we need to.
this will make sure that every node gets a label.
And in fact, these labels will define a topological order.
So let's not forget the code for depth first search.
acyclic graph, and you're given a start vertex, S.
Of course, you don't visit any vertex you've already been to.
You keep track of who you visited.
you immediately start recursing on that node.
loop to ensure that every single node gets labeled.
So I'm going to call that subroutine DFS-Loop.
It does not take a start vertex.
Initialization, all nodes start out on an explorative course.
and we're going to count down each time we finish exploring a new node.
And these will be precisely the f values.
in the topological ordering that we output.
In the main loop we're going to iterate over all of the nodes of the graph.
So for example, we just do a scan through the node array.
been explored in some previous invocation of DFS, we don't search from it.
loop when we computed the connected components of an undirected graph.
then we just invoke DFS in the graph, with that vertex as the starting point.
what the actual assignments of vertices to positions are.
And as I foreshadowed, we're going to use this global current_label variable.
And that'll have us assign vertices to positions from right to the left.
where we plucked off sink vertices one at a time.
So, when's the right time to assign a vertex its position?
the right time is when we've completely finished with that vertex.
f (s) = to whatever the current_label is and then we decrement the current_label.
And that's it, that is the entire algorithm.
it will get some integer assignment at the end.
the smallest one is 1.
The claim is that is a topological ordering.
with just a trivial amount of extra bookkeeping.
Lets see how it works on our running example.
we initialize the current label variable to be equal to 4.
let's say we start somewhere like the vertex v.
loop, we wind up considering the vertices in a totally arbitrary order.
So let's say we first call DFS from this vertex v.
which is n, and here, n is the number of vertices, which is 4.
So f(t) is going to get, so our t is going to get the assignment, the label 4.
So then now we're done with t, we backtrack back to v.
now there's no more outgoing arcs to explore, so for loops finish.
So we're done with it in depth-first search.
having finished with v, we decrement the current label, which is now down to 2.
maybe the next vertex we consider is the vertex t.
But we've already been there, so we don't bother to DFS on t.
And then maybe after that, we try it on s.
So maybe s is the third vertex that the for loop considers.
We haven't seen s yet, so we invoke DFS, starting from the vertex s.
nothing's going to happen with the arc sv.
But on the other hand, the arc sW will cause us to recursively call DFS on w.
w gets the assignment of the current label.
We decrement current label, now its value is 1.
It gets the current label, which is 1.
that we exhibited a couple slides ago.
how it works in a concrete example.
So, as far as the running time of this algorithm the running time is linear.
It's exactly what you'd want it to be.
the usual reasons that these search algorithms run in linear time.
each of the n nodes.
when you visit the tail of that edge.
So you only do a constant amount of work per edge as well.
Of course, the other key property is correctness.
That is, we need to show that you are guaranteed to get a topological ordering.
That means every arc travels forward in the ordering.
to u in this algorithm is less than the label assigned to v.
depending on which of the vertices u or v is visited first by depth-first search.
depth-first search is going to be invoked exactly once from each of the vertices.
Either u or v could be first, both are possible.
So first let's assume that u was visited by DFS before v, so then what happens?
it's going to find everything findable from that node.
it's a candidate for being discovered.
certainly DFS invoked at u is going to discover v.
finish, it's going to get popped off the program stack before that of u.
u's call is not going to get popped off the stack until v's does beforehand.
that means it will be assigned a larger label than u.
more recursive calls get popped off the stack.
Now, what's up in the second case, case two?
So this is where v is visited before u.
And here's where we use the fact that the graph has no cycles.
So there's a direct arc from u to v.
That means there cannot be any directed path from v all the way back to u.
That would create a directed cycle.
Therefore, DFS invoked from v is not going to discover u.
there'd be a directed cycle.
So it doesn't find u at all.
u's is even pushed onto the stack.
So we're totally done with v before we even start to consider u.
its label is going to be larger, which is exactly what we wanted to prove.
the strongly connected components of a directed graph.
This time, we can't do it in one depth-first search, we'll need two.

References: v.

 v.

 v.

 v.

 v.

 v.

 v.