Sorting with only a partial order definition

[Lasse Vågsæther Karlsen]

Paul Rubin wrote:
> 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.

Thank you both.

-- 
Lasse Vågsæther Karlsen
http://usinglvkblog.blogspot.com/
mailto:lasse at vkarlsen.no
PGP KeyID: 0x2A42A1C2