Sorting without transitivity

[Alex Martelli]

Frank Niessink wrote:

> Hi all,
> 
> [It's been while since I've dealt with transitivity and stuff, so
> I hope I got the terminology right]
> 
> I have objects that are not transitivily ordered, e.g.:
> 
> A > B
> A == C
> B == C
> 
> Now I have a list [A, B, C] and I want to sort it.
> The resulting list should have B before A, I don't care where
> C is. However, the Python list.sort() method (Python 2.2.2 on cygwin)
> doesn't put A and B in the right order.

I think what you want is what's known as a *topological
sort* -- a sort obtaining any ordering that respect certain
given pairwise constraints that don't, however, define a
complete order.

> How can I get the desired behavior? Should I implement my own
> sort algorithm? Any pointers?

You can find topological sorts in Python on the net.  E.g.,

http://starship.python.net/crew/aaron_watters/kjbuckets/tsort.py

this one uses kjbuckets, but it's not hard to transliterate
to forms using other representation for the constraints and
other ways to store sets.


Alex