Talk:Topological sorting

Relation to linear extension?

This article currently contains this sentence:

Topological orderings are also closely related to the concept of a linear extension of a partial order in mathematics.

Well, duhh, of course, that's obvious. The question is: how do topological orderings differ from linear extensions? Is there any difference at all? Perhaps topological sorting is defined only for finite sets/dags/orders, while linear extensions are more general, defined for infinite sets/dags/orders? Is there anything else, besides this finite/countable divide? 67.198.37.16 (talk) 17:25, 26 February 2018 (UTC)

Topological orderings are derived from directed acyclic graphs. Linear extensions are derived from partially ordered sets. Those are two different kinds of objects, and are not even in a one-to-one relation with each other (many different DAGs might correspond to a single partial order). I don't think finiteness or generality comes into it. But also it's a disciplinary divide: if you talk to a computer scientist, they will probably know what topological sorting is but not what a linear extension is, and if you talk to a mathematician it's the opposite. —David Eppstein (talk) 17:37, 26 February 2018 (UTC)

Relationship to topology?

The name "topological sorting" strongly suggests a connection with the mathematical subject of topology; yet such a connection is neither acknowledged nor disclaimed anywhere in the article. (Nor, for that matter, is it addressed in the topology article.) I would appreciate it if somebody who understands the origin of the term "topological sorting" (in particular, whether it has anything to do with topology) could shed some light on this, preferably in the text of the article. — Preceding unsigned comment added by 198.0.200.174 (talk • contribs)

See http://cstheory.stackexchange.com/questions/30659/why-is-topological-sorting-topological — the likely origin is in the meaning of "topology" that refers to the connectivity structure of a network, not to topology as a branch of mathematics. But without a reliable source we can't add anything to the article, and cstheory.stackexchange.com is not a reliable source. —David Eppstein (talk) 02:40, 20 March 2015 (UTC)

"Graph topology" refers to the connectivity of a graph, just as geometric topology refers to the connectivity of manifolds and solids. A topological sort takes a partial ordering and generates a total ordering such that all the arrows still point in one direction, so in a sense it is a total ordering embedding that preserves the (ordered) topology of the graph. — Preceding unsigned comment added by 66.60.126.246 (talk) 02:27, 15 June 2018 (UTC)