In graph theory, a topological sort of a directed acyclic graph (DAG) is a linear ordering of its nodes which is compatible with the partial order R induced on the nodes where x comes before y (xRy) if there's a directed path from x to y in the DAG. An equivalent definition is that each node comes before all nodes to which it has edges. Every DAG has at least one topological sort, and may have many. A labeled graph with 6 vertices and 7 edges. ... A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ...

Examples

The canonical application of topological sorting is in scheduling a sequence of jobs. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be done. Then, a topological sort gives an order in which to perform the jobs. This has applications in computer science, such as in instruction scheduling, ordering of formula cell evaluation in spreadsheets, dependencies in makefiles, and symbol dependencies in linkers. In computer science, instruction scheduling is a compiler optimization used to improve instruction-level parallelism, which improves performance on machines with instruction pipelines. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... make is a computer program that automates the compilation of programs whose files are dependent on each other. ...

The graph shown to the left has many valid topological sorts, including: 7,5,3,11,8,2,9,10 7,5,11,2,3,10,8,9 3,7,8,5,11,10,9,2

Image File history File links A directed acyclic graph, created by Derrick Coetzee in Illustrator and Photoshop. ...

Algorithms

The usual algorithm for topological sorting has running time linear in the number of nodes plus the number of edges (Θ(|V|+|E|)). First, find a list of "start nodes" which have no incoming edges and insert them into a queue Q. Then, The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... In providing services to people, and in computer science, transport and operations research a queue is a First-In-First-Out (FIFO) process â€” the first element in the queue will be the first one out. ...

 Q ← Set of all nodes with no incoming edges while graph has edges or Q is non-empty do if Q is empty then output error message (all remaining edges are part of a cycle) remove a node n from Q output n for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into Q 

If this algorithm terminates without outputting all the nodes of the graph, it means the graph has at least one cycle and therefore is not a DAG, so a topological sort is impossible; in this case, the algorithm may report a precise error by taking advantage of the fact that all remaining edges at this point are part of such a cycle.

Note that, reflecting the non-uniqueness of the resulting sort, the structure Q need not be a queue. It may be a stack (corresponding to depth-first search) or simply a set. Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...

Another algorithm for topological sort is to run depth-first search to find the last element. This element is then recorded and removed. Then we can use backtracking and find the second-to-last element. Continue in this way until all elements are found. Since each node and vertex is visited, the algorithm runs in O(edges+vertices) time.

External links

• NIST Dictionary of Algorithms and Data Structure: topological sort

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press and McGraw-Hill.
  • First Edition, 1990. ISBN 0070131430. Section 23.4: Topological sort, pp.485–488.
  • Second Edition, 2001. ISBN 0262032937. 2001. Section 22.4: Topological sort, pp.549–552.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...