Overriding sorting attribute in class, python

Question

I would like to use bisect (as shown here, in the second answer: Does python have a sorted list?), but instead of using a list of numbers, I have a list of objects. In specific, objects from this class: https://networkx.github.io/documentation/latest/_modules/networkx/classes/graph.html

I would like the list to keep the graphs sorted by their number of nodes. If I push these graphs into the list, it looks like it is being inserted in an arbitrary way, (If I run it many times, it changes between the runs).

Is there "sort" function that each class can define, that when applying sorting it will be used (like operator overriding in other languages) ?

import bisect
import networkx as nx

L=[]
G1 = nx.Graph()
G2 = nx.Graph()

G1.add_edges_from([(1,2),(1,3),(2,3),(3,4),(4,5),(4,6),(5,6),(4,7),(7,8),(7,9),(8,9)])
print 'G1', G1.number_of_nodes()
G2.add_edges_from([(1,2),(1,3)])
print 'G2', G2.number_of_nodes()

bisect.insort(L,G1)
bisect.insort(L,G2)

print 'L0 ', L[0].number_of_nodes()
print 'L1' ,L[1].number_of_nodes()

If there's another way of doing that, it would be great to.

Thanks

Something like that may also be ok: L_sort = sorted(L, key=L.__len__) — matlabit, Jan 27 '16 at 09:02
Got it: L_sort = sorted(L, key=lambda graph: graph.number_of_nodes()) — matlabit, Jan 27 '16 at 09:10
Or more simply `L_sort = sorted(L, key=Graph.number_of_nodes)`. But this is equivalent to `L_sort = sorted(L, key=len)` given `Graph` implements `__len__`. You need to reference the class method not instance, so in your first comment `Graph.__len__` would also have worked. — AChampion, Jan 27 '16 at 09:11
Do you need to maintain the list in sorted order, or is it satisfactory to simple sort it after you've added all the graphs to it? — PM 2Ring, Jan 27 '16 at 09:46
it is enough for me to sort it after I add, since the list shouldn't be very long. Thanks for your answer. The Rich Comparison Methods were actually something I was looking for, but didn't know of (it's good to know its out there). — matlabit, Jan 27 '16 at 10:09

PM 2Ring · Answer 1 · 2016-01-27T10:02:37.010

The somewhat arbitrary order of your list is due to the fact that objects are ordered by id (which is derived from the RAM address of the object in CPython) unless they provide some other way to define an ordering.

The easy way to solve your problem is to simply use the built-in list.sort method (or the sorted function), passing key=len as the key function argument.

However, if you want to use bisect to maintain a sorted list, you can do that too, but your class needs to define the Rich Comparison methods.

You could add these methods to your graph class, but it may be easier (and cleaner) to define a new class as a wrapper.

Here's a simple example that wraps the built-in list type. It defines a private method, _cmp to perform length-based comparisons, and the Rich Comparison "magic" methods call _cmp. For greater efficiency, the Rich Comparison methods should be defined directly, to avoid calling another method, but using _cmp is easier to read (and to write :) ).

import bisect

class MyList(object):
    def __init__(self, data):
        self.data = data

    def __repr__(self):
        return 'MyList({0!r})'.format(self.data)

    def _cmp(self, other):
        return len(self.data) - len(other.data)

    #Rich comparison methods
    def __lt__(self, other):
        return self._cmp(other) < 0

    def __le__(self, other):
        return self._cmp(other) <= 0

    def __eq__(self, other):
        return self._cmp(other) == 0

    def __ne__(self, other):
        return self._cmp(other) != 0

    def __ge__(self, other):
        return self._cmp(other) >= 0

    def __gt__(self, other):
        return self._cmp(other) > 0


data = (
    [50, 60],
    [10, 20, 30],
    [1, 2, 3, 4, 5],
    [5, 6],
    [7, 8, 9, 10],
)

blist = []
for seq in data:
    a = MyList(seq)
    bisect.insort(blist, a)
    print(a)
    print(blist)
    print()

output

MyList([50, 60])
[MyList([50, 60])]

MyList([10, 20, 30])
[MyList([50, 60]), MyList([10, 20, 30])]

MyList([1, 2, 3, 4, 5])
[MyList([50, 60]), MyList([10, 20, 30]), MyList([1, 2, 3, 4, 5])]

MyList([5, 6])
[MyList([50, 60]), MyList([5, 6]), MyList([10, 20, 30]), MyList([1, 2, 3, 4, 5])]

MyList([7, 8, 9, 10])
[MyList([50, 60]), MyList([5, 6]), MyList([10, 20, 30]), MyList([7, 8, 9, 10]), MyList([1, 2, 3, 4, 5])]

You may like to take a look at heapq: you may find it better for your purposes than bisect. heapq will (of course) use the Rich Comparison methods if they are defined.

Overriding sorting attribute in class, python

1 Answers1