Expanding a path from a graph

Question

I know there are modules for this type of structure, but I like and prefer to learn how things really works by myself. So... I've being trying to expand a path from a graph, such as for example:

Click to copy

g = dict(
    s=['a','d','s'],
    a=['s','d','b'],
    d=['s','a','e'],
    b=['a','e','c'],
    e=['d','b','f'],
    f=['e','g'],
    c=['b'],
    g=['f'])

So far I can see the neighbors of a given node with:

Click to copy

def vecinosDe(n = ''):
    return g[n]

I want to each time I call a function that has one argument given, a graph node, returns a list of the other nodes connected to that one given.
Then enter that same list given, created, to that same function to return the nodes connected to that list graph nodes given, and consecutively until it reaches to the 'g' node.
I also know that I need to check if the node connected to the node given has any recursion(loop).

Here's the code I have so far:

Click to copy

def expandir(n = '', lista = []):
    lista.append([n]) #or lista = lista + [n]?
    for v in g[n]:
        for i in range(len(lista)): #?
            lista[i].append(v)
    return lista

This is what happens, which I know it's not good, lol.

Click to copy

>>> expandir('s')
[['s', 'd', 'a', 's']]
>>> expandir('d')
[['S', 'D', 'A', 'S', 'S', 'A', 'E'], ['D', 'S', 'A', 'E']]

In some part of the code within the second for loop I think I should check if there is a node equal to the node I want to expand, the node given. Here's where I get stuck.
Try this?

Click to copy

if n == v:  #?

Also I'm thinking that this may need some kind of recursion, right? But I would like some tips to keep putting the puzzle together. :P

Should I return a list, a list of lists?... how? :S
Any tips? :)
thanks in advance

Answer 1

Here's a modification of @tangentstorm's answer that avoids raising explicit exception by using a generator:

Click to copy

def pathiter(adjacent_vertexes, start, end, path=None):
    if path is None: path = (start,)

    for vertex in adjacent_vertexes[start]:
        if vertex == end:
            yield path + (vertex,)
        elif vertex not in path:
            for p in pathiter(adjacent_vertexes, vertex, end, path + (vertex,)):
                yield p

Example:

Click to copy

end = 'g'
for v in g:
    path = next(pathiter(g, v, end), None)
    if path is not None:
        print ' → '.join(path)
    else:
        print "no path between %s and %s" % (v, end)

Output

Click to copy

a → s → d → e → f → g
c → b → a → s → d → e → f → g
b → a → s → d → e → f → g
e → f → g
d → s → a → b → e → f → g
g → f → g
f → g
s → a → d → e → f → g

You could print all paths:

Click to copy

for v in graph:
    print "%s ⇢ %s:" % (v, end)
    path = None
    for path in pathiter(graph, v, end):
        print '\t'+' → '.join(path)
    if path is None:
        print "no path between %s and %s" % (v, end)

Output

Click to copy

a ⇢ g:
    a → s → d → e → f → g
    a → d → e → f → g
    a → b → e → f → g
c ⇢ g:
    c → b → a → s → d → e → f → g
    c → b → a → d → e → f → g
    c → b → e → f → g
b ⇢ g:
    b → a → s → d → e → f → g
    b → a → d → e → f → g
    b → e → f → g
e ⇢ g:
    e → f → g
d ⇢ g:
    d → s → a → b → e → f → g
    d → a → b → e → f → g
    d → e → f → g
g ⇢ g:
    g → f → g
f ⇢ g:
    f → g
s ⇢ g:
    s → a → d → e → f → g
    s → a → b → e → f → g
    s → d → a → b → e → f → g
    s → d → e → f → g

Answer 2

Here's my take on it:

Click to copy

graph = g # from your code

def findPath(graph, node, path=tuple(), end='g'):
    for key in graph[node]:
        next = path + (key,)
        if key == end:
            raise Exception("Found it! Path is: %s" % '.'.join(path))
        elif key in path:
            pass # avoid loops
        else:
            # print next # if you want to see what it's doing
            findPath(graph, key, next, end)
    else: # no break/raise at this level
        if len(path) == 0: print "no path found."

findPath(graph, 's')

I think your main problem [aside from really unreadable variable names :)] is that your path (lista) has a default argument of []. This is bad because default arguments are mutable

Also I'm thinking that this may need some kind of recursion, right? But I would like some tips to keep putting the puzzle together. :P

Yep, when you see a tree, think recursion. :)