# Topological Sorting

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

• a linear ordering of all vertices in a DAG G such that if G contains edge (u, v), then u appears before v in the ordering

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?

• topological sort depends on a partial ordering of the vertices.

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?

2. CBAED
3. ABCDE
4. 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

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

• The ordering of values in a set depends on a binary relation R being defined on the values in the set.

• Binary Relation:
• R on 2 sets A and B is a subset of the Cartesian product of A and B, or R | A X B
• R on 1 set A is a subset of the Cartesian product of A with itself, or R | A X A

Example: Let R be the less than relation on N (Natural numbers), then:
R = {(a, b): a, b ∈ N where a < b}

• Common Properties of Relations:
• Reflexive - R | A X A is reflexive if ∀a ∈ A, a R a

Example: for N,  = or ≤ are reflexive, but not > or <

A={a,b,c} R={(a,a),(b,b),(c,c)} is reflexive.

• Symmetric - R | A X A is reflexive if ∀a, b ∈ A, a R b  implies  b R a

Example: for N, = is symmetric, but not < or ≤

A={a,b,c} R={(a,b),(b,b),(b,a)} is symmetric.

• Transitive - R | A X A is transitive if ∀a, b, c  ∈ A, a R b  and  b R c  implies  a R c

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.

• Antisymmetric - R | A X A is antisymmetric if ∀a, b ∈ A, a R b  and  b R a  implies a = b

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.

• Partial Ordering Relation
• a relation R on the set A, where R has the properties: reflexive, transitive and antisymmetric, and A is said to be a partially ordered set

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

• Total Ordering Relation
• a partial ordering relation R is said to be a total ordering if ∀a, b ∈ A then either  a R b  holds, or  b R a  holds.  That is all pairings of the elements in A are related by R.

Example: for N, ≤ is a total ordering

1 ≤ 2 ≤ 3 ≤ 4 ...

• Maximal Element in Partially Ordered Sets
• Is an element a such that ∀b ∈ A, b R a holds.  Think of R being ≤, then a would greater than or equal to all other elements b in A.
• There may be no single "maximum" element in A, as for N with ≤
• There may be multiple maximal elements in A, as for the professor example with undershorts and socks.