3 ?/FONT> 5 ?/FONT> 1 ?/FONT> 2 ?/FONT> 4 ?/FONT> 6 ?/FONT> 8 ?/FONT> 7
For such a diagram, it seems clear what would be meant by a listing or ranking of the eight objects that is consistent with the given partial order. Such a ranking would be 3, 5, 1, 2, 4, 6, 8, 7. No other ranking would be consistent with the given partial order. This can be generalized to any partial order by interpreting the arrows as constraints on the ordering of objects in a ranking. For example, an arrow from 3 to 5 would mean that 3 must be ranked higher than 5. Then, a ranking consistent with a partial order would mean a ranking of the n objects that violates no constraints (that is, a ranking that violates no arrows or pairs).
Example 11.5
Consider the partial order on the set of nine integers represented by Figure 11.2. n
The ranking 2, 3, 4, 5, 6, 7, 8, 9, 10 would not be consistent with this partial order, because it violates at least one of the constraints?/FONT>namely, that 6 be ranked higher than 3, or that 10 be ranked higher than 2. This diagram actually represents the "is divided evenly by but is not equal to" relation introduced earlier.
The definition of topological sorting can now be stated more formally than at the outset of the chapter. A topological sort is a ranking of the n objects of S that is consistent with the given partial order. Let us try to solve the following topological sorting problem.
Example 11.6
Given a partial order on a set S of n objects, produce a topological sort of the n objects, if one exists. If no such ranking exists, then print out a message saying that none exists.* n
* If a relation is asymmetric and transitive but not irreflexive, then one can eliminate all pairs of the form (x, x) from the relation or, equivalently, erase all self-loops from its diagram. The resulting relation is a partial order, and it still makes sense to find a topological sort with respect to it. The topological sort then satisfies the constraints of the original relation involving distinct objects.
For simplicity assume that S is always the set of the first n integers 1, 2, 3, . . . , n, and that the partial order is given as m pairs of integers representing arrows in the corresponding diagram. Assume no pairs are replicated. For concreteness, take the input to have the following form:
This particular instance of the topological sorting problem will be referred to repeatedly throughout the chapter. Is there an obvious algorithm for this problem? Try to think of one before continuing.
Figure 11.2 A Partial Order on the Integers 2, . . . , 9
10 value of n
7 3
5 3
2 10
6 8
5 6 m = 9 pairs
4 8
7 1
4 2
7 6