12 - A small scale study – topological sorting

Summary

Topological sorting is a classical example in the study of data structures and is often included within introductory programming courses in Computer Science at tertiary level. We shall use the problem to illustrate how a well-defined (and hence mathematical but not necessarily numerical) problem can yield a specification which, after appropriate transformation, gives rise to non-recursive PDL code and subsequently to a procedural program in a high-level language.

Although programs in procedural language are in effect algorithms, recall that the aim of this text is not the development of algorithms per se; and hence the algorithm which emerges at the end of the chapter is a consequence of the way in which we transform the problem specification. Other transformations would imply different algorithms. No value judgements are offered as to the quality of the resultant algorithm but it must be said that many years of programming experience will have had some effect on the way that the specification has been interpreted and subsequently transformed.

Problem formulation

In mathematical terminology the problem may be stated as: To find a linear ordering which is consistent with a given (necessarily acyclic) binary relation on a finite set'. Now whilst this may be fine for a (modern) Mathematician and should also be intelligible to any Computer Scientist who has attended a discrete mathematics course as part of his studies, it does not immediately suggest how we might formulate a proper specification of the process in terms of the fundamental entities at our disposal.