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.


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.

  • $\begingroup$ I have access to this. I'll give it a read and ponder this and other answers. Thanks. $\endgroup$ Mar 2 '15 at 22:04
  • 10
    $\begingroup$ 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". $\endgroup$ Mar 3 '15 at 2:36
  • $\begingroup$ @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. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.