Input description: A directed acyclic graph G=(V,E), also known as a partial order or poset.
Problem description: Find a linear ordering of the vertices of V such that for each edge , vertex i is to the left of vertex j.
Discussion: Topological sorting arises as a natural subproblem in most algorithms on directed acyclic graphs. Topological sorting orders the vertices and edges of a DAG in a simple and consistent way and hence plays the same role for DAGs that depth-first search does for general graphs.
Topological sorting can be used to schedule tasks under precedence constraints. Suppose we have a set of tasks to do, but certain tasks have to be performed before other tasks. These precedence constraints form a directed acyclic graph, and any topological sort (also known as a linear extension) defines an order to do these tasks such that each is performed only after all of its constraints are satisfied.
Three important facts about topological sorting are:
A linear extension of a given DAG is easily found in linear time. The basic algorithm performs a depth-first search of the DAG to identify the complete set of source vertices, where source vertices are vertices without incoming edges. At least one such source must exist in any DAG. Note that source vertices can appear at the start of any schedule without violating any constraints. After deleting all the outgoing edges of the source vertices, we will create new source vertices, which can sit comfortably to the immediate right of the first set. We repeat until all vertices have been accounted for. Only a modest amount of care with data structures (adjacency lists and queues) is needed to make this run in O(n+m) time.
This algorithm is simple enough that you should be able to code up your own implementation and expect good performance, although implementations are described below. Two special considerations are:
Algorithms for listing all linear extensions in a DAG are based on backtracking. They build all possible orderings from left to right, where each of the in-degree zero vertices are candidates for the next vertex. The outgoing edges from the selected vertex are deleted before moving on. Constructing truly random linear extensions is a hard problem, but pseudorandom orders can be constructed from left to right by selecting randomly among the in-degree zero vertices.
Since the basic topological sorting algorithm will get stuck as soon as it identifies a vertex on a directed cycle, we can delete the offending edge or vertex and continue. This quick-and-dirty heuristic will eventually leave a DAG.
Implementations: Many textbooks contain implementations of topological sorting, including [MS91] (see Section ) and [Sed92] (see Section ). LEDA (see Section ) includes a linear-time implementation of topological sorting in C++.
XTango (see Section ) is an algorithm animation system for UNIX and X-windows, which includes an animation of topological sorting.
Combinatorica [Ski90] provides Mathematica implementations of topological sorting and other operations on directed acyclic graphs. See Section .
Notes: Good expositions on topological sorting include [CLR90, Man89]. Brightwell and Winkler [BW91] proved that it is #P-complete to count the number of linear extensions of a partial order. The complexity class #P includes NP, so any #P-complete problem is at least NP-hard.
Related Problems: Sorting (see page ), feedback edge/vertex set (see page ).