Question? Leave a message!




Topological sort

Topological sort
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 © 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... 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/mansfield&otkunc/Paper/03-02-04.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 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 11.4.5.1 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 11.4.5.1 Example Let’s step through this algorithm with this example – Which task can we start with?