The procedure TopologicalSort attempts to produce a linear ordering of a collection of elements that is consistent with a specified partial ordering of those elements. This means that an element  precedes an element  in the partial order only if  precedes  in the linear order.

The partial order is specified as a ``relation'' rel, which is a list or set of pairs , each representing an ordering of the elements of the domain of the relation. A pair  belongs to the relation rel if  precedes  in the partial order it represents. The domain of the relation is the set of all expressions that occur as either a first or second entry (or both) in some pair in the relation rel.

Alternatively, you may think of the members of rel as directed edges in a graph whose vertices are the elements of the domain of the relation. In these terms, a topological sort of the vertices is a linear ordering of them such that a vertex  occurs before  in the linear order only if there is a directed path from  to  in the graph. The two characterizations are equivalent.

In general, there may be many linear orderings of the vertices of a graph that are consistent with it.  For example, the partial order  (indicating that  is "less than"  and  is "less than"  has two consistent linear orderings:  and . The TopologicalSort procedure produces one of them.

It is also possible that no linear ordering consistent with the given partial order exists. This is the case when the directed graph contains a cycle. If TopologicalSort detects a cycle in the graph, then an exception is raised. The simplest example of this is the relation , which clearly has no consistent linear order.

Error, (in TopologicalSort) graph is not acyclic