title: Python: How to find more than one pathway in a recursive loop when multiple child nodes refers back to the parent?
body: <p>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.</p>
  
  <p>Lets say:</p>
  
  <p>Graph = {'A':['route1','route2'],'B':['route1','route2','route3','route4'], 'C':['route3','route4'], 'D':['route4'] }</p>
  
  <p>Accessible through:</p>
  
  <p>A -> route1, route2</p>
  
  <p>B -> route2, route 3, route 4</p>
  
  <p>C -> route3, route4</p>
  
  <p>There are two solutions in this path from A -> D:</p>
  
  <p>route1 -> route2 -> route4</p>
  
  <p>route1 -> route2 -> route3 -> route4</p>
  
  <p>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 ).</p>
  
  <p>However with the check, i only get one solution back: route1 -> route2 -> route4, and not the other possible solution. </p>
  
  <p>Here is the actual coding: Routes will be substituted by Reactions. </p>
  
  <pre><code>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] &lt; 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
  </code></pre>
  
  <p>Here is the method call: dic_passOver is a dictionary keeping track if the nodes are visited</p>
  
  <pre><code>solution = (find_all_paths( graph, "M_glc_DASH_D_c', 'M_pyr_c', 'begin', dic_passOver ))
  </code></pre>
  
  <p>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.</p>
  
  <pre><code>if passOver.values()[y][z] &lt; 161 :
                          passOver.values()[y][z] = passOver.values()[y][z] + 1
  </code></pre>
  
  <p>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.</p>