next up previous contents index CD CD Algorithms
Next: Minimum Spanning Tree Up: Graph Problems: Polynomial-Time Previous: Connected Components

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 tex2html_wrap_inline28605 , 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:

Implementations: Many textbooks contain implementations of topological sorting, including [MS91] (see Section gif) and [Sed92] (see Section gif).     LEDA (see Section gif) includes a linear-time implementation of topological sorting in C++.

XTango (see Section gif) 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 gif.

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 gif), feedback edge/vertex set (see page gif).    

next up previous contents index CD CD Algorithms
Next: Minimum Spanning Tree Up: Graph Problems: Polynomial-Time Previous: Connected Components

Mon Jun 2 23:33:50 EDT 1997