View source for Topological sorting

{{Short description|Node ordering for directed acyclic graphs}}
In [[Computer science|computer science]], a '''topological sort''' or '''topological ordering''' of a [[Directed graph|directed graph]] is a [[Total order|linear ordering]] of its [[Vertex (graph theory)|vertices]] such that for every directed edge ''(u,v)'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node ''v'' is visited only after all its dependencies are visited''.'' A topological ordering is possible if and only if the graph has no [[Directed cycle|directed cycle]]s, that is, if it is a [[Directed acyclic graph|directed acyclic graph]] (DAG). Any DAG has at least one topological ordering, and [[Algorithm|algorithm]]s are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications, especially in ranking problems such as [[Feedback arc set|feedback arc set]]. Topological sorting is possible even when the DAG has [[Connectivity (graph theory)|disconnected components]].

== Examples ==
[[Image:Directed acyclic graph 2.svg|thumb|upright=1.4|This graph has many valid topological sorts, including:

{{bulleted list | 5, 7, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
| 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
| 3, 5, 7, 8, 11, 2, 10, 9 ([[Coffman–Graham algorithm|lexicographic by incoming neighbors]])
| 5, 7, 3, 8, 11, 2, 10, 9 (fewest edges first)
| 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
| 5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)
| 3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)}}]]

The canonical application of topological sorting is in [[Job shop scheduling|scheduling]] a sequence of jobs or tasks based on their [[Dependency graph|dependencies]]. 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 started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer). Then, a topological sort gives an order in which to perform the jobs.  A closely-related application of topological sorting algorithms was first studied in the early 1960s in the context of the PERT technique for scheduling in [[Project management|project management]].{{r|Jarnagin}} In this application, the vertices of a graph represent the milestones of a project, and the edges represent tasks that must be performed between one milestone and another. Topological sorting forms the basis of linear-time algorithms for finding the [[Critical path method|critical path]] of the project, a sequence of milestones and tasks that controls the length of the overall project schedule.

In computer science, applications of this type arise in [[Instruction scheduling|instruction scheduling]], ordering of formula cell evaluation when recomputing formula values in [[Engineering:Spreadsheet|spreadsheet]]s, [[Logic synthesis|logic synthesis]], determining the order of compilation tasks to perform in [[Makefile|makefile]]s, data [[Serialization|serialization]], and resolving symbol dependencies in [[Linker (computing)|linkers]]. It is also used to decide in which order to load tables with foreign keys in databases.

== Algorithms ==
The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, <math>O(\left|{V}\right| + \left|{E}\right|).</math>

===Kahn's algorithm===
One of these algorithms, first described by {{harvp|Kahn|1962}}, works by choosing vertices in the same order as the eventual topological sort.{{r|Kahn}} First, find a list of "start nodes" that have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty acyclic graph. Then:

 ''L'' ← Empty list that will contain the sorted elements
 ''S'' ← Set of all nodes with no incoming edge
 
 '''while''' ''S'' '''is not''' empty '''do'''
     remove a node ''n'' from ''S''
     add ''n'' to ''L''
     '''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 ''S''
 
 '''if''' ''graph'' has edges '''then'''
     '''return''' error   ''(graph has at least one cycle)''
 '''else''' 
     '''return''' ''L''   ''(a topologically sorted order)''

If the graph is a [[Directed acyclic graph|DAG]], a solution will be contained in the list L (although the solution is not necessarily unique). Otherwise, the graph must have at least one cycle and therefore a topological sort is impossible.

Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created. A variation of Kahn's algorithm that breaks ties [[Lexicographic order|lexicographically]] forms a key component of the [[Coffman–Graham algorithm]] for parallel scheduling and [[Layered graph drawing|layered graph drawing]].

===Depth-first search===
An alternative algorithm for topological sorting is based on [[Depth-first search|depth-first search]]. The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e., a leaf node):

 ''L'' ← Empty list that will contain the sorted nodes
 '''while''' exists nodes without a permanent mark '''do'''
     select an unmarked node ''n''
     visit(''n'')
 
 '''function''' visit(node ''n'')
     '''if''' ''n'' has a permanent mark '''then'''
         '''return'''
     '''if''' ''n'' has a temporary mark '''then'''
         '''stop'''   ''(graph has at least one cycle)''
 
     mark ''n'' with a temporary mark
 
     '''for each''' node ''m'' with an edge from ''n'' to ''m'' '''do'''
         visit(''m'')
 
     remove temporary mark from ''n''
     mark ''n'' with a permanent mark
     add ''n'' to head of ''L''

Each node ''n'' gets ''prepended'' to the output list L only after considering all other nodes that depend on ''n'' (all descendants of ''n'' in the graph).  Specifically, when the algorithm adds node ''n'', we are guaranteed that all nodes that depend on ''n'' are already in the output list L: they were added to L either by the recursive call to visit() that ended before the call to visit ''n'', or by a call to visit() that started even before the call to visit ''n''.  Since each edge and node is visited once, the algorithm runs in linear time. This depth-first-search-based algorithm is the one described by {{harvp|Cormen|Leiserson|Rivest|Stein|2001}};{{r|CLRS}} it seems to have been first described in print by Tarjan in 1976.{{r|Tarjan}}

===Parallel algorithms===
On a [[Parallel random-access machine|parallel random-access machine]], a topological ordering can be constructed in ''O''((log ''n'')<sup>2</sup>) time using a polynomial number of processors, putting the problem into the complexity class '''[[NC (complexity)|NC]]<sup>2</sup>'''.{{r|Cook}}
One method for doing this is to repeatedly square the [[Adjacency matrix|adjacency matrix]] of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the [[Longest path problem|longest path]] distances in the graph. Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering.{{r|DNS}}

An algorithm for parallel topological sorting on [[Distributed memory|distributed memory]] machines parallelizes the algorithm of Kahn for a [[Directed acyclic graph|DAG]] <math>G = (V, E)</math>.{{r|SMDD}} On a high level, the algorithm of Kahn repeatedly removes the vertices of indegree 0 and adds them to the topological sorting in the order in which they were removed. Since the outgoing edges of the removed vertices are also removed, there will be a new set of vertices of indegree 0, where the procedure is repeated until no vertices are left. This algorithm performs <math>D+1</math> iterations, where {{mvar|D}} is the longest path in {{mvar|G}}. Each iteration can be parallelized, which is the idea of the following algorithm.

In the following, it is assumed that the graph partition is stored on {{mvar|p}} processing elements (PE), which are labeled <math>0, \dots, p-1</math>. Each PE {{mvar|i}} initializes a set of local vertices <math>Q_i^1</math> with indegree 0, where the upper index represents the current iteration. Since all vertices in the local sets <math>Q_0^1, \dots, Q_{p-1}^1</math> have indegree 0, i.e., they are not adjacent, they can be given in an arbitrary order for a valid topological sorting. To assign a global index to each vertex, a [[Prefix sum|prefix sum]] is calculated over the sizes of <math>Q_0^1, \dots, Q_{p-1}^1</math>. So, each step, there are <math display="inline">\sum_{i=0}^{p-1} |Q_i|</math> vertices added to the topological sorting.
[[File:Parallel_Topological_Sorting.gif|thumb|upright=1.35|Execution of the parallel topological sorting algorithm on a DAG with two processing elements.]]
In the first step, PE {{mvar|j}} assigns the indices <math display="inline">\sum_{i=0}^{j-1} |Q_i^1|, \dots, \left(\sum_{i=0}^{j} |Q_i^1|\right) - 1</math> to the local vertices in <math>Q_j^1</math>. These vertices in <math>Q_j^1</math> are removed, together with their corresponding outgoing edges. For each outgoing edge <math>(u, v)</math> with endpoint {{mvar|v}} in another PE <math>l, j \neq l</math>, the message <math>(u, v)</math> is posted to PE {{mvar|l}}. After all vertices in <math>Q_j^1</math> are removed, the posted messages are sent to their corresponding PE. Each message <math>(u, v)</math> received updates the indegree of the local vertex {{mvar|v}}. If the indegree drops to zero, {{mvar|v}} is added to <math>Q_j^2</math>. Then the next iteration starts.

In step {{mvar|k}}, PE {{mvar|j}} assigns the indices <math display="inline">a_{k-1} + \sum_{i=0}^{j-1} |Q_i^k|, \dots, a_{k-1} + \left(\sum_{i=0}^{j} |Q_i^k|\right) - 1</math>, where  <math>a_{k-1}</math>is the total number of processed vertices after step {{tmath|k-1}}. This procedure repeats until there are no vertices left to process, hence <math display="inline">\sum_{i=0}^{p-1} |Q_i^{D+1}| = 0</math>. Below is a high level, [[SPMD|single program, multiple data]] pseudo-code overview of this algorithm.

Note that the [[Prefix sum#Parallel algorithms|prefix sum]] for the local offsets <math display="inline">a_{k-1} + \sum_{i=0}^{j-1} |Q_i^k|, \dots, a_{k-1} + \left(\sum_{i=0}^{j} |Q_i^k|\right) - 1</math> can be efficiently calculated in parallel.
 '''p''' processing elements with IDs from 0 to ''p''-1
 '''Input:''' G = (V, E) DAG, distributed to PEs, PE index j = 0, ..., p - 1
 '''Output:''' topological sorting of G
 
 '''function''' traverseDAGDistributed
     δ incoming degree of local vertices ''V''
     {{math|1=''Q'' = {{mset|''v'' ∈ ''V'' | δ[''v''] {{=}} 0}}}}                     // All vertices with indegree 0
     nrOfVerticesProcessed = 0
 
     '''do'''                 
         '''global''' build prefix sum over size of ''Q''     // get offsets and total number of vertices in this step
         offset = nrOfVerticesProcessed + sum(Q<sub>i</sub>, i = 0 to j - 1)          // ''j'' is the processor index
         '''foreach''' u '''in''' Q                                       
             localOrder[u] = index++;
             '''foreach''' (u,v) in E '''do''' post message (''u, v'') to PE owning vertex ''v''
         nrOfVerticesProcessed += sum(|Q<sub>i</sub>|, i = 0 to p - 1)
         deliver all messages to neighbors of vertices in Q  
         receive messages for local vertices V
         remove all vertices in Q
         '''foreach''' message (''u, v'') received:
             '''if''' --δ[v] = 0
                 add ''v'' to ''Q''
     '''while''' global size of ''Q'' > 0
 
     '''return''' localOrder
The communication cost depends heavily on the given graph partition. As for runtime, on a CRCW-PRAM model that allows fetch-and-decrement in constant time, this algorithm runs in <math display="inline">\mathcal{O} \left(\frac{m + n}{p} + D (\Delta + \log n)\right)</math>, where {{mvar|D}} is again the longest path in {{mvar|G}} and {{mvar|Δ}} the maximum degree.{{r|SMDD}}

==Application to shortest path finding==
The topological ordering can also be used to quickly compute [[Shortest path problem|shortest paths]] through a weighted directed acyclic graph. Let {{mvar|V}} be the list of vertices in such a graph, in topological order. Then the following algorithm computes the shortest path from some source vertex {{mvar|s}} to all other vertices:{{r|CLRS}}

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Let {{mvar|d}} be an array of the same length as {{mvar|V}}; this will hold the shortest-path distances from {{mvar|s}}. Set {{math|1=''d''[''s''] = 0}}, all other {{math|1=''d''[''u''] = ∞}}.
* Let {{mvar|p}} be an array of the same length as {{mvar|V}}, with all elements initialized to {{mono|nil}}. Each {{math|''p''[''u'']}} will hold the predecessor of {{math|''u''}} in the shortest path from {{mvar|s}} to {{mvar|u}}.
* Loop over the vertices {{mvar|u}} as ordered in {{mvar|V}}, starting from {{mvar|s}}:
** For each vertex {{mvar|v}} directly following {{mvar|u}} (i.e., there exists an edge from {{mvar|u}} to {{mvar|v}}):
*** Let {{mvar|w}} be the weight of the edge from {{mvar|u}} to {{mvar|v}}.
*** Relax the edge: if {{math|''d''[''v''] > ''d''[''u''] + ''w''}}, set
**** {{math|''d''[''v''] ← ''d''[''u''] + ''w''}},
**** {{math|''p''[''v''] ← ''u''}}.
{{frame-footer}}
</div>

Equivalently:
<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Let {{mvar|d}} be an array of the same length as {{mvar|V}}; this will hold the shortest-path distances from {{mvar|s}}. Set {{math|1=''d''[''s''] = 0}}, all other {{math|1=''d''[''u''] = ∞}}.
* Let {{mvar|p}} be an array of the same length as {{mvar|V}}, with all elements initialized to {{mono|nil}}. Each {{math|''p''[''u'']}} will hold the predecessor of {{mvar|u}} in the shortest path from {{mvar|s}} to {{mvar|u}}.
* Loop over the vertices {{mvar|u}} as ordered in {{mvar|V}}, starting from {{mvar|s}}:
** For each vertex {{mvar|v}} into {{mvar|u}} (i.e., there exists an edge from {{mvar|v}} to {{mvar|u}}):
*** Let {{mvar|w}} be the weight of the edge from {{mvar|v}} to {{mvar|u}}.
*** Relax the edge: if {{math|''d''[''u''] > ''d''[''v''] + ''w''}}, set
**** {{math|''d''[''u''] ← ''d''[''v''] + ''w''}},
**** {{math|''p''[''u''] ← ''v''}}.
{{frame-footer}}
</div>

On a graph of {{mvar|n}} vertices and {{mvar|m}} edges, this algorithm takes {{math|Θ(''n'' + ''m'')}}, i.e., linear, time.{{r|CLRS}}

==Uniqueness==
If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed [[Hamiltonian path]] in the [[Directed acyclic graph|DAG]]. If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other. Therefore, it is possible to test in linear time whether a unique ordering exists, and whether a Hamiltonian path exists, despite the NP-hardness of the Hamiltonian path problem for more general directed graphs (i.e., cyclic directed graphs).{{r|VM}}

==Relation to partial orders==
Topological orderings are also closely related to the concept of a [[Linear extension|linear extension]] of a partial order in mathematics. A partially ordered set is just a set of objects together with a definition of the "≤" inequality relation, satisfying the axioms of reflexivity (''x''&nbsp;≤&nbsp;''x''), antisymmetry (if ''x''&nbsp;≤&nbsp;''y'' and ''y''&nbsp;≤&nbsp;''x'' then ''x''&nbsp;=&nbsp;''y'') and [[Transitive relation|transitivity]] (if ''x''&nbsp;≤&nbsp;''y'' and ''y''&nbsp;≤&nbsp;''z'', then ''x''&nbsp;≤&nbsp;''z''). A [[Total order|total order]] is a partial order in which, for every two objects ''x'' and ''y'' in the set, either ''x''&nbsp;≤&nbsp;''y'' or ''y''&nbsp;≤&nbsp;''x''. Total orders are familiar in computer science as the comparison operators needed to perform [[Comparison sort|comparison sort]]ing algorithms. For finite sets, total orders may be identified with linear sequences of objects, where the "≤" relation is true whenever the first object precedes the second object in the order; a comparison sorting algorithm may be used to convert a total order into a sequence in this way. A linear extension of a partial order is a total order that is compatible with it, in the sense that, if ''x''&nbsp;≤&nbsp;''y'' in the partial order, then  ''x''&nbsp;≤&nbsp;''y'' in the total order as well.

One can define a partial ordering from any DAG by letting the set of objects be the vertices of the DAG, and defining ''x''&nbsp;≤&nbsp;''y'' to be true, for any two vertices ''x'' and ''y'', whenever there exists a directed path from ''x'' to ''y''; that is,  whenever ''y'' is [[Reachability|reachable]] from ''x''. With these definitions, a topological ordering of the DAG is the same thing as a linear extension of this partial order. Conversely, any partial ordering may be defined as the reachability relation in a DAG. One way of doing this is to define a DAG that has a vertex for every object in the partially ordered set, and an edge ''xy'' for every pair of objects for which ''x''&nbsp;≤&nbsp;''y''. An alternative way of doing this is to use the [[Transitive reduction|transitive reduction]] of the partial ordering; in general, this produces DAGs with fewer edges, but the reachability relation in these DAGs is still the same partial order. By using these constructions, one can use topological ordering algorithms to find linear extensions of partial orders.

==Relation to scheduling optimisation==
By definition, the solution of a scheduling problem that includes a precedence graph is a valid solution to topological sort (irrespective of the number of machines), however, topological sort in itself is ''not'' enough to optimally solve a scheduling optimisation problem. Hu's algorithm is a popular method used to solve scheduling problems that require a precedence graph and involve processing times (where the goal is to minimise the largest completion time amongst all the jobs). Like topological sort, Hu's algorithm is not unique and can be solved using DFS (by finding the largest path length and then assigning the jobs). 
==See also==
* tsort, a Unix program for topological sorting
* [[Feedback arc set]], a set of edges whose removal allows the remaining subgraph to be topologically sorted
* [[Tarjan's strongly connected components algorithm]], an algorithm that gives the topologically sorted list of strongly connected components in a graph
* [[Pre-topological order]]

==References==
{{reflist|refs=

<ref name=Cook>{{citation
 | title = A Taxonomy of Problems with Fast Parallel Algorithms
 | journal = Information and Control | volume = 64 | issue = 1–3
 | year = 1985 | pages = 2–22
 | doi = 10.1016/S0019-9958(85)80041-3| doi-access = free}}</ref>

<ref name=CLRS>{{citation
 | contribution = Section 22.4: Topological sort
 | edition = 2nd
 | isbn = 0-262-03293-7
 | pages = 549–552
 | publisher = MIT Press and McGraw-Hill
 | title = Introduction to Algorithms
 | title-link = Introduction to Algorithms | year = 2001}}</ref>

<ref name=DNS>{{citation
 | last1 = Dekel | first1 = Eliezer
 | last2 = Nassimi | first2 = David
 | last3 = Sahni | first3 = Sartaj
 | doi = 10.1137/0210049
 | issue = 4
 | journal = SIAM Journal on Computing
 | mr = 635424
 | pages = 657–675
 | title = Parallel matrix and graph algorithms
 | volume = 10
 | year = 1981}}</ref>

<ref name=Jarnagin>{{citation
 | last = Jarnagin | first = M. P.
 | title = Automatic machine methods of testing PERT networks for consistency
 | year = 1960
 | series = Technical Memorandum No. K-24/60
 | publisher = U. S. Naval Weapons Laboratory
 | location = Dahlgren, Virginia}}</ref>

<ref name=Kahn>{{citation
 | last = Kahn | first = Arthur B.
 | title = Topological sorting of large networks
 | journal = Communications of the ACM
 | volume = 5 | issue = 11 | year = 1962 | pages = 558–562
 | doi = 10.1145/368996.369025| s2cid = 16728233| doi-access = free}}</ref>

<ref name=SMDD>{{citation|last1=Sanders|first1=Peter|url=https://www.springer.com/gp/book/9783030252083|title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox| last2=Mehlhorn| first2=Kurt|last3=Dietzfelbinger|first3=Martin| last4=Dementiev|first4=Roman|date=2019|publisher=Springer International Publishing|isbn=978-3-030-25208-3}}</ref>

<ref name=Tarjan>{{citation
 | title = Edge-disjoint spanning trees and depth-first search
 | journal = Acta Informatica | volume = 6 | issue = 2 | year = 1976 | pages = 171–185
 | doi = 10.1007/BF00268499| s2cid = 12044793 }}</ref>

<ref name=VM>{{citation
 | last1 = Vernet | first1 = Oswaldo
 | last2 = Markenzon | first2 = Lilian
 | contribution = Hamiltonian problems for reducible flowgraphs
 | title = Proceedings: 17th International Conference of the Chilean Computer Science Society
 | year = 1997
 | pages = 264–267
 | doi = 10.1109/SCCC.1997.637099| hdl = 11422/2585
 | s2cid = 206554481
 | contribution-url = http://pantheon.ufrj.br/bitstream/11422/2585/4/02_97_000575787.pdf
 | hdl-access = free }}</ref>

}}

==Further reading==
*D. E. Knuth, [[The Art of Computer Programming]], Volume 1, section 2.2.3, which gives an algorithm for topological sorting of a partial ordering, and a brief history.
*[[Biography:Bertrand Meyer|Bertrand Meyer]], ''Touch of Class: Learning to Program Well with Objects and Contracts'', Springer, 2099, chapter 15, ''Devising and engineering an algorithm: topological sort'', using a modern programming language, for a detailed pedagogical presentation of topological sort (using a variant of Kahn's algorithm) with consideration of data structure design, API design, and software engineering concerns.

== External links ==
* [https://xlinux.nist.gov/dads/HTML/topologicalSort.html NIST Dictionary of Algorithms and Data Structures: topological sort]
* {{MathWorld|urlname=TopologicalSort|title=Topological Sort|mode=cs2}}

{{sorting}}

[[Category:Graph algorithms]]
[[Category:Sorting algorithms]]

{{Sourceattribution|Topological sorting}}