Topological Sorting

  

 

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:

• Only directed acyclic graphs can have linear extensions, since any directed cycle is an inherent   contradiction to a linear order of tasks.
• Every DAG can be topologically sorted, so there must always be at least one schedule for any reasonable precedence constraints among jobs.
• DAGs typically allow many such schedules, especially when there are few constraints. Consider n jobs without any constraints. Any of the n! permutations of the jobs constitutes a valid linear extension.

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:

• What if I need all the linear extensions, instead of just one of them? - In certain applications, it is important to construct all linear extensions of a DAG. Beware, because the number of linear extensions can grow exponentially in the size of the graph. Even the problem of counting the number of linear extensions is NP-hard.

  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.

• What if your graph is not acyclic? - When the set of constraints is not a DAG, but it contains some inherent contradictions in the form of cycles, the natural problem becomes to find the smallest set of jobs or constraints that if eliminated leaves a DAG.   These smallest sets of offending jobs (vertices) or constraints (edges) are known as the feedback vertex set and the feedback arc set, respectively, and are discussed in Section . Unfortunately, both of them are NP-complete problems.

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