Six degrees (Graphs in python)

[JJHT7439]

I have to complete a lab which basically takes a text file and finds path between 2 actors that you input by going through the movies in the text file. (For the labs purposes we are only doing 3 degrees of separation)

For example if the text file is:

Apollo13 Kevin Bacon Tom Hanks Gary sinise
HollowMan Elisabeth Shue Kevin Bacon Josh Brolin
AFewGoodMen Tom Cruise Demi Moore Jack Nicholson Kevin Bacon
OneCrazySummer John Cusack Demi Moore
DaVinciCode Tom Hanks Ian McKellen Audrey Tautou

and you searched from the start being John Cusack, and goal being Kevin Bacon it would return:

John Cusack
was in OneCrazySummer with
Demi Moore
was in AFewGoodMen with
Kevin Bacon

I am trying to do this by constructing a graph which has actors only neighboring movies and movies only neighboring actors, and doing a depth first search through them to find a path.

I am currently getting a lot of errors trying to load the graph in my code. Specifically at a point in my code where I try to access the neighbors of the node it returns that NoneType.neighbors does not exist, but I don't see how the actorNode or movieNode can be NoneType. I know that my code to this point probably does not work but I can't test past the construction of the graph.

Here's my code so far:

# Class for node
class node:
    __slots__ = ('movie','neighbor')

# Node constructor
def mkNode(name):
    n = node
    n.name = name
    return

# Find if node is in the graph
def findNode(nodelist, name):
    for n in nodelist:
        if n == None:
            return None
        elif n.name == name:
            return

#Creates graph
def loadGraphFile(file):
    graph = []
    for line in file:
        contents = line.split()
        movieName = contents[0]
        actorName = contents[1:]
        movieNode = findNode(graph, movieName)
        if movieNode == None:
            movieNode = mkNode(movieName)
            graph.append(movieNode)
        actorNode = findNode(graph,actorName)
        if actorNode == None:
            actorNode = mkNode(actorName)
            graph.append(actorNode)
        actorNode.neighbor.append(movieNode)
        movieNode.neighbor.append(actorNode)
    return graph

# Searches graph for path 
def search(start,goal,visited):
    if start == goal:
        return [start]
    else:
        for n in start.neighbor:
            content = line.split()
            for x in range(0,(len(content)-1),2):
                z = (content[x] + content[x+1])
                if not z in visited:
                    visited.append(z)
                    path = search(z,goal,visited)
                    if path != None:
                        return [start] + path
                    visited.append(x)

specifically when it does actorNode.neighbor.append(movieNode) it returns the error that NoneType.neighbor doesn't exist. But I have a statement right above it to check if the actorNode is None and change it.

[Gribouillis]

The first error I see is that line 7 should be n = node() .

[JJHT7439]

Alright, I didn't catch that typo but it still doesn't solve the problem. I revised my code a little but I get the same problem.

This is the code I have now:

# Class for node
class node:
    __slots__ = ('name','neighbors')

# Node constructor
def mkNode(name):
    n = node()
    n.name = name
    n.neighbors = []
    return

# Find if node is in the graph
def findNode(nodelist, name):
    for n in nodelist:
        if n == None:
            return None
        elif n.name == name:
            return 

#Creates graph
def loadGraphFile(file):
    graph = []
    for line in file:
        contents = line.split()
        movieName = contents[0]
        actorName = contents[1:]
        movieNode = findNode(graph, movieName)
        if movieNode == None:
            movieNode = mkNode(movieName)
            graph.append(movieNode)
        actorNode = findNode(graph,actorName)
        if actorNode == None:
            actorNode = mkNode(actorName)
            graph.append(actorNode)
        actorNode.neighbor.append(movieNode)
        movieNode.neighbor.append(actorNode)
    return graph

def loadGraphFileName(filename):
    return loadGraphFile(open(filename))

# Searches graph for path 
def search(start,goal,visited):
    if start == goal:
        return [start]
    else:
        for n in start.neighbor:
            content = line.split()
            for x in range(0,(len(content)-1),2):
                z = (content[x] + content[x+1])
                if not z in visited:
                    visited.append(z)
                    path = search(z,goal,visited)
                    if path != None:
                        return [start] + path
                    visited.append(x)

And this is the text file I'm using:

Apollo13 Kevin Bacon Tom Hanks Gary sinise
HollowMan Elisabeth Shue Kevin Bacon Josh Brolin
AFewGoodMen Tom Cruise Demi Moore Jack Nicholson Kevin Bacon
OneCrazySummer John Cusack Demi Moore
DaVinciCode Tom Hanks Ian McKellen Audrey Tautou

When I run loadGraphFileName('6degree.txt')
It always gives me the error:
File "C:\Users\***\Desktop\sixdegrees.py", line 37, in loadGraphFile
actorNode.neighbor.append(movieNode)
AttributeError: 'NoneType' object has no attribute 'neighbor'

[TrustyTony]

Add print statements to loadGraphFileName every few lines to check your assumptions, especially at end of for and before error place.

[woooee]

To emphasize what Tony said:

actorNode = findNode(graph,actorName)
        if actorNode == None:
            actorNode = mkNode(actorName)
            print "created", actorNode
            graph.append(actorNode)
            print "graph", graph

You want to test each function individually before going on to the next function, or you have 56 lines of code to debug and no idea what the problem is.

[nezachem]

What does mkNode return? Or, to put it other way around, why mkNode returns nothing?

[SgtMe]

Futhermore, why does findNode return none, and why do you need an if statement there to check whether it will return either nothing, or nothing? Therefore, findNode and actorNode will always be none, so your 'ifs' at lines 28 and 31 will always be none.

[JJHT7439]

Wow a lot of posts, I figured out that the problem was that I missed a character so mkNode didn't return the created node to actorNode or movieNode.

And findNode is to check if the node is already in the graph. I did not have it checking for None at the start, because the above problem made it seem like it was not catching the None value in that function. I removed the if == None part now.

[samidh456]

Slast12 Would you like to update your code with the one working and then mark it solved so that order people might find this post useful.

[JJHT7439]

# Class for node
class node:
    __slots__ = ('name','neighbor')

# Node constructor
def mkNode(name):
    n = node()
    n.name = name
    n.neighbor = []
    return n

# Find if node is in the graph
def findNode(nodelist, name):
    for n in nodelist:
        if n.name == name:
            return 

#Creates graph
def loadGraphFile(file):
    graph = []
    for line in file:
        contents = line.split()
        movieName = contents[0]
        actorName = contents[1:]
        movieNode = findNode(graph, movieName)
        if movieNode == None:
            movieNode = mkNode(movieName)
            graph.append(movieNode)
        actorNode = findNode(graph,actorName)
        if actorNode == None:
            actorNode = mkNode(actorName)
            graph.append(actorNode)
        actorNode.neighbor.append(movieNode)
        movieNode.neighbor.append(actorNode)
    return graph

def loadGraphFileName(filename):
    return loadGraphFile(open(filename))

Yeah thats the code I have for creating the graph, It seems to work.

[woooee]

"findNode" still returns "None" in all cases.

[woooee]

Since it is only 3 degrees of separation and a small data set, you could also do this with dictionaries, which is not as efficient, unless of course you are required to code it a certain way.

from collections import defaultdict
test_entries = ["Apollo13, Kevin Bacon, Tom Hanks, Gary Sinise",
                "HollowMan, Elisabeth Shue, Kevin Bacon, Josh Brolin",
                "AFewGoodMen, Tom Cruise, Demi Moore, Jack Nicholson, Kevin Bacon",
                "OneCrazySummer, John Cusack, Demi Moore",
                "DaVinciCode, Tom Hanks, Ian McKellen, Audrey Tautou"]

# a dictionary of titles --> actors
movie_dict = defaultdict(list)
# a dictionary of actors --> movie titles
actor_dict = defaultdict(list)
for movie_actor in test_entries:
   substrs = movie_actor.split(",")
   movie_name = substrs[0].strip()
   for actor in substrs[1:]:            ## all actors in the movie
       actor = actor.strip()
       movie_dict[movie_name].append(actor)
       actor_dict[actor].append(movie_name)
   
##   all other actors that were in John Cusack films
for title in actor_dict["John Cusack"]:  ## all John Cusack movie titles
    for actor in movie_dict[title]:   ## actors in this John Cusack film
        for actor_title in actor_dict[actor]:  ## all movies actor was in
            if actor_title in actor_dict["Kevin Bacon"]:  ## also was in
                print "Found", actor, actor_title

[TrustyTony]

Two things: findNode looks for me to allways return None, and when is the file closed?

[Gribouillis]

# Class for node
class node:
    __slots__ = ('name','neighbor')

# Node constructor
def mkNode(name):
    n = node()
    n.name = name
    n.neighbor = []
    return n

# Find if node is in the graph
def findNode(nodelist, name):
    for n in nodelist:
        if n.name == name:
            return 

#Creates graph
def loadGraphFile(file):
    graph = []
    for line in file:
        contents = line.split()
        movieName = contents[0]
        actorName = contents[1:]
        movieNode = findNode(graph, movieName)
        if movieNode == None:
            movieNode = mkNode(movieName)
            graph.append(movieNode)
        actorNode = findNode(graph,actorName)
        if actorNode == None:
            actorNode = mkNode(actorName)
            graph.append(actorNode)
        actorNode.neighbor.append(movieNode)
        movieNode.neighbor.append(actorNode)
    return graph

def loadGraphFileName(filename):
    return loadGraphFile(open(filename))

Yeah thats the code I have for creating the graph, It seems to work.

I modified your code

# Class for node
class node:
    __slots__ = ('name','neighbor')

# Node constructor
def mkNode(name):
    n = node()
    n.name = name
    n.neighbor = []
    return n

# Find if node is in the graph
def findNode(nodelist, name):
    for n in nodelist:
        if n.name == name:
            return n

#Creates graph
def loadGraphFile(file):
    graph = []
    for line in file:
        contents = line.split()
        movieName = contents[0]
        actorNames = [contents[i]+ " " + contents[i+1] for i in range(1, len(contents), 2)]
        movieNode = findNode(graph, movieName)
        if movieNode == None:
            movieNode = mkNode(movieName)
            graph.append(movieNode)
        for actorName in actorNames:
            actorNode = findNode(graph,actorName)
            if actorNode == None:
                actorNode = mkNode(actorName)
                graph.append(actorNode)
            actorNode.neighbor.append(movieNode)
            movieNode.neighbor.append(actorNode)
    return graph

def loadGraphFileName(filename):
    return loadGraphFile(open(filename))

Here is the graph on a png image.

@tonyjv : it's not very important to close files in python :)

[newbieha]

Apollo13:
: Apollo13

this is output. doesn't seem right

[Gribouillis]

To draw your graph as I did above, you can use this code snippet http://www.daniweb.com/code/snippet323792.html

[James_41]

I have a similar code and it is not printing out my text file