Relations, Functions, and MatricesTopological SortingAlgorithm: Topological SortingExample: Topological SortingSlide 5Example: PERT ChartSlide 7Exercise: PERT ChartRelations, Functions, and MatricesMathematical Structures for Computer ScienceChapter 4Copyright © 2006 W.H. Freeman & Co. MSCS Slides Relations, Functions and MatricesSection 4.2 Topological Sorting 2Topological SortingTopological sorting finds a total ordering  from a partial ordering  on a finite set that is an extension of , meaning that if x  y, then x  y . This is indeed a sorting process in the sense that the objects end up being totally ordered, but since they must be partially ordered to begin with, it is a very specialized sorting process.In a finite partially ordered set, an element is minimal if it has no predecessors. In a finite nonempty partially ordered set, at least one minimal element must exist. To see this, let x belong to the set. If x is not minimal, then there is a y in the set with y  x, y  x. If y is not minimal, then there is a z in the set with z  y, z  y, and so on. Because the set is finite, this process cannot go on indefinitely, so one such element must be minimal. A minimal element in a Hasse diagram has no elements below it.Section 4.2 Topological Sorting 3Algorithm: Topological SortingTopSort(finite set S; partial ordering on S) //find a total ordering on S that is an extension of  Local variable integer i //enumerates tasks in total ordering i = 1 while S =  pick a minimal element xi from S; S = S  {xi} i = i 1 end while //x1 < x2 < x3 < … < xn is now a total ordering of  that extends write(x1, x2, x3, …, xn) end function TopSortSection 4.2 Topological Sorting 4Example: Topological SortingErnie and his brothers run a woodworking shop in the hills of New Hampshire that manufactures rocking chairs with padded cushion seats. The manufacturing process can be broken down into a number of tasks, some of which have certain other tasks as prerequisites. The following table shows the manufacturing tasks for a rocking chair, the prerequisite tasks, and the number of hours required to perform each task.Section 4.2 Topological Sorting 5Example: Topological SortingWe can define a partial ordering on the set of tasks by x  y  task x = task y or task x is a prerequisite to task y. Quite obviously, this relation is reflexive, antisymmetric, and transitive. Also, x  y  task x is a prerequisite to task y.Also, x < y  task x is a prerequisite to task y.In the Hasse diagram for this partial ordering, the nodes are tasks. Add to each node the information about the time to perform the task. Orient the diagram so that, if x < y, then x is to the left of y rather than below y. Thus, the entire diagram runs from left to right rather than from bottom to top. Such a diagram for task scheduling is often called a PERT (program evaluation and review technique) chart.Section 4.2 Topological Sorting 6Example: PERT ChartThe PERT chart for manufacturing rocking chairs is shown below.With task numbers substituted for task names and arrows pointing to a task from its prerequisite task(s). The numbers in parentheses indicate the time required to perform the task.Section 4.2 Topological Sorting 7Example: Topological SortingOne topological sort of the partial ordering of this manufacturing example is 6, 1, 7, 2, 3, 5, 4, 8, 10, 9, 11, 12.In the figure on the previous slide, either 6 or 1 is minimal and may be chosen as the first element. If 6 is chosen and removed from the set, then, as shown in the figure (a), either 1 or 7 is minimal. If 1 is then chosen and removed from the set (figure (b)), then 2, 3, 4, 5, and 7 are all minimal and any one can be chosen next. The process continues until all nodes have been chosen. If Ernie’s brothers all move to the city and he is left to build rocking chairs alone, the topological sort gives an order in which he can perform tasks sequentially.(a) (b)Section 4.2 Topological Sorting 8Exercise: PERT ChartConstruct the PERT chart for building a house from the following task