CODEWITHSUNDEEP
pythonpython-2.7typeerror
Enigma
Enigma

Reputation: 129

Path Finder code, __getitem__ TypeError

I am trying to make a "path finder"

def find_all_paths(start, end, graph, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths


 graph={1: ['2'], 2: ['3', '4', '5'], 3: ['4'], 4: ['5', '6'], 5: [], 6: []}

if I enter find_all_paths(2,5,graph) in the shell I should get back all the paths that go from key 2 in the graph dictionary to the the 5 values a proper result should be something like

path=[[2,5],[2,3,4,5][2,4,5]]

the code keeps giving values errors such as 

   for node in graph[start]:
TypeError: 'int' object has no attribute '__getitem__'

could someone please help me get this thing running

Upvotes: 0

Views: 76

Answers (1)

Laurent LAPORTE
Laurent LAPORTE

Reputation: 22992

There are several awkwardness and errors:

Instead of initialising the path parameter with a list, use None. And create the empty list in the function body.

def find_all_paths(start, end, graph, path=None):
    path = path or []

The values passed to the find_all_paths doesn't respect the signature. Write this instead:

newpaths = find_all_paths(node, end, graph, path)

Since the values are integer, the graph must contain int instead of strings.

graph = {1: [2], 2: [3, 4, 5], 3: [4], 4: [5, 6], 5: [], 6: []}

Here is the fixed version of your code:

def find_all_paths(start, end, graph, path=None):
    path = path or []
    path.append(start)
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(node, end, graph, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

If you try this:

graph = {1: [2], 2: [3, 4, 5], 3: [4], 4: [5, 6], 5: [], 6: []}
print(find_all_paths(2, 5, graph))

You'll get:

[[2, 3, 4, 5, 6]]

Upvotes: 2

Related Questions