Question? Leave a message!

Topological sort

Topological sort
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
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 © 2006-2013 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 run-time 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... 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 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 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 in-degree zero • That is, it has at least one source Proof: – If we cannot find a vertex with in-degree 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 in-degree zero 1 • Find any vertex w such that (w, ℓ ) is an edge 1 • Create a new list L = (w, ℓ , …, ℓ ) 1 k – By the pigeon-hole 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 in-degree zeroTopological sort 15 11.4.4 Topological Sort First, we need a two lemmas: – Any sub-graph of a DAG is a DAG Proof: – If a sub-graph has a cycle, that same cycle must appear in the super- graph – We assumed the super-graph was a DAG – This is a contradiction ∴ the sub-graph 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 in-degree zero Removing the vertex v and consider the vertex-induced sub-graph with the remaining n vertices – If this sub-graph 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 in-degree zero • Let v be the next vertex in the topological sort • Continue iterating with the vertex-induced sub-graph W \ vTopological sort 19 Example On this graph, iterate the following V = 12 times – Choose a vertex v that has in-degree zero – Let v be the next vertex in our topological sort – Remove v and all edges connected to itTopological sort 20 Example Let’s step through this algorithm with this example – Which task can we start with?