backtracking in the graph

Question

In python I have a graph as adjacency list presentation. and a distance from specific points to all other elements in the graph.

graph = {
    1 :[2, 7],
    2 :[1, 3],
    3 :[2, 4, 8],
    4 :[3, 5, 9],
    5 :[4, 6, 9],
    6 :[5, 8, 10],
    7 :[1, 8,10],
    8 :[3, 6, 7, 9],
    9 :[4, 5, 8],
    10:[7, 6]
    }

distance = {1: 1, 2: 0, 3: 0, 4: 1, 5: 2, 6: 2, 7: 2, 8: 1, 9: 2, 10: 3}

How I can backtrack the path from an element: for instance if I will try to backtrack from 10, it should return:

[10, 7, 1, 2]
[10, 7, 8, 3]
[10, 6, 8, 3]

I tried to do this recursively

def findprev(graph, distance, el, path = []):
    value = distance[el]
    if value == 0:
        print path
        path = []

    for i in graph[el]:
        if value - 1 == distance[i]:
            path.append(i)
            path = findprev(graph, distance, i, path)
    return path

but apparently I am losing something important, because the result is:

[7, 1, 2]
[8, 3]
[6, 8, 3]

Can anyone help to find a bug

This is not so much "backtracking" (in the computer-science sense) so much as it is finding the path between two nodes in a graph via search (e.g. DFS, BFS). — ninjagecko, Apr 28 '12 at 14:34
http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument — Fred Foo, Apr 28 '12 at 15:15

Rob Wouters · Accepted Answer · 2012-04-28T15:20:16.507

1

def findprev(graph, distance, el, path=None):
    if path is None:
        path = [el]
    else:
        path.append(el)
    value = distance[el]
    if value == 0:
        print(path)

    for i in graph[el]:
        if value - 1 == distance[i]:
            findprev(graph, distance, i, path[:])

findprev(graph, distance, 10)

Output:

[10, 7, 1, 2]
[10, 7, 8, 3]
[10, 6, 8, 3]

Or, if you want to return the resulting paths:

def findprev(graph, distance, el, path=None):
    if path is None:
        path = [el]
    else:
        path.append(el)
    value = distance[el]
    if value == 0:
        return [path]

    result = []
    for i in graph[el]:
        if value - 1 == distance[i]:
            paths = findprev(graph, distance, i, path[:])
            for p in paths:
                result.append(p)
    return result

edited Apr 28 '12 at 15:20

answered Apr 28 '12 at 15:11

Rob Wouters

15,797
3
42
36

If you just pass plain `path` you are reusing the same list for the construction of different paths. If you pass `path[:]` a copy is passed to the recursive call instead. – Rob Wouters Apr 28 '12 at 15:19
Also never use mutable values as default arguments of a function. See: http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument – Rob Wouters Apr 28 '12 at 15:21

jamylak · Answer 2 · 2012-04-28T16:33:11.087

Here is another solution to your problem. I renamed distance to distances because it seemed like a better name to me and i use the name distance for each individual point's distance.

>>> def find_paths(point,path=[]):
        distance = distances[point]
        elements = graph[point]
        if distance == 0:
            yield path + [point]
        else:
            for element in elements:
                if distances[element] == distance - 1:
                    for item in find_paths(element,path+[point]):
                        yield item


>>> for path in find_paths(10):
        print path


[10, 7, 1, 2]
[10, 7, 8, 3]
[10, 6, 8, 3]

backtracking in the graph

2 Answers2