Sorting with only a partial order definition

[Paul Rubin]

Lasse Vågsæther Karlsen <lasse at vkarlsen.no> writes:
> I have a list of items and a "rule" for ordering them.
> 
> Unfortunately, the rule is not complete so it won't define the correct
> order for any two items in that list.
> 
> In other words, if I pick two random items from the list I may or may
> not have a rule that dictates the order of those two items. The rule
> could be "implicit" in that I got rules for other items, for instance:

That's called topological sorting and any reference on graph
algorithms will describe how to do it.  I don't know of Python code
offhand but it's easy to write.

   http://en.wikipedia.org/wiki/Topological_sorting

gives a straightforward linear-time algorithm.