Getting friends within a specified degree of separation

Question

Hi, all. I'm a very, very new programmer. My language of choice at the moment is Python, and I feel like I have a decent feel for it. I'm just now starting to learn about recursion. (By the way, if anyone could recommend a good guide on this, please let me know!) Just so you all know, this question is very elementary, and the code I'm posting is horribly, horribly wrong.

Anyway, I'm trying to write a function that will get all the friends within a specified degree. If I pass it 0 as the degree, I just want myself. If I pass it 1, I want me and all my friends. 2, I want me, my friends, and all their friends, and so on.

I've tried quite a few different ways of doing this, but none work. I try to visualize how it should work in theory, and I can't quite get that either because I'm so inexperienced in this area. Maybe a kind soul here can show me all the ways in which this code fails and then explain how to do it properly and/or recommend a good guide on the subject. Here goes:

    def getFriends(self,degree,friendList):
        if degree == 0:
            friendList.append(self)
            return friendList
        else:
            friendList = friendList.append(self)
            for each in self.friends:
                each.getFriends(degree-1,friendList)

It doesn't work, and I know I've done stupid, stupid things. Someone please slap me and point me in the correct direction!

Thanks.

Answer 1

You can move friendList.append(self) to the line before the if - you need it in both cases. You also don't need to assign the result to friendlist - it's a bug.

In your algorithm, you will likely to add the same people twice - if A is a friend of B and B is a friend of A. So, you need to keep a set of friends that you've processed already. Before processing, check this set and don't do anything if the person has been processed already.

Answer 2

friendList = friendList.append(self)

This sets friendList to None, unconditionally, as that's the invariable return value of any list's append method -- so, fix that weirdness first...!-)

Once you've fixed that, you still need to fix the function so that it always ends with return of something -- "falling off the end" returns None. E.g.:

def getFriends(self,degree, friendList):
    if degree == 0:
        friendList.append(self)
        return friendList
    else:
        friendList.append(self)
        for each in self.friends:
            each.getFriends(degree-1, friendList)
        return friendList

which can and clearly should be refactored to eliminate the duplication (DRY, Don't Repeat Yourself, is THE heart of programming...):

def getFriends(self,degree, friendList):
    friendList.append(self)
    if degree > 0:
        for each in self.friends:
            each.getFriends(degree-1, friendList)
    return friendList

PS: that (the alist=alist.append(...) issue) precisely how I got back in touch with my wife Anna in 2002 (we'd been not-quite-sweetheart friends many years before but had lost track of each other) -- she started studying Python, used exactly this erroneous construct, couldn't understand why it failed -- looked around the Python community, saw and recognized my name, mailed me asking about it... less than two years later we were married, and soon after she was the first woman member of the Python Software Foundation and my co-author in "Python Cookbook" 2nd ed. So, of course, I've got an incredible sweet spot for this specific Python error...;-).

Answer 3

Is your identation correct? The body of the method should be indented relative to it's definition

Answer 4

There's no return statement in the else clause. So if degree != 0, this method will always return None. You want to append the result of each recursive getFriends call to your friendList, and then return friendList.

By the way, if you want to make this algorithm faster, there are well established methods for doing this with either graph algorithms or matrix manipulation. For example, if you represent friendship relationships with an adjacency matrix A, and you want to find all people who are within n degrees of separation of each other, you can compute B=A^n. If B[i][j] > 0, then i and j are within n degrees of separation of each other. Matrix multiplication is easy with a package like NumPy.

Answer 5

(Sorry, I can't comment on Alex's answer... yet)

I don't really like the idea that getFriends returns a value that is never used. It works, for sure, but it looks a bit intriguing ;) Also, the first call to getFriends would be self.getFriends(degree, []) which is confusing: when getting a list of friends, why would you pass as an argument an empty list, right?

For clarity, I think that I would prefer this slightly different version, using the _getFriends helper function:

def getFriends(self, degree):
    friendList = []
    self._getFriends(degree, friendList)
    return friendList

def _getFriends(self, degree, friendList):
    friendList.append(self)
    if degree:
        for friend in self.friends:
            friend._getFriends(degree-1, friendList)