1,105,263 Community Members

Recursion -- Degrees of Separation

Member Avatar
RM@Bowdoin
Newbie Poster
2 posts since Oct 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I'm trying to find degrees of separation between any two actors in a movie database. I succeed when I reach my base case, which is 1 degree of separation (i.e. actor is in same movie as another actor) but I use recursion to find all other degrees of separation, and I get "runtime error: maximum recursion depth exceeded in cmp".

##gets file with movie information
f = open("filename.txt")
actedWith = {}
ActorList = []
movies = {}
actedIn = []
dos = 1

def getDegrees(target, base, dos):
    for actor in actedWith[base]:
        if target == actor:
            print base, "has ", dos, " degree(s) of separation from ", target
            return
    dos = dos+1
    for actor in actedWith[base]:
        getDegrees(target, actor, dos)


for l in f:
    ##strip of whitespace
    l = l.strip()
    ##split by where forward-slashes are
    l = l.split("/")
    ##add the first "word" on the line to the database of movie names
    movies = {l[0] : l[1:]}
    for e in l[1:]:
        if e in actedWith:
            actedWith[e] = actedWith[e]+movies[l[0]]
        else:
            actedWith[e] = movies[l[0]]

base = raw_input("Enter Actor Name (Last, First): ")
target = raw_input("Enter Second Actor Name (Last, First): ")
getDegrees(target, base, dos)

Database file I use can be found at http://www.mediafire.com/?qtryvkzmuv5jey3
To test base case, I use Bacon, Kevin and Pitt, Brad. To test others I use Bacon, Kevin and Gamble, Nathan Please help!

Note: Cross-posted this question at: http://stackoverflow.com/questions/8206707/recursion-error-degrees-of-separation-python

Member Avatar
pyTony
pyMod
6,103 posts since Apr 2010
Reputation Points: 818 [?]
Q&As Helped to Solve: 1,056 [?]
Skill Endorsements: 42 [?]
Moderator
Featured
 
0
 

Compare your approach with mine www.daniweb.com/software-development/python/code/323868

Shouldn't you return value in your recursive function, now you have only test print and return None?

Member Avatar
Gribouillis
Posting Maven
3,452 posts since Jul 2008
Reputation Points: 1,140 [?]
Q&As Helped to Solve: 883 [?]
Skill Endorsements: 18 [?]
Moderator
 
0
 

I suggest a non recursive function

from collections import deque

def getDegrees(target, base):
    "Return the distance from actor base to actor target (-1 on failure)"
    if target == base:
        return 0
    else:
        enqueued = set([base])
        fifo = deque(((base, 0),))
        while fifo:
            actor, depth = fifo.popleft()
            for other in actedWith.get(actor, ()):
                if other == target:
                    return depth + 1
                elif other not in enqueued:
                    enqueued.add(other)
                    fifo.append((other, depth + 1))
        return -1 # no degree

Technically, it's a breadth-first traversal, see http://en.wikipedia.org/wiki/Tree_traversal#Breadth-first_Traversal

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: