# Why is “topological sorting” topological?

Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why is it not called "dependency sort" or something else? Why "topological"? I admit I'm mystified.

## 2 Answers

The earliest reference I could find for topological sort is from [Lasser61]:

A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal nodes and the nodes are assumed to be numbered by a non-topological system. Given a list of these lines in numeric order, a simple technique can be used to create at high speed a list in topological order.

I don't have access to this article right now but I would wager that the "topology" in "topological sort" does not come from the mathematical notion of topology (e.g.: open sets, compactness, etc...) but rather from the "network topology" sense.

[Lasser61] Lasser, Daniel J. "Topological ordering of a list of randomly-numbered elements of a network." Communications of the ACM 4, no. 4 (1961): 167-168.

• I have access to this. I'll give it a read and ponder this and other answers. Thanks. – PartialOrder Mar 2 '15 at 22:04
• Another hint that network topology rather than the mathematical meaning of topological is intended is that the term used in pure mathematics for almost the same idea (possibly first used by Dushnik and Miller 1941) is "linear extension" rather than "topological order". – David Eppstein Mar 3 '15 at 2:36
• @mhum It looks like the term may have originated with Jarnagin (1960) Automatic machine methods of testing PERT networks for consistency (note: "PERT networks"). There don't seem to be a lot of copies of this floating around but I'm going to request one via inter-library loan and see what it says. – PartialOrder Mar 4 '15 at 12:38

The topology of a set of items is how they are connected. Topological sorting is sorting items based only on their topology.