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.

up vote 13 down vote accepted

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
  • 9
    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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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