Topological sorting

Any DAG has at least one topological ordering, and there are linear time algorithms for constructing it.

Topological sorting has many applications, especially in ranking problems such as feedback arc set.

The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies.

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.

Topological sorting forms the basis of linear-time algorithms for finding the 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, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers.

It is also used to decide in which order to load tables with foreign keys in databases.

One of these algorithms, first described by Kahn (1962), works by choosing vertices in the same order as the eventual topological sort.

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.

An alternative algorithm for topological sorting is based on depth-first search.

[4] On a parallel random-access machine, a topological ordering can be constructed in O((log n)2) time using a polynomial number of processors, putting the problem into the complexity class NC2.

The resulting matrix describes the longest path distances in the graph.

Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering.

In the following, it is assumed that the graph partition is stored on p processing elements (PE), which are labeled

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 is calculated over the sizes of

Below is a high level, single program, multiple data pseudo-code overview of this algorithm.

As for runtime, on a CRCW-PRAM model that allows fetch-and-decrement in constant time, this algorithm runs in

[7] The topological ordering can also be used to quickly compute shortest paths through a weighted directed acyclic graph.

Then the following algorithm computes the shortest path from some source vertex s to all other vertices:[3] Equivalently: On a graph of n vertices and m edges, this algorithm takes Θ(n + m), i.e., linear, time.

[3] 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 DAG.

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).

One can define a partial ordering from any DAG by letting the set of objects be the vertices of the DAG, and defining x ≤ 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 reachable from x.

Conversely, any partial ordering may be defined as the reachability relation in a DAG.

An alternative way of doing this is to use the 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 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).