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:

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:

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:

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.

>>> 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?

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:

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:

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

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:

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

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:

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. :)

Answer 3

There is a very good sample in javascript to path searching in http://eloquentjavascript.net/chapter7.html. It teaches you, of course, in javascript, to develop step by step this very algorithm. Its a good reading to understand what it's doing.