Python: How to find more than one pathway in a recursive loop when multiple child nodes refers back to the parent?

Question

I'm using recursion to find the path from some point A to some point D. I'm transversing a graph to find the pathways.

Lets say:

Graph = {'A':['route1','route2'],'B':['route1','route2','route3','route4'], 'C':['route3','route4'], 'D':['route4'] }

Accessible through:

A -> route1, route2

B -> route2, route 3, route 4

C -> route3, route4

There are two solutions in this path from A -> D:

route1 -> route2 -> route4

route1 -> route2 -> route3 -> route4

Since point B and point A has both route 1, and route 2. There is an infinite loop so i add a check whenever i visit the node( 0 or 1 values ).

However with the check, i only get one solution back: route1 -> route2 -> route4, and not the other possible solution.

Here is the actual coding: Routes will be substituted by Reactions.

def find_all_paths(graph,start, end, addReaction, passed = {}, reaction = [] ,path=[]):

    passOver =  passed 

    path = path + [start]   
    reaction = reaction + [addReaction]
    if start == end:
        return [reaction] 
    if not graph.has_key(start):
        return []

    paths=[]
    reactions=[]

    for x in range (len(graph[start])):    
        for y in range (len(graph)):
            for z in range (len(graph.values()[y])):
                if (graph[start][x] == graph.values()[y][z]): 
                    if passOver.values()[y][z] < 161 :
                        passOver.values()[y][z] = passOver.values()[y][z] + 1
                            if (graph.keys()[y] not in path):
                                newpaths = find_all_paths(graph, (graph.keys()[y]), end, graph.values()[y][z], passOver , reaction, path)
                            for newpath in newpaths:
                                reactions.append(newpath)
    return reactions

Here is the method call: dic_passOver is a dictionary keeping track if the nodes are visited

solution = (find_all_paths( graph, "M_glc_DASH_D_c', 'M_pyr_c', 'begin', dic_passOver ))

My problem seems to be that once a route is visited, it can no longer be access, so other possible solutions are not possible. I accounted for this by adding a maximum amount of recursion at 161, where all the possible routes are found for my specific code.

if passOver.values()[y][z] < 161 :
                        passOver.values()[y][z] = passOver.values()[y][z] + 1

However, this seem highly inefficient, and most of my data will be graphs with indexes in their thousands. In addition i won't know the amount of allowed node visits to find all routes. The number 161 was manually figured out.

Answer 1

Well, I can't understand your representation of the graph. But this is a generic algorithm you can use for finding all paths which avoids infinite loops.

First you need to represent your graph as a dictionary which maps nodes to a set of nodes they are connected to. Example:

graph = {'A':{'B','C'}, 'B':{'D'}, 'C':{'D'}}

That means that from A you can go to B and C. From B you can go to D and from C you can go to D. We're assuming the links are one-way. If you want them to be two way just add links for going both ways.

If you represent your graph in that way, you can use the below function to find all paths:

def find_all_paths(start, end, graph, visited=None):
    if visited is None:
        visited = set()

    visited |= {start}
    for node in graph[start]:
        if node in visited:
            continue
        if node == end:
            yield [start,end]
        else:
            for path in find_all_paths(node, end, graph, visited):
                yield [start] + path

Example usage:

>>> graph = {'A':{'B','C'}, 'B':{'D'}, 'C':{'D'}}
>>> for path in find_all_paths('A','D', graph):
...   print path
... 
['A', 'C', 'D']
['A', 'B', 'D']
>>> 

Edit to take into account comments clarifying graph representation

Below is a function to transform your graph representation(assuming I understood it correctly and that routes are bi-directional) to the one used in the algorithm above

def change_graph_representation(graph):
    reverse_graph = {}
    for node, links in graph.items():
        for link in links:
            if link not in reverse_graph:
                reverse_graph[link] = set()
            reverse_graph[link].add(node)

    result = {}
    for node,links in graph.items():
        adj = set()
        for link in links:
            adj |= reverse_graph[link]
        adj -= {node}
        result[node] = adj
    return result

If it is important that you find the path in terms of the links, not the nodes traversed you can preserve this information like so:

def change_graph_representation(graph):
    reverse_graph = {}
    for node, links in graph.items():
        for link in links:
            if link not in reverse_graph:
                reverse_graph[link] = set()
            reverse_graph[link].add(node)

    result = {}
    for node,links in graph.items():
        adj = {}
        for link in links:
            for n in reverse_graph[link]:
                adj[n] = link
        del(adj[node])
        result[node] = adj
    return result

And use this modified search:

def find_all_paths(start, end, graph, visited=None):
    if visited is None:
        visited = set()

    visited |= {start}
    for node,link in graph[start].items():
        if node in visited:
            continue
        if node == end:
            yield [link]
        else:
            for path in find_all_paths(node, end, graph, visited):
                yield [link] + path

That will give you paths in terms of links to follow instead of nodes to traverse. Hope this helps :)