Sorting without transitivity

Steven Taschuk staschuk at
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    Mark: "Turn-about is fair play, sir."
                             -- _Mirror Dance_, Lois McMaster Bujold

More information about the Python-list mailing list