Sorting without transitivity

[Frank Niessink]

On Sat Apr 19 23:34:05 2003, 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.
> 
> How can I get the desired behavior? Should I implement my own
> sort algorithm? Any pointers?

Hi all,

First, thanks for all the help and sorry for not responding sooner.
I really appreciate the cheerful and supporting nature of this group.

I've looked into the existing topological sorting implementations in
Python, but all of them seemed to assume that the user of the method
already knows what items are smaller than which other items. 

In my case I don't have that information readily available, so I 
wanted the algorithm to take care of that. Also, giving an exception 
when there are cycles was not acceptable. 

So, I've been working on another implementation. Below is a tlist 
class that sorts its contents topologically. List items should 
provide a __lt__ method and an __eq__ method.

Any comments? Suggestions for improvements?

(Of course I have tests, mail me if you'd like to see the tests as well.)

---------- tlist.py --------------------

class tlist(list):
    ''' Topological list class. This class uses topological sort to
        sort its contents. List items should provide __lt__ and 
        __eq__ methods. '''
        
    def __init__(self, initial=None):
        list.__init__(self, initial or [])
        self.sort()

    def sort(self):
        result = []
        while self:
            result.append(self.popmin())
        self[:] = result

    def popmin(self):
        min = self.min()
        self.remove(min)
        return min

    def min(self):
        smallest, remainder = self[0], self[1:]
        found = False
        while not found:
            for item in remainder:
                if item < smallest:
                    remainder.remove(item)
                    smallest = item
                    break
            else:
                found = True
        return smallest

----------------------------------------

Thanks again, Frank

-- 
The Nutri-Matic was designed and manufactured by the Sirius Cybernetics 
Corporation whose complaints department now covers all the major land masses
of the first three planets in the Sirius Tau Star system.
	-- Douglas Adams, 'The Hitch Hiker's Guide to the Galaxy'