Topological Sort (an application of DFS)
CSC263 Tutorial 9
Topological sort
• Wehaveasetoftasksandasetofdependencies (precedence constraints) of form “task A must be done before task B”
• Topologicalsort:Anorderingofthetasksthat conforms with the given dependencies
• Goal: Find a topological sort of the tasks or decide that there is no such ordering
Examples
• Scheduling:Whenschedulingtaskgraphsin distributed systems, usually we first need to sort the tasks topologically
…and then assign them to resources (the most efficient scheduling is an NP-complete problem)
• Orduringcompilationtoordermodules/libraries dc
agf b
e
Examples
• Resolving dependencies: apt-get uses topological sorting to obtain the admissible sequence in which a set of Debian packages can be installed/removed
Topological sort more formally
• SupposethatinadirectedgraphG=(V,E) vertices V represent tasks, and each edge (u, v)∊E means that task u must be done before task v
• What is an ordering of vertices 1, …, |V| such that for every edge (u, v), u appears before v in the ordering?
• SuchanorderingiscalledatopologicalsortofG
• Note:therecanbemultipletopologicalsortsofG
Topological sort more formally
• IsitpossibletoexecuteallthetasksinGinanorder that respects all the precedence requirements given by the graph edges?
• Theansweris”yes”ifandonlyifthedirectedgraph G has no cycle!
(otherwise we have a deadlock)
• SuchaGiscalledaDirectedAcyclicGraph,orjusta DAG
Algorithm for TS • TOPOLOGICAL-SORT(G):
1) call DFS(G) to compute finishing times f[v] for each vertex v
2) as each vertex is finished, insert it onto the front of a linked list
3) return the linked list of vertices
• Note that the result is just a list of vertices in order of decreasing finish times f[]
Edge classification by DFS
Edge (u,v) of G is classified as a:
(1) Tree edge iff u discovers v during the DFS: P[v] = u
If (u,v) is NOT a tree edge then it is a:
(2) Forward edge iff u is an ancestor of v in the DFS tree (3) Back edge iff u is a descendant of v in the DFS tree
(4) Cross edge iff u is neither an ancestor nor a descendant of v
Tree edges
Forward edges
Back edges
a bc
Cross edges
Edge classification by DFS
c
The edge classification depends on the particular DFS tree!
Tree edges
Both are valid
Forward edges
Back edges
a b
a b
Cross edges
Edge classification by DFS
c
c
The edge classification depends on the particular DFS tree!
DAGs and back edges
• CantherebeabackedgeinaDFSonaDAG?
• NO! Back edges close a cycle!
• AgraphGisaDAG<=>thereisnobackedge classified by DFS(G)
Back to topological sort • TOPOLOGICAL-SORT(G):
1) call DFS(G) to compute finishing times f[v] for each vertex v
2) as each vertex is finished, insert it onto the front of a linked list
3) return the linked list of vertices
d=∞ f=∞
a
b c
d d = = ∞1 f = ∞
Next we discover the vertex d
d=∞ f=∞
Let’s say we start the DFS from the vertex c
Time = 12
Topological sort
d=∞ d=∞
f=∞ d
e f=∞
d=∞ f=∞
f
1)
Call DFS(G) to compute the finishing times f[v]
d=∞ f=∞
a
b c
d=1 f=∞
Next we discover the vertex d
d=∞ f=∞
Let’s say we start the DFS from the vertex c
d d = = 2∞
f = ∞ d
e
d = ∞ f = ∞
Time = 23
d=∞ f=∞
f
Topological sort
1)
Call DFS(G) to compute the finishing times f[v]
d=∞ f=∞
d=1 f=∞
linked list
Next we discover the vertex d
d=∞ f=∞
as each vertex is finished, Let’s say we start the DFS
d = 2
f=∞ d
d = ∞ e f=∞
Next we discover the vertex f f is done, move back to d
Time = 34
1) 2)
Call DFS(G) to compute the finishing times f[v]
a
b c
from the vertex c
insert it onto the front of a
d = 3 f f = = 4∞
f
Topological sort
f
d=∞ f=∞
a
b c
d=1 f=∞
Next we discover the vertex d Next we discover the vertex f
d=∞ f=∞
Let’s say we start the DFS from the vertex c
d = 2
f=5 d
d = ∞ e f=∞
f is done, move back to d d is done, move back to c
Time = 45
d=3 f=4
f
Topological sort
df
1)
Call DFS(G) to compute the finishing times f[v]
d=∞ f=∞
a
b c
d=1 f=∞
Next we discover the vertex d Next we discover the vertex f
d=∞ f=∞
Let’s say we start the DFS from the vertex c
d = 2
f=5 d
d = ∞ e f=∞
f is done, move back to d d is done, move back to c
Time = 65
d = 3 f=4
f
Next we discover the vertex e
Topological sort
df
1)
Call DFS(G) to compute the finishing times f[v]
d=∞ f=∞
a bc
d=1 f=∞
Next we discover the vertex d
d=∞ f=∞
Let’s say we start the DFS from the vertex c
d = 2 f = 5
d
e
d = 6 f = ∞
f is done, move back to d cross edges
Time = 76
d = 3 f=4
f
d is done, move back to c Next we discover the vertex e
Topological sort
edf
1)
Call DFS(G) to compute the finishing times f[v]
Next we discover the vertex f Both edges from e are
e is done, move back to c
d=∞ f=∞
a bc
d=1 f=∞
Just a note: If there was (c,f) Next we discover the vertex d
d=∞ f=∞
Let’s say we start the DFS from the vertex c
d = 2
f=5 d
d = 6 e f=7
classified as a forward edge f is done, move back to d
Time = 78
d = 3 f=4
f
Next we discover the vertex e e is done, move back to c
Topological sort
cedf
c is done as well
1)
Call DFS(G) to compute the finishing times f[v]
edge in the graph, it would be Next we discover the vertex f
(in this particular DFS run) d is done, move back to c
d=∞ f=∞
b
d=1 c f = 8
Next we discover the vertex c, but c was already processed => (a,c) is a cross edge
d d = = ∞9 f = ∞
a
Let’s now call DFS visit from the vertex a
TTimimee==190
Topological sort
d=2 d=6
Next we discover the vertex b
f=5 d d=3
e f=7
f f=4
cedf
1)
Call DFS(G) to compute the finishing times f[v]
d = 10 f = ∞11
d=1 c f = 8
Next we discover the vertex c, but c was already processed => (a,c) is a cross edge
d=9 f=∞
a
Let’s now call DFS visit from the vertex a
Time = 101
Topological sort
b
d=2 d=6
Next we discover the vertex b
f=5 d d=3
e f=7
f f=4
b is done as (b,d) is a cross edge => now move back to c
bcedf
1)
Call DFS(G) to compute the finishing times f[v]
d = 10 f = 11
d=1 c f = 8
Next we discover the vertex c, but c was already processed => (a,c) is a cross edge
d=9 f=∞
a
Let’s now call DFS visit from the vertex a
Time = 121
Topological sort
b
d=2 d=6
Next we discover the vertex b b is done as (b,d) is a cross
f=5 d d=3
e f=7
f f=4
edge => now move back to c a is done as well
bcedf
1)
Call DFS(G) to compute the finishing times f[v]
d = 10 f = 11
d=1 c f=8
Next we discover the vertex c, vertices
d=9 f = 12
Let’s now call DFS visit from
Time = 131
a
WE HAVE THE RESULT! the vertex a
Topological sort
b
d=2 d=6
but c was already processed => (a,c) is a cross edge
f=5 d d=3
e f=7
Next we discover the vertex b b is done as (b,d) is a cross
f f=4
edge => now move back to c a is done as well
abcedf
1)
Call DFS(G) to compute the finishing times f[v]
3)
return the linked list of
d = 10 f=11
a
b c
d=1 f=8
Try yourself with different vertex order for DFS visit
d = 9 f=12
Time = 131
The linked list is sorted in decreasing order of finishing times f[]
Topological sort
d=2 d=6
f = 5 d d=3
e f = 7
Note: If you redraw the graph so that all vertices are in a line ordered by a valid topological sort, then all edges point „from left to right“
f f=4
abcedf
Time complexity of TS(G) • Running time of topological sort:
Θ(n+m)
where n=|V| and m=|E|
• Why? Depth first search takes Θ(n + m) time in the worst case, and inserting into the front of a linked list takes Θ(1) time
Proof of correctness
• Theorem: TOPOLOGICAL-SORT(G) produces a
topological sort of a DAG G
• The TOPOLOGICAL-SORT(G) algorithm does a DFS on the DAG G, and it lists the nodes of G in order of decreasing finish times f[]
• We must show that this list satisfies the topological sort property, namely, that for every edge (u,v) of G, u appears before v in the list
• Claim: For every edge (u,v) of G: f[v] < f[u] in DFS
Proof of correctness
“For every edge (u,v) of G, f[v] < f[u] in this DFS”
• The DFS classifies (u,v) as a tree edge, a forward edge or a cross-edge (it cannot be a back-edge since G has no cycles):
i. If(u,v)isatreeoraforwardedge ⇒visa descendant of u ⇒ f[v] < f[u]
ii. If (u,v) is a cross-edge
Proof of correctness
“For every edge (u,v) of G: f[v] < f[u] in this DFS” Q.E.D. of Claim
ii. If (u,v) is a cross-edge:
• as (u,v) is a cross-edge, by definition, neither u
is a descendant of v nor v is a descendant of u: d[u] < f[u] < d[v] < f[v]
or
d[v] < f[v] < d[u] < f[u]
since (u,v) is an edge, v is surely discovered before u's exploration completes
f[v] < f[u]
Proof of correctness
• TOPOLOGICAL-SORT(G) lists the nodes of G from highest to lowest finishing times
• By the Claim, for every edge (u,v) of G: f[v] < f[u]
⇒ u will be before v in the algorithm's list • Q.E.D of Theorem