{"id":574,"date":"2018-07-19T11:14:39","date_gmt":"2018-07-19T11:14:39","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=574"},"modified":"2018-12-21T10:22:03","modified_gmt":"2018-12-21T10:22:03","slug":"topological-sorting","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/topological-sorting\/","title":{"rendered":"Topological sorting"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will discuss about Topological Sorting.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\n\u2022 To understand the concept of Topological Sorting\r\n\r\n\u2022 To discuss some applications of Topological Sorting\r\n\r\n\u2022 To Illustrate Topological Sorting using a walkthrough example\r\n\r\n \r\n\r\n37.1 Topological Sort<\/strong>\r\n\r\n \r\n

We have a set of tasks<\/strong> and a set of dependencies (precedence constraints)<\/strong> of form \u201ctask A must be done before task B\u201d.<\/p>\r\n \r\n\r\nTopological sort<\/strong>: An ordering of the tasks that conforms to the given dependencies.\r\n\r\n \r\n\r\nGoal<\/strong>: Find a topological sort of the tasks or decide that there is no such ordering\r\n\r\n \r\n\r\n37.2 Recap of Graph Fundamentals<\/strong>\r\n\r\n \r\n\r\n37.2.1 Digraphs<\/strong>\r\n\r\n \r\n

A digraph is a graph whose edges are all directed. It is a shortened representation of \u201cdirected graph\u201d. Some of the applications of digraphs are representation of the following One-way streets, Flights, Task Scheduling as graphs.<\/p>\r\n \r\n\r\n37.2.2 Digraph Application<\/strong>\r\n\r\n \r\n

Scheduling is a typical example of a digraph. Edge (a,b) means that task a must be completed before task b can start. Consider the following graph given in Figure 37.1. The first task that has to be done is ics21 as it does not have any predecessors. Next, we can proceed in sequence to ics22, ics23 and then proceed onto ics161 and end with\u00a0good life. Or, after ics23, we can do ics52 and ics53 in parallel. Please note that, in order to do ics53, we have to do ics21, ics22 as well as ics23. Similarly, ics51 can be done after ics21. It does not have to wait for ics22 or ics23 as there are no edges from these two to ics51. Another order is ics131 after ics21 as there is an edge from ics21 to ics131. Similarly ics151 can be done after ics51. But ics53 ends there. There are various possible moves from ics21 such as ics131 or ics51 or icsics22. But to reach ics53, ics21, ics22, ics23 and ics51 have to be finished.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n37.2.3 Reachability<\/strong>\r\n\r\n \r\n

Consider the example given in Figure 37.2. The list of vertices reachable from any node via directed paths is called reachability.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Consider node C. The nodes reachable from C are E, A and D. That is, from C we can go to E directly or to A and D through E (Figure 37.2).<\/p>\r\n \r\n

Similarly, from B, the nodes reachable are: C, E, A, D and F. While B has direct connectivity to A, C, D and F, E can be reached through C. This is shown in Figure 37.3.<\/p>\r\n\r\n<\/div>\r\n\"\"<\/strong>\r\n

\r\n\r\n \r\n\r\n37.3 DAGs and Topological Ordering<\/strong>\r\n\r\n \r\n

A directed acyclic graph (DAG) is a digraph that has no directed cycles. Figure 37.4 is an example of a DAG and its topological ordering.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

A\u00a0 topological ordering of a digraph is a numbering v<\/em><\/strong>1 , \u2026, v<\/em><\/strong>n<\/em><\/strong> of the vertices such that for every edge (v<\/em>i<\/em> , v<\/em>j<\/em>), we have i<\/em> < j.<\/em> That is i has to be done before j. Example: In a task scheduling digraph, a topological ordering is a task sequence that satisfies the precedence constraints. A digraph admits a topological ordering if and only if it is a DAG. One of the topological ordering for the DAG G, is shown in Figure 37.4.<\/p>\r\n \r\n

Initial node can be A or B. Only after A and B are done can we move to C. Only after C and B are done can we move to D. After D is done we can move to E. So, the ordering here is: A,B,C,D and E.<\/p>\r\n \r\n\r\n37.4 Topological Sorting<\/strong>\r\n\r\n \r\n

Now let us consider an example of Topological sorting for a typical student day graph which is given in Figure 37.5.<\/p>\r\n\r\n<\/div>\r\n\"\"<\/strong>\r\n

\r\n

The first node to be traversed is wake-up. After that, study computer sci.. Then , we can either do eat or nap (in any order). Only after eat and nap, we can do more c.s. There are 3 things to be done before \u201cwrite a c.s. program\u201d: play, more c.s. and work out. Play and work out can be done only after \u201cmore c.s.\u201d. But, after \u201cmore c.s.\u201d, play and work out can be done in any order. Once \u201cwrite a c.s. program is over, \u201cmake cookies for professors\u201d, sleep and then \u201cdream about graphs\u201d can be done in that order. For a directed acyclic graph (DAG) G = (V,E), a topological sort is a linear ordering of all of G\u2019s vertices v1, v2, \u2026, vn such that:<\/p>\r\n \r\n\r\nFormally: for every edge (vi,vk) in E<\/em>, i<k.\r\n\r\nVisually: all arrows are pointing to the right.\r\n\r\nA real-world example for this is getting dressed.\r\n\r\n \r\n\r\n37.4.1 Examples<\/strong>\r\n\r\n \r\n

One of the major applications of topological sorting is scheduling where graphs are used to represent the order of tasks. When scheduling task graphs in 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). Another application is during compilation to order the modules\/libraries. Consider the graph given in Figure 37.6. In the graph given at the side, we can either start with d or c. Let us assume that we start with c. After c, we can proceed to d. After d, we can do a, g and f. After this, we can do b followed by e.<\/p>\r\n\r\n<\/div>\r\n\u00a0<\/strong>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n

Let us consider another example of getting dressed. The dependencies and the topological ordering is shown in Figure 37.7.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

The topological ordering may be as follows: we start with Socks, Underwear, Pants, Shoes, then, Shirt, Belt, Tie and Jacket and then Watch. Note that here, the node Watch is independent.<\/p>\r\n \r\n\r\n37.5 Topological sorting for cyclic graphs?<\/strong>\r\n\r\n\"\"\r\n

The topological sorting for cyclic graphs is impossible. Let us consider two vertices v and w on a cycle, there exists paths from v to w and<\/em> from w to v. Consider the cyclic\u00a0graph (Figure 37.8). To do 1, we have to do 2. To do 2, we have to do 3. To do 3, we have to do 1. Any ordering will contradict one of these paths .<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n37.6 Topological sort more formally<\/strong>\r\n\r\n \r\n

Is it possible to execute all the tasks in G<\/strong> in an order that respects all the precedence requirements given by the graph edges? The answer is \"yes<\/strong>\" if and only if<\/em> the directed graph G<\/strong> has no cycle<\/strong>! (Otherwise we have a deadlock<\/strong>).<\/p>\r\n \r\n\r\n37.6.1 Topological sort<\/strong>\r\n\r\n \r\n

Topological sort can be defined as the linearly ordering of the vertices so that the lineorder respects the ordering relations implied by the arcs.<\/p>\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

Considering the graph shown in Figure 37.9, the following topological orderings are possible:0,1,2,5,9, and 0,4,5,9 , but 0,6,3,7 is not possible because there is no edge between 3 and 7. There are often many possible topological sorts of a given DAG. Consider the following DAG (Figure 37.10)<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\nThe Topological orders for this DAG are as follows:1,2,5,4,3,6,7 2,1,5,4,7,3,6,2,5,1,4,7,3,6 etc.. Each topological order is a feasible schedule.\r\n\r\n<\/div>\r\n

\r\n

Let us consider the following problem of Getting Ready: A - waking up, B - taking a<\/em> shower, C - eating breakfast and D leaving for work<\/em><\/p>\r\n \r\n\r\nThe constraints would be A before B, A before C, B before D, and C before D\r\n\r\n \r\n

We can model dependencies (or constraints) like these using a Directed Acyclic<\/em><\/strong> Graph. <\/em><\/strong>Given a set of items and constraints, we create the corresponding graph. In this graph each item corresponds to a vertex in the graph and for each constraint where item A must finish before item B, we place a directed edge A \u00e0 B. Following these rules, the DAG would be as shown in<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\nA topological sort would give A, B, C, D.\r\n\r\n \r\n

Another example for topological sort is items of clothing to wear. The items are shown in Figure 37.12.<\/p>\r\n\"\"\r\n\r\nThere is no exact one order to put these items on, but we must adhere to certain restrictions:\r\n