Topological Sorting |
Document last modified: |
Overview
Topological sorting is useful for defining the order things must be done. For example, prerequisites must be completed prior to certain other courses.
DAG (directed acyclic graph) can model the problem (what is a cycle?) and the DFS can produce a sort that defines one valid ordering of paths to follow.
Question 22.16
From this DAG could you reasonably convince yourself that C251 could be skipped?
Is C201 → C343 → C251 valid?
Topological sort
Question 22.16 continued
Must C201 and C251 be taken before C342?
How many valid ways could you order courses
starting with C201 to C343?
Totally ordered sets, all elements are ordered by a binary relation: e.g. 4 ≤ 5
Partially ordered sets, some elements are ordered by a binary relation: George Bush 43 descended from George Bush 41, but you probably did not.
See end of notes or text for formal definition.
Example
The following is a DAG at left that has been topologically sorted at right. It shows one valid ordering: DEABC.
Other valid orderings are possible from the DAG, for example: ADBEC
Question 22.17 - Which of the following are invalid orderings and why?
- ADEBC
- CBAED
- ABCDE
- DECAB
Example - Cormen page 613
A = {belt, jacket, pants, shirt, shoes, socks, tie, undershorts, watch}
R = {(a, b): a, b ∈ A
a R b = { if a is on, won't have to take a off to put on b }
R = {(belt, jacket), (tie, jacket), (shirt, belt), (pants, belt), (pants, shoes), (shirt, tie), (undershorts, pants), (undershorts, shoes), (socks, shoes)}
Topological-Sort (G) 1 call DFS (G) to compute the v.f for each vertex v 2 as each vertex is finished, insert it onto the front of a linked list.
The last finished is at the head of the list.3 return the linked list of vertices, which is sorted last to first finished Start with shirt.
Question 22.18
List the above items in topologically sorted order.
socks have the greatest finish time, 18, jacket the smallest. What can you say about the relationship between finish time and topological ordering?
Must the professor put on his socks and undershorts in that order? That is could the order be switched?
When must our professor (according to the sort) put on his pants?
When must our professor (according to the sort) put on his watch?
What is the complexity of the Topological-Sort algorithm?
Compute the DFS of the DAG at right. Visit vertices at each for in the order of C4, C1, C2, C3, C5.
Give a topological sort for the DAG at right. Are other sorts possible?
From the following DFS table, what is the topological order?
u v w x y z Π NIL u NIL y v w d 1 1 9 4 3 10 f 8 7 12 5 6 11
DFS (G) -- Initialize arrays 1 for each vertex u ∈ G.V do 2 u.color ← WHITE 3 u.Π ← NIL 4 time ← 0 5 for each vertex u ∈ G.V do 6 if u.color = WHITE then 7 DFS-Visit (G, u)
DFS-Visit (G, u) 1 u.color ← GRAY 2 time ← time + 1 3 u.d ← time 4 for each vertex v ∈ G.Adj[ u ] do 5 if v.color = WHITE then 6 v.Π ← u 7 DFS-Visit (G, v) 8 u.color ← BLACK 9 u.f ← time ← time + 1
Ordering of Values in Sets
Example: Let R be the less than relation on N (Natural numbers), then:
R = {(a, b): a, b ∈ N where a < b}
Example: for N, = or ≤ are reflexive, but not > or <
A={a,b,c} R={(a,a),(b,b),(c,c)} is reflexive.
Example: for N, = is symmetric, but not < or ≤
A={a,b,c} R={(a,b),(b,b),(b,a)} is symmetric.
Example: for N, =, ≤ , < are all transitive
a < b and b < c implies a < c
A={a,b,c} R={(a,b),(b,c),(a,c)} is transitive.
Example: for N, ≤ is antisymmetric, but not <
a ≤ b and b ≤ a implies a = b
A={a,b,c} R={(a,b),(b,c),(a,c),(a,a)} is antisymmetric.
A={a,b,c} R={(a,b),(b,c),(a,c),(a,a),(b,b),(c,c)} is reflexive, transitive and antisymmetric.
A = N (natural numbers) R = {(a,b) | a % b = 0} divisible is reflexive, transitive and antisymmetric.
The set of all positive divisors of 42, {1, 2, 3, 6, 7, 14, 21, 42}, partially ordered by divisibility
Example: for N, ≤ is a total ordering
1 ≤ 2 ≤ 3 ≤ 4 ...