Topological Sorting

Overview

Topological sorting is useful for defining the order things must be done. For example, prerequisites must be completed prior to certain course.

A 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?
• How many valid ways could you order courses starting with C201 to C343?
• How many valid ways could you order courses starting with C201 to B490?

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
   
• 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?

1. ADEBC
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 where once a has been put on, you won't have to take a off in order to put on b and if b is put on before a, then you would have to take b off in order to correctly put on a}

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 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 largest 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 can our professor (according to the sort) put on his pants?
• When can 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. At Line 5, visit 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
p	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.p ¬ 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.p ¬ 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 <

  • 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 ≤ 

  • 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

  • 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

• 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
     
• 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.