Sorting without transitivity
staschuk at telusplanet.net
Sun Apr 20 18:37:26 CEST 2003
Quoth Michael Hudson:
> Do you (or anyone else) know why it's called a *topological* sort?
Not really. Knuth says: "The problem of topological sorting is to
embed the partial order in a linear order." [TAoCP, 2.2.3.]
> Don't see no topology here, off hand.
> It could be that the open subsets of a topological space are a poset
> under inclusion, I guess.
Hm... poset == partially ordered set?
Certainly inclusion is a partial order of subsets, and a
topological sort finds an inclusion-preserving map from any space
S to a space T in which inclusion satisfies the trichotomy
condition. Is that what topologists mean by "embed S in T"?
Steven Taschuk Aral: "Confusion to the enemy, boy."
staschuk at telusplanet.net Mark: "Turn-about is fair play, sir."
-- _Mirror Dance_, Lois McMaster Bujold
More information about the Python-list