Finding a path in a directed graph in Python

Question

I am a Python beginner. As I wish to learn from the bottom up please keep any suggestions in line with my level, avoiding advanced constructs or graphing libraries.

I have a directed graph, below:

test= {
'a':    [['b'],     ['Starfleet Commander', 'Ninja Hamsters', 'Seahorse Adventures']], 
'b':    [['c'],     ['Call of Arms', 'Dwarves and Swords', 'The Movie: The Game']], 
'c':    [['e','d'],     ['Seven Schemers', 'Pirates in Java Island', 'Dwarves and Swords']], 
'd':    [[],    ['Seahorse Adventures', 'Ninja Hamsters', 'Super Mushroom Man']],
'e':    [[],            ['Seven Schemers', 'Pirates in Java Island', 'Dwarves and Swords']], 
}

Now I create a recursive method to return the path between a source and a destination:

def path_to_friend(network, source, destination):
if source == destination:
    return [destination]
else:
    for new_source in network[source][0]:

            #print 'source> '+ source + '; new source> ' + new_source
            try:
                return [source] + path_to_friend(network, new_source, destination)
            except TypeError, e:
                print source, new_source, destination, e
                pass

And make a function call:

print path_to_friend(test, 'a', 'd')

This fails for the case where the recursion follows the node/key 'e' which has no value. The error returned is:

can only concatenate list (not "NoneType") to list

if the graph entry for 'c' is changed to:

'c':    [['d','e'],     ['Seven Schemers', 'Pirates in Java Island', 'Dwarves and Swords']]

So 'd' is reached before 'e' then no error is raised.

Problem this is not enough information for me to understand why my code is creating this error. I have failed to understand something basic about the language.

Please advise.

Answer 1

Your code has many issues here. First of all, if no path exists between a Node(A) and a Node(B), the function returns None.

And since on the next recusrion, you try to add [source] + path_to_friend(network, new_source, destination) which basically is equivalent to [source] + None it will simply fail and raise the error you just had. To solve this, we will simply test the result of path_to_friend before we append it to the result

def path_to_friend(network, source, destination):
    if source == destination:
        return [destination]
    else:
        for new_source in network[source][0]:

                #print 'source> '+ source + '; new source> ' + new_source
                sub_path = path_to_friend(network, new_source, destination)
                if sub_path is not None:
                    return [source] + sub_path

The second problem you will probably encounter, is in the case there are cycles in the network. In which case, you might find yourself in an infinite loop:

Node A visits Node B which in turn visits Node A....

To fix that, we will use a set that keeps track of the visited nodes and pass it along the function

def path_to_friend(network, source, destination, visited=None):
    if source == destination:
        return [destination]
    else:
        visited = visited or set()
        for new_source in network[source][0]:
                if new_source not in visited: # check if the next node was already visited
                    visited.add(new_source) # add the next node to the list of visited nodes
                    #print 'source> '+ source + '; new source> ' + new_source
                    sub_path = path_to_friend(network, new_source, destination, visited)
                    if sub_path is not None:
                        return [source] + sub_path

Answer 2

You need to do this with a recursive method? If not you can use BFS search. Take a look a this way to solve the problem