Return to Question

I have lots of graphs, so I keep them in dictionaries. Keys are the names of graphs. Here is an example of my data:

graph['graph'] = {
0: {1: {}}, 
1: {2: {}, 3: {}}, 
2: {3: {}}, 
3: {4: {}}, 
4: {5: {}}, 
5: {6: {}}, 
6: {7: {}}, 
7: {6: {}, 5: {}, 8: {}}
8: {}
}
graph['name'] = 'nameofthegraph'

These structures are taken from pygraphviz, which simply shows the outgoing edges from any nodes. Keys are the nodes and values are outgoing edges to the nodes. However, when I have very complicated graphs as below, this code could not find all paths.

These structures are taken from pygraphviz, which simply shows the outgoing edges from any nodes. Keys are the nodes and values are outgoing edges to the nodes. However, when I have very complicated graphs as below, this code could not find all paths.

def findLeaves(gdict):
 # takes graph and find its leaf nodes
 leaves = []
 for endNode in gdict.iterkeys():
  if not gdict[endNode]:
   leaves.append(endNode)
 return leaves
graphPaths = {}
def findPaths(gname, gdict, leave, path):
 # finds all noncycle paths
 if not gdict:
  return []
 temp = [node for node in gdict.iterkeys() if leave in gdict[node].keys() and node not in path]
 if temp:
  for node in temp:
   findPaths(gname, gdict, node, [node] + path)
 else:
  graphPaths[gname].append(path) 
graph = {}
graph['graph'] = {0: {1: {}}, 1: {2: {}, 3: {}}, 2: {3: {}}, 3: {4: {}}, 4: {5: {}}, 5: {6: {}}, 6: {7: {}}, 7: {6: {}, 5: {}, 8: {}}, 8: {}}
graph['name'] = 'nameofthegraph'
# main
leaves = findLeaves(graph['graph'])
graphPaths['nameofthegraph'] = []
seenNodes = []
for leave in leaves:
 findPaths(graph['name'], graph['graph'], leave, [leave])
 
for path in graphPaths.values()[0]:
 print path

def findLeaves(gdict):
 # takes graph and find its leaf nodes
 leaves = []
 for endNode in gdict.iterkeys():
 if not gdict[endNode]:
 leaves.append(endNode)
 return leaves
graphPaths = {}
def findPaths(gname, gdict, leave, path):
 # finds all noncycle paths
 if not gdict:
 return []
 temp = [node for node in gdict.iterkeys() if leave in gdict[node].keys() and node not in path]
 if temp:
 for node in temp:
 findPaths(gname, gdict, node, [node] + path)
 else:
 graphPaths[gname].append(path) 
graph = {}
graph['graph'] = {0: {1: {}}, 1: {2: {}, 3: {}}, 2: {3: {}}, 3: {4: {}}, 4: {5: {}}, 5: {6: {}}, 6: {7: {}}, 7: {6: {}, 5: {}, 8: {}}, 8: {}}
graph['name'] = 'nameofthegraph'
# main
leaves = findLeaves(graph['graph'])
graphPaths['nameofthegraph'] = []
seenNodes = []
for leave in leaves:
 findPaths(graph['name'], graph['graph'], leave, [leave])
 
for path in graphPaths.values()[0]:
 print path

def findLeaves(gdict):
 # takes graph and find its leaf nodes
 leaves = []
 for endNode in gdict.iterkeys():
 if not gdict[endNode]:
 leaves.append(endNode)
 return leaves
graphPaths = {}
def findPaths(gname, gdict, leave, path):
 # finds all noncycle paths
 if not gdict:
 return []
 temp = [node for node in gdict.iterkeys() if leave in gdict[node].keys() and node not in path]
 if temp:
 for node in temp:
 findPaths(gname, gdict, node, [node] + path)
 else:
 graphPaths[gname].append(path) 
  # main
 leaves = findLeaves(graph['graph'])
 graphPaths['nameofthegraph'] = []
 seenNodes = []
 for leave in leaves:
 findPaths(graph['name'], graph['graph'], leave, [leave])

graph['graph']: {
0: {1: {}}, 
1: {2: {}, 3: {}}, 
2: {3: {}}, 
3: {4: {}}, 
4: {5: {}}, 
5: {6: {}}, 
6: {7: {}}, 
7: {6: {}, 5: {}, 8: {}}
8: {}
}
graph['name'] = 'nameofthegraph'

enter image description here

EDIT: I realized that I had some mistakes, sorry about it. Now everything works fine. For the complete code:

def findLeaves(gdict):
 # takes graph and find its leaf nodes
 leaves = []
 for endNode in gdict.iterkeys():
 if not gdict[endNode]:
 leaves.append(endNode)
 return leaves
graphPaths = {}
def findPaths(gname, gdict, leave, path):
 # finds all noncycle paths
 if not gdict:
 return []
 temp = [node for node in gdict.iterkeys() if leave in gdict[node].keys() and node not in path] 
 if temp:
 for node in temp:
 findPaths(gname, gdict, node, [node] + path) 
 else:
 graphPaths[gname].append(path) 
graph = {}
graph['graph'] = {0: {1: {}}, 1: {2: {}, 3: {}}, 2: {3: {}}, 3: {4: {}}, 4: {5: {}}, 5: {6: {}}, 6: {7: {}}, 7: {6: {}, 5: {}, 8: {}}, 8: {}}
graph['name'] = 'nameofthegraph'
# main
leaves = findLeaves(graph['graph'])
graphPaths['nameofthegraph'] = []
seenNodes = []
for leave in leaves:
 findPaths(graph['name'], graph['graph'], leave, [leave])
 
for path in graphPaths.values()[0]:
 print path

def findLeaves(gdict):
 # takes graph and find its leaf nodes
 leaves = []
 for endNode in gdict.iterkeys():
  if not gdict[endNode]:
   leaves.append(endNode)
 return leaves
graphPaths = {}
def findPaths(gname, gdict, leave, path):
 # finds all noncycle paths
 if not gdict:
  return []
 temp = [node for node in gdict.iterkeys() if leave in gdict[node].keys() and node not in path]
 if temp:
  for node in temp:
   findPaths(gname, gdict, node, [node] + path)
 else:
  graphPaths[gname].append(path)  
graph = {}
graph['graph'] = {0: {1: {}}, 1: {2: {}, 3: {}}, 2: {3: {}}, 3: {4: {}}, 4: {5: {}}, 5: {6: {}}, 6: {7: {}}, 7: {6: {}, 5: {}, 8: {}}, 8: {}}
graph['name'] = 'nameofthegraph'

# main
leaves = findLeaves(graph['graph'])
graphPaths['nameofthegraph'] = []
seenNodes = []
for leave in leaves:
 findPaths(graph['name'], graph['graph'], leave, [leave])
  
for path in graphPaths.values()[0]:
  print path

graph['graph'] = {
0: {1: {}}, 
1: {2: {}, 3: {}}, 
2: {3: {}}, 
3: {4: {}}, 
4: {5: {}}, 
5: {6: {}}, 
6: {7: {}}, 
7: {6: {}, 5: {}, 8: {}}
8: {}
}
graph['name'] = 'nameofthegraph'

complex graph example