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.
$\begingroup$
$\endgroup$
0
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
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.
-
15$\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$ Commented Mar 3, 2015 at 2:36
-
1$\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$ Commented Mar 4, 2015 at 12:38
-
$\begingroup$ The term "network topology" refers to the graph structure in the connectivity of devices in the network, and graphs are naturally topological spaces. $\endgroup$ Commented Dec 26, 2021 at 20:02
$\begingroup$
$\endgroup$
Topology is the study of how "shapes" change when you apply continuous transformations to them. The central object of study is a topological space, which can be thought of as a way of saying which parts of an object are close to which other parts or how an object's pieces fit together. A graph (the kind with nodes and edges) is a topological space if you consider edges to be line segments from one vertex to another. You can ask questions like "How far away is this point from that one?" or "is this point between these other two points?".
In this light, a topological ordering could be viewed as a continuous (meaning "no cutting") function from the graph to $\mathbb{R}$ such that the restriction to each edge is monotonically increasing (with respect to the orders on $\mathbb{R}$ and the directedness of the edge), and such that no two vertices are mapped to the same point.
You're "continuously squishing the graph to a line" in a way that edges point forward, and then the nodes of the graph are ordered based on the order of the associated real number.
Edit: Note that this is probably not the origin of why the term "topological" was applied, but it is one sense in which topological sort is topological.
$\begingroup$
$\endgroup$
1
The word "topology" does not come from the mathematical field that often talks about doughnuts and coffee mugs. "Topology" just means a topologic study... that is, a study of the shape of something. You might recall topographic maps in geography class or you might be aware of the idea of 'network topology' which just generally means "the shape of a network." Network practitioners, for example, will talk about a "star topology" which simply is a network in a star shape, or a "ring topology" which simply means "in a ring shape." People can also refer to the topological landscape of a country, without really trying to refer to homeomorphisms, but instead the shape of the rivers and mountains.
Under the understanding that "topological" means "pertaining to shape", a "topological sort" simply means "a spacial sort."
It might be that the mathematical field of 'topology' is some student's first memorable encounter of the word that causes this kind of question to pop up regularly (I had a topologist once tell me he went to a networks conference because he saw a lot of mention of 'topology' and he felt that everyone was using the term incorrectly.) And I think that is why I have not yet had an algebraist ask me why "social groups" are called "groups" without even defining an operation on the elements.
-
$\begingroup$ I think I see your point--I edited my answer to hopefully clarify. I'd still argue that a great general way to formalize this notion of "shape" is with the tools of topology. I would consider even informal discussions about these sorts of "shapes of things" (e.g. counting a graph's cycles) to be topological, regardless of whether the people talking know about open sets. But it's often just one way to frame the discussion, made more or less relevant by context. As an analogy, 1st-graders aren't really learning CS when they learn long-addition, but I'd still say that they're doing an algorithm. $\endgroup$ Commented Jan 1, 2022 at 23:54
$\begingroup$
$\endgroup$
The topology of a set of items is how they are connected. Topological sorting is sorting items based only on their topology.
