Sorting edges in a graph

Question

I have a class called Graph to represent a connected undirected graph, I want to implement quicksort to sort the edges based on weights on the edges.

class Graph:
    def __init__(self, n):
        self.vertices = range(n)
        self.edges = set([(random.random(), i, j) for i in xrange(n) for j in xrange(n)])

    def qsort(self):
        if len(self.edges) <= 1:
            return self.edges
        else:
            return qsort([x for x in self.edges[1:] if x < self.edges[0]]) + [self.edges[0]] + qsort([x for x in self.edges[1:] if x >= self.edges[0]])

graph = Graph(10)
graph.qsort()

When I try to run the above, I get NameError: global name 'qsort' is not defined.

Can someone tell me what I am doing wrong?

score 1 · Accepted Answer · edited May 23 '17 at 11:44

1

The literal answer to your question is that you are omitting the self keyword: return self.qsort(...) + [self.edges[0]] + self.qsort(...).

It looks like you are trying to implement something like the 3-line qsort from this answer, also given in the Python Cookbook. Your implementation is wrong because it should take two arguments, self and the array you are sorting.

Unfortunately, there is no way to avoid passing in the array, but there is a possible workaround. Add an extra keyword argument to your method: qsort(self, arr = None), then check if the array is None and use self.edges in that case. Your neat syntax of graph.qsort() will not have to change in that case:

def qsort(self, arr = None):
    if arr is None: arr = list(self.edges)
    if len(arr) <= 1: return arr
    else:
        return self.qsort([x for x in arr[1:] if x < arr[0]]) + \
               [arr[0]] + \
               self.qsort([x for x in arr[1:] if x >= arr[0]])

Note that because self.edges is a set, the qsort method is basically a no-op unless you do something with the output array. The set will not be altered.

edited May 23 '17 at 11:44

Community

1
1

answered Oct 19 '15 at 13:23

Mad Physicist

107,652
25
181
264

It looks like 2 different sort are involved. self.sort() in the sample code doesn't accept any parameters. But the call to the missing "global" qsort() passes some ... – LiMar Oct 19 '15 at 13:26
Good call. I have addressed the issue – Mad Physicist Oct 19 '15 at 13:36
I have added `self.qsort(...) + ...`. But now it says: `TypeError: 'set' object has no attribute '__getitem__'` – VeilEclipse Oct 19 '15 at 13:49
You are getting the error because `self.edges` is a set, not a list or other iterable. I have updated the answer. – Mad Physicist Oct 19 '15 at 18:41

Sorting edges in a graph

1 Answers1