Question? Leave a message!




Topological sort

Topological sort
ECE 250 Algorithms and Data Structures Topological sort Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Topological sort 2 Topological Sort In this topic, we will discuss: – Motivations – Review the definition of a directed acyclic graph (DAG) – Describe a topological sort and applications – Prove the existence of topological sorts on DAGs – Describe an abstract algorithm for a topological sort – Do a runtime and memory analysis of the algorithm – Describe a concrete algorithm – Define critical times and critical pathsTopological sort 3 11.4.1 Motivation Given a set of tasks with dependencies, is there an order in which we can complete the tasks Dependencies form a partial ordering – A partial ordering on a finite number of objects can be represented as a directed acyclic graph (DAG)Topological sort 4 11.4.1 Motivation Cycles in dependencies can cause issues... http://xkcd.com/754/Topological sort 5 11.4.2 Restriction of paths in DAGs In a DAG, given two different vertices v and v , j k there cannot both be a path from v to v and a path from v to v j k k j Proof: – Assume otherwise; thus there exists two paths: (v , v , v , v , … , v ) j 1,1 1,2 1,3 k (v , v , v , v , … , v ) k 2,1 2,2 2,3 j From this, we can construct the path (v , v , v , v , … , v , v , v , v , … , v ) j 1,1 1,2 1,3 k 2,1 2,2 2,3 j This a path is a cycle, but this is an acyclic graph ∴ contradictionTopological sort 6 11.4.3 Definition of topological sorting A topological sorting of the vertices in a DAG is an ordering v , v , v , …, v 1 2 3 V such that v appears before v if there is a path from v to v j k j kTopological sort 7 11.4.3 Definition of topological sorting Given this DAG, a topological sort is H, C, I, D, J, A, F, B, G, K, E, LTopological sort 8 11.4.3 Example For example, there are paths from H, C, I, D and J to F, so all these must come before F in a topological sort H, C, I, D, J, A, F, B, G, K, E, L Clearly, this sorting need not be uniqueTopological sort 9 11.4.3 Applications Consider the course instructor getting ready for a dinner out He must wear the following: – jacket, shirt, briefs, socks, tie, etc. There are certain constraints: – the pants really should go on after the briefs, – socks are put on before shoes http://www.idealliance.org/proceedings/xml03/slides/mansfieldotkunc/Paper/030204.htmlTopological sort 10 11.4.3 Applications The following is a task graph for getting dressed: One topological sort is: briefs, pants, wallet, keys, belt, socks, shoes, shirt, tie, jacket, iPod, watch A more reasonable topological sort is: briefs, socks, pants, shirt, belt, tie, jacket, wallet, keys, iPod, watch, shoesTopological sort 11 11.4.3 Applications C++ header and source files have include statements – A change to an included file requires a recompilation of the current file – On a large project, it is desirable to recompile only those source files that depended on those files which changed – For large software projects, full compilations may take hoursTopological sort 12 11.4.3 Applications The following is a DAG representing a number of tasks – The green arrows represent dependencies – The numbering indicates a topological sort of the tasks Ref: The Standard Task Graph http://www.kasahara.elec.waseda.ac.jp/schedule/Topological sort 13 11.4.4 Topological Sort Theorem: A graph is a DAG if and only if it has a topological sorting Proof strategy: Such a statement is of the form a ↔ b and this is equivalent to: a → b and b → aTopological sort 14 11.4.4 Topological Sort First, we need a two lemmas: – A DAG always has at least one vertex with indegree zero • That is, it has at least one source Proof: – If we cannot find a vertex with indegree zero, we will show there must be a cycle – Start with any vertex and define a list L = (v) – Then iterate this loop V times: • Given the list L, the first vertex ℓ does not have indegree zero 1 • Find any vertex w such that (w, ℓ ) is an edge 1 • Create a new list L = (w, ℓ , …, ℓ ) 1 k – By the pigeonhole principle, at least one vertex must appear twice • This forms a cycle; hence a contradiction, as this is a DAG ∴ we can always find a vertex with indegree zeroTopological sort 15 11.4.4 Topological Sort First, we need a two lemmas: – Any subgraph of a DAG is a DAG Proof: – If a subgraph has a cycle, that same cycle must appear in the super graph – We assumed the supergraph was a DAG – This is a contradiction ∴ the subgraph must be a DAGTopological sort 16 11.4.4 Topological Sort We will start with showing a → b: If a graph is a DAG, it has a topological sort By induction: A graph with one vertex is a DAG and it has a topological sort Assume a DAG with n vertices has a topological sort A DAG with n + 1 vertices must have at least one vertex v of indegree zero Removing the vertex v and consider the vertexinduced subgraph with the remaining n vertices – If this subgraph has a cycle, so would the original graph—contradiction – Thus, the graph with n vertices is also a DAG, therefore it has a topological sort Add the vertex v to the start of the topological sort to get one for the graph of size n + 1Topological sort 17 11.4.4 Topological Sort Next, we will show that b → a: If a graph has a topological ordering, it must be a DAG We will show this by showing the contrapositive: ¬a → ¬b: If a graph is not a DAG, it does not have a topological sort By definition, it has a cycle: (v , v , v , …, v , v ) 1 2 3 k 1 – In any topological sort, v must appear before v , because (v , v ) is a path 1 2 1 2 – However, there is also a path from v to v : (v , v , …, v , v ) 2 1 2 3 k 1 – Therefore, v must appear in the topological sort before v 2 1 This is a contradiction, therefore the graph cannot have a topological sort ∴ A graph is a DAG if and only if it has a topological sortingTopological sort 18 11.4.5 Topological Sort Idea: – Given a DAG V, make a copy W and iterate: • Find a vertex v in W with indegree zero • Let v be the next vertex in the topological sort • Continue iterating with the vertexinduced subgraph W \ vTopological sort 19 11.4.5.1 Example On this graph, iterate the following V = 12 times – Choose a vertex v that has indegree zero – Let v be the next vertex in our topological sort – Remove v and all edges connected to itTopological sort 20 11.4.5.1 Example Let’s step through this algorithm with this example – Which task can we start withTopological sort 21 11.4.5.1 Example Of Tasks C or H, choose Task CTopological sort 22 11.4.5.1 Example Having completed Task C, which vertices have indegree zero CTopological sort 23 11.4.5.1 Example Only Task H can be completed, so we choose it CTopological sort 24 11.4.5.1 Example Having removed H, what is next C, HTopological sort 25 11.4.5.1 Example Both Tasks D and I have indegree zero – Let us choose Task D C, HTopological sort 26 11.4.5.1 Example We remove Task D, and now C, H, DTopological sort 27 11.4.5.1 Example Both Tasks A and I have indegree zero – Let’s choose Task A C, H, DTopological sort 28 11.4.5.1 Example Having removed A, what now C, H, D, ATopological sort 29 11.4.5.1 Example Both Tasks B and I have indegree zero – Choose Task B C, H, D, ATopological sort 30 11.4.5.1 Example Removing Task B, we note that Task E still has an indegree of two – Next C, H, D, A, BTopological sort 31 11.4.5.1 Example As only Task I has indegree zero, we choose it C, H, D, A, BTopological sort 32 11.4.5.1 Example Having completed Task I, what now C, H, D, A, B, ITopological sort 33 11.4.5.1 Example Only Task J has indegree zero: choose it C, H, D, A, B, ITopological sort 34 11.4.5.1 Example Having completed Task J, what now C, H, D, A, B, I, JTopological sort 35 11.4.5.1 Example Only Task F can be completed, so choose it C, H, D, A, B, I, JTopological sort 36 11.4.5.1 Example What choices do we have now C, H, D, A, B, I, J, FTopological sort 37 11.4.5.1 Example We can perform Tasks G or K – Choose Task G C, H, D, A, B, I, J, FTopological sort 38 11.4.5.1 Example Having removed Task G from the graph, what next C, H, D, A, B, I, J, F, GTopological sort 39 11.4.5.1 Example Choosing between Tasks E and K, choose Task E C, H, D, A, B, I, J, F, GTopological sort 40 11.4.5.1 Example At this point, Task K is the only one that can be run C, H, D, A, B, I, J, F, G, ETopological sort 41 11.4.5.1 Example And now that both Tasks G and K are complete, we can complete Task L C, H, D, A, B, I, J, F, G, E, KTopological sort 42 11.4.5.1 Example There are no more vertices left C, H, D, A, B, I, J, F, G, E, K, LTopological sort 43 11.4.5.1 Example Thus, one possible topological sort would be: C, H, D, A, B, I, J, F, G, E, K, LTopological sort 44 11.4.5.1 Example Note that topological sorts need not be unique: C, H, D, A, B, I, J, F, G, E, K, L H, I, J, C, D, F, G, K, L, A, B, ETopological sort 45 11.4.6 Analysis What are the tools necessary for a topological sort – We must know and be able to update the indegrees of each of the vertices A 1 – We could do this with a table of the indegrees of B 1 each of the vertices C 0 – This requires Q(V) memory D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 L 2Topological sort 46 11.4.6 Analysis We must iterate at least V times, so the runtime must be W(V) A 1 B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 L 2Topological sort 47 11.4.6 Analysis We need to find vertices with indegree zero – We could loop through the array with each iteration 2 – The run time would be O(V ) A 1 B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 L 2Topological sort 48 11.4.6 Analysis What did we do with tree traversals – Use a queue (or other container) to temporarily store those vertices with indegree zero A 1 – Each time the indegree of a vertex is decremented to B 1 zero, push it onto the queue C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 L 2Topological sort 49 11.4.6 Analysis What are the run times associated with the queue – Initially, we must scan through each of the vertices: Q(V) – For each vertex, we will have to push onto and pop off the A 1 queue once, also Q(V) B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 L 2Topological sort 50 11.4.6 Analysis Finally, each value in the indegree table is associated with an edge – Here, E = 16 A 1 – Each of the indegrees must be decremented to zero B 1 – The run time of these operations is W(E) C 0 2 – If we are using an adjacency matrix:Q(V ) D 2 – If we are using an adjacency list:Q(E) E 4 F 2 G 1 H 0 I 1 J 1 K 1 L 2 + 16Topological sort 51 11.4.6 Analysis Therefore, the run time of a topological sort is: Q(V + E) if we use an adjacency list 2 Q(V ) if we use an adjacency matrix A 1 and the memory requirements is Q(V) B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 L 2Topological sort 52 11.4.6 Analysis What happens if at some step, all remaining vertices have an indegree greater than zero – There must be at least one cycle within that subset of A 1 vertices B 1 C 0 Consequence: we now have an Q(V + E) algorithm D 2 for determining if a graph has a cycle E 4 F 2 G 1 H 0 I 1 J 1 K 1 L 2Topological sort 53 11.4.7 Implementation Thus, to implement a topological sort: – Allocate memory for and initialize an array of indegrees – Create a queue and initialize it with all vertices that have indegree zero While the queue is not empty: – Pop a vertex from the queue – Decrement the indegree of each neighbor – Those neighbors whose indegree was decremented to zero are pushed onto the queueTopological sort 54 11.4.7 Implementation We will, however, use a trick with our queue – Initialization Type arrayvertexsize(); int ihead = 0, itail = 1; – Testing if empty: ihead == itail + 1 – For push ++itail; arrayitail = next vertex; – For pop Type currenttop = arrayihead; ++ihead;Topological sort 55 11.4.7 Implementation Because we place each vertex into the queue exactly once – We must never resize the array – We do not have to worry about the queue cycling Most importantly, however, because of the properties of a queue – When we finish, the underlying array stores the topological sortTopological sort 56 Example With the previous example, we initialize: – The array of indegrees – The queue A 1 B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 Queue: L 2 The queue is emptyTopological sort 57 Example Stepping through the table, push all source vertices into the queue A 1 B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 Queue: L 2 The queue is emptyTopological sort 58 Example Stepping through the table, push all source vertices into the queue A 1 B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 Queue: C H L 2 The queue is emptyTopological sort 59 Example Pop the front of the queue A 1 B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 Queue: C H L 2Topological sort 60 Example Pop the front of the queue – C has one neighbor: D A 1 B 1 C 0 D 2 E 4 F 2 G 1 H 0 I 1 J 1 K 1 Queue: C H L 2Topological sort 61 Example Pop the front of the queue – C has one neighbor: D – Decrement its indegree A 1 B 1 C 0 D 1 E 4 F 2 G 1 H 0 I 1 J 1 K 1 Queue: C H L 2Topological sort 62 Example Pop the front of the queue A 1 B 1 C 0 D 1 E 4 F 2 G 1 H 0 I 1 J 1 K 1 Queue: C H L 2Topological sort 63 Example Pop the front of the queue – H has two neighbors: D and I A 1 B 1 C 0 D 1 E 4 F 2 G 1 H 0 I 1 J 1 K 1 Queue: C H L 2Topological sort 64 Example Pop the front of the queue – H has two neighbors: D and I – Decrement their indegrees A 1 B 1 C 0 D 0 E 4 F 2 G 1 H 0 I 0 J 1 K 1 Queue: C H L 2Topological sort 65 Example Pop the front of the queue – H has two neighbors: D and I – Decrement their indegrees A 1 • Both are decremented to zero, so push them onto the queue B 1 C 0 D 0 E 4 F 2 G 1 H 0 I 0 J 1 K 1 Queue: C H L 2Topological sort 66 Example Pop the front of the queue – H has two neighbors: D and I – Decrement their indegrees A 1 • Both are decremented to zero, so push them onto the queue B 1 C 0 D 0 E 4 F 2 G 1 H 0 I 0 J 1 K 1 Queue: C H D I L 2Topological sort 67 Example Pop the front of the queue A 1 B 1 C 0 D 0 E 4 F 2 G 1 H 0 I 0 J 1 K 1 Queue: C H D I L 2Topological sort 68 Example Pop the front of the queue – D has three neighbors: A, E and F A 1 B 1 C 0 D 0 E 4 F 2 G 1 H 0 I 0 J 1 K 1 Queue: C H D I L 2Topological sort 69 Example Pop the front of the queue – D has three neighbors: A, E and F – Decrement their indegrees A 0 B 1 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 1 K 1 Queue: C H D I L 2Topological sort 70 Example Pop the front of the queue – D has three neighbors: A, E and F – Decrement their indegrees A 0 • A is decremented to zero, so push it onto the queue B 1 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 1 K 1 Queue: C H D I A L 2Topological sort 71 Example Pop the front of the queue A 0 B 1 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 1 K 1 Queue: C H D I A L 2Topological sort 72 Example Pop the front of the queue – I has one neighbor: J A 0 B 1 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 1 K 1 Queue: C H D I A L 2Topological sort 73 Example Pop the front of the queue – I has one neighbor: J – Decrement its indegree A 0 B 1 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A L 2Topological sort 74 Example Pop the front of the queue – I has one neighbor: J – Decrement its indegree A 0 • J is decremented to zero, so push it onto the queue B 1 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J L 2Topological sort 75 Example Pop the front of the queue A 0 B 1 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J L 2Topological sort 76 Example Pop the front of the queue – A has one neighbor: B A 0 B 1 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J L 2Topological sort 77 Example Pop the front of the queue – A has one neighbor: B – Decrement its indegree A 0 B 0 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J L 2Topological sort 78 Example Pop the front of the queue – A has one neighbor: B – Decrement its indegree A 0 • B is decremented to zero, so push it onto the queue B 0 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B L 2Topological sort 79 Example Pop the front of the queue A 0 B 0 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B L 2Topological sort 80 Example Pop the front of the queue – J has one neighbor: F A 0 B 0 C 0 D 0 E 3 F 1 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B L 2Topological sort 81 Example Pop the front of the queue – J has one neighbor: F – Decrement its indegree A 0 B 0 C 0 D 0 E 3 F 0 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B L 2Topological sort 82 Example Pop the front of the queue – J has one neighbor: F – Decrement its indegree A 0 • F is decremented to zero, so push it onto the queue B 0 C 0 D 0 E 3 F 0 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B F L 2Topological sort 83 Example Pop the front of the queue A 0 B 0 C 0 D 0 E 3 F 0 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B F L 2Topological sort 84 Example Pop the front of the queue – B has one neighbor: E A 0 B 0 C 0 D 0 E 3 F 0 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B F L 2Topological sort 85 Example Pop the front of the queue – B has one neighbor: E – Decrement its indegree A 0 B 0 C 0 D 0 E 2 F 0 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B F L 2Topological sort 86 Example Pop the front of the queue A 0 B 0 C 0 D 0 E 2 F 0 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B F L 2Topological sort 87 Example Pop the front of the queue – F has three neighbors: E, G and K A 0 B 0 C 0 D 0 E 2 F 0 G 1 H 0 I 0 J 0 K 1 Queue: C H D I A J B F L 2Topological sort 88 Example Pop the front of the queue – F has three neighbors: E, G and K – Decrement their indegrees A 0 B 0 C 0 D 0 E 1 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F L 2Topological sort 89 Example Pop the front of the queue – F has three neighbors: E, G and K – Decrement their indegrees A 0 • G and K are decremented to zero, B 0 so push them onto the queue C 0 D 0 E 1 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K L 2Topological sort 90 Example Pop the front of the queue A 0 B 0 C 0 D 0 E 1 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K L 2Topological sort 91 Example Pop the front of the queue – G has two neighbors: E and L A 0 B 0 C 0 D 0 E 1 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K L 2Topological sort 92 Example Pop the front of the queue – G has two neighbors: E and L – Decrement their indegrees A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K L 1Topological sort 93 Example Pop the front of the queue – G has two neighbors: E and L – Decrement their indegrees A 0 • E is decremented to zero, so push it onto the queue B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L 1Topological sort 94 Example Pop the front of the queue A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L 1Topological sort 95 Example Pop the front of the queue – K has one neighbors: L A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L 1Topological sort 96 Example Pop the front of the queue – K has one neighbors: L – Decrement its indegree A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L 0Topological sort 97 Example Pop the front of the queue – K has one neighbors: L – Decrement its indegree A 0 • L is decremented to zero, so push it onto the queue B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L L 0Topological sort 98 Example Pop the front of the queue A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L L 0Topological sort 99 Example Pop the front of the queue – E has no neighbors—it is a sink A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L L 0Topological sort 100 Example Pop the front of the queue A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L L 0Topological sort 101 Example Pop the front of the queue – L has no neighbors—it is also a sink A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L L 0Topological sort 102 Example The queue is empty, so we are done A 0 B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 Queue: C H D I A J B F G K E L L 0Topological sort 103 Example We deallocate the memory for the temporary indegree array A 0 The array stores the topological sorting B 0 C 0 D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 C H D I A J B F G K E L L 0Topological sort 104 Example We deallocate the memory for the temporary indegree array A 0 The array used for the queue stores the topological sort B 0 – Note the difference in order from our previous sort C 0 C, H, D, A, B, I, J, F, G, E, K, L D 0 E 0 F 0 G 0 H 0 I 0 J 0 K 0 C H D I A J B F G K E L L 0Topological sort 105 11.4.8 Critical path Suppose each task has a performance time associated with it – If the tasks are performed serially, the time required to complete the last task equals to the sum of the individual task times – These tasks require 0.3 + 0.7 + 0.5 + 0.4 + 0.1 = 2.0 s to execute seriallyTopological sort 106 11.4.8 Critical path Suppose two tasks are ready to execute – We could perform these tasks in parallel – Computer tasks can be executed in parallel (multiprocessing) – Different tasks can be completed by different teams in a companyTopological sort 107 11.4.8 Critical path Suppose Task A completes – We can now execute Tasks B and D in parallel – However, Task E cannot execute until Task C completes, and Task C cannot execute until Task B completes • The least time in which these five tasks can be completed is 0.3 + 0.5 + 0.4 + 0.1 = 1.3 s • This is called the critical time of all tasks • The path (A, B, C, E) is said to be the critical pathTopological sort 108 11.4.8 Critical path The program described previously shows the critical path in red – We will define the critical time of each task to be the earliest time that it could be completed after the start of execution Ref: The Standard Task Graph http://www.kasahara.elec.waseda.ac.jp/schedule/Topological sort 109 11.4.8 Finding the critical path Tasks that have no prerequisites have a critical time equal to the time it takes to complete that task For tasks that depend on others, the critical time will be: – The maximum critical time that it takes to complete a prerequisite – Plus the time it takes to complete this task In this example, the critical times are: – Task A completes in 0.3 s – Task B must wait for A and completes after 0.8 s – Task D must wait for A and completes after 1.0 s – Task C must wait for B and completes after 1.2 s – Task E must wait for both C and D, and completes after max(1.0, 1.2) + 0.1 = 1.3 sTopological sort 110 11.4.8.1 Finding the critical path Thus, we require more information: – We must know the execution time of each task – We will have to record the critical time for each task • Initialize these to zero – We will need to know the previous task with the longest critical time to determine the critical path • Set these to nullTopological sort 111 11.4.8.2 Finding the critical path Suppose we have the following times for the tasks In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 0.0 Ø B 1 6.1 0.0 Ø C 3 4.7 0.0 Ø D 3 8.1 0.0 Ø E 2 9.5 0.0 Queue Ø F 0 17.1 0.0Topological sort 112 11.4.8.2 Finding the critical path Each time we pop a vertex v, in addition to what we already do: – For v, add the task time onto the critical time for that vertex: • That is the critical time for v – For each adjacent vertex w: • If the critical time for v is greater than the currently stored critical time for w – Update the critical time with the critical time for v – Set the previous pointer to the vertex vTopological sort 113 11.4.8.2 Finding the critical path So we initialize the queue with those vertices with indegree zero In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 0.0 Ø B 1 6.1 0.0 Ø C 3 4.7 0.0 Ø D 3 8.1 0.0 Ø E 2 9.5 0.0 Queue Ø F 0 17.1 0.0 A FTopological sort 114 11.4.8.2 Finding the critical path Pop Task A and update its critical time 0.0 + 5.2 = 5.2 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 0.0 Ø B 1 6.1 0.0 Ø C 3 4.7 0.0 Ø D 3 8.1 0.0 Ø E 2 9.5 0.0 Queue Ø F 0 17.1 0.0 FTopological sort 115 11.4.8.2 Finding the critical path Pop Task A and update its critical time 0.0 + 5.2 = 5.2 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 Ø B 1 6.1 0.0 Ø C 3 4.7 0.0 Ø D 3 8.1 0.0 Ø E 2 9.5 0.0 Queue Ø F 0 17.1 0.0 FTopological sort 116 11.4.8.2 Finding the critical path For each neighbor of Task A: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 Ø B 1 6.1 0.0 Ø C 3 4.7 0.0 Ø D 3 8.1 0.0 Ø E 2 9.5 0.0 Queue Ø F 0 17.1 0.0 FTopological sort 117 11.4.8.2 Finding the critical path For each neighbor of Task A: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 5.2 A Ø C 3 4.7 0.0 D 2 8.1 5.2 A Ø E 2 9.5 0.0 Queue Ø F 0 17.1 0.0 F BTopological sort 118 11.4.8.2 Finding the critical path Pop Task F and update its critical time 0.0 + 17.1 = 17.1 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 5.2 A Ø C 3 4.7 0.0 D 2 8.1 5.2 A Ø E 2 9.5 0.0 Queue Ø F 0 17.1 0.0 BTopological sort 119 11.4.8.2 Finding the critical path Pop Task F and update its critical time 0.0 + 17.1 = 17.1 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 5.2 A Ø C 3 4.7 0.0 D 2 8.1 5.2 A Ø E 2 9.5 0.0 Queue Ø F 0 17.1 17.1 BTopological sort 120 11.4.8.2 Finding the critical path For each neighbor of Task F: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 5.2 A Ø C 3 4.7 0.0 D 2 8.1 5.2 A Ø E 2 9.5 0.0 Queue Ø F 0 17.1 17.1 BTopological sort 121 11.4.8.2 Finding the critical path For each neighbor of Task F: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 5.2 A C 2 4.7 17.1 F D 2 8.1 5.2 A E 1 9.5 17.1 F Queue Ø F 0 17.1 17.1 BTopological sort 122 11.4.8.2 Finding the critical path Pop Task B and update its critical time 5.2 + 6.1 = 11.3 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 5.2 A C 2 4.7 17.1 F D 2 8.1 5.2 A E 1 9.5 17.1 F Queue Ø F 0 17.1 17.1Topological sort 123 11.4.8.2 Finding the critical path Pop Task B and update its critical time 5.2 + 6.1 = 11.3 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 2 4.7 17.1 F D 2 8.1 5.2 A E 1 9.5 17.1 F Queue Ø F 0 17.1 17.1Topological sort 124 11.4.8.2 Finding the critical path For each neighbor of Task B: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 2 4.7 17.1 F D 2 8.1 5.2 A E 1 9.5 17.1 F Queue Ø F 0 17.1 17.1Topological sort 125 11.4.8.2 Finding the critical path For each neighbor of Task F: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task – Both C and E are waiting on F Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 1 4.7 17.1 F D 1 8.1 11.3 B E 0 9.5 17.1 F Queue Ø F 0 17.1 17.1 ETopological sort 126 11.4.8.2 Finding the critical path Pop Task E and update its critical time 17.1 + 9.5 = 26.6 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 1 4.7 17.1 F D 1 8.1 11.3 B E 0 9.5 17.1 F Queue Ø F 0 17.1 17.1Topological sort 127 11.4.8.2 Finding the critical path Pop Task E and update its critical time 17.1 + 9.5 = 26.6 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 1 4.7 17.1 F D 1 8.1 11.3 B E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1Topological sort 128 11.4.8.2 Finding the critical path For each neighbor of Task E: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 1 4.7 17.1 F D 1 8.1 11.3 B E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1Topological sort 129 11.4.8.2 Finding the critical path For each neighbor of Task E: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 26.6 E D 1 8.1 11.3 B E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1 CTopological sort 130 11.4.8.2 Finding the critical path Pop Task C and update its critical time 26.6 + 4.7 = 31.3 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 26.6 E D 1 8.1 11.3 B E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1Topological sort 131 11.4.8.2 Finding the critical path Pop Task C and update its critical time 26.6 + 4.7 = 31.3 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 31.3 E D 1 8.1 11.3 B E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1Topological sort 132 11.4.8.2 Finding the critical path For each neighbor of Task C: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 31.3 E D 1 8.1 11.3 B E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1Topological sort 133 11.4.8.2 Finding the critical path For each neighbor of Task C: – Decrement the indegree, push if necessary, and check if we must update the critical time In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 31.3 E D 0 8.1 31.3 C E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1 DTopological sort 134 11.4.8.2 Finding the critical path Pop Task D and update its critical time 31.3 + 8.1 = 39.4 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 31.3 E D 0 8.1 31.3 C E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1Topological sort 135 11.4.8.2 Finding the critical path Pop Task D and update its critical time 31.3 + 8.1 = 39.4 In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 31.3 E D 0 8.1 39.4 C E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1Topological sort 136 11.4.8.2 Finding the critical path Task D has no neighbors and the queue is empty – We are done In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 31.3 E D 0 8.1 39.4 C E 0 9.5 26.6 F Queue Ø F 0 17.1 17.1Topological sort 137 11.4.8.2 Finding the critical path Task D has no neighbors and the queue is empty – We are done In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 31.3 E D 0 8.1 39.4 C E 0 9.5 26.6 F Ø F 0 17.1 17.1Topological sort 138 11.4.8.2 Finding the critical path We can also plot the completing of the tasks tasks in time – We need to be able to execute two tasks in parallel for this example In Task Critical Previous Task Task degree Time Time Ø A 0 5.2 5.2 B 0 6.1 11.3 A C 0 4.7 31.3 E D 0 8.1 39.4 C E 0 9.5 26.6 F Ø F 0 17.1 17.1Topological sort 139 11.4.8.2 Finding the critical path Incidentally, the task and previous task defines a forest using the parental tree data structure Previous Task Task Ø A B A C E D C E F Ø FTopological sort 140 Summary In this topic, we have discussed topological sorts – Sorting of elements in a DAG – Implementation • A table of indegrees • Select that vertex which has current indegree zero – We defined critical paths • The implementation requires only a few more table entriesTopological sort 141 References Wikipedia, http://en.wikipedia.org/wiki/Topologicalsorting 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, §11.1, p.200. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §9.2, p.3425. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017