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

