I am trying to find all possible paths from a given source to destination. I created a directed acyclic graph using the NetworkX library of python. Finding all possible paths is a time exponential problem. I have seen a lot of suggestions about using dynamic programming to improve timing but I could not find any solution that how can I use dynamic programming in this case. Here are the three different approaches I am using for finding all possible paths between two nodes. First approach,
def find_all_paths(graph, start, end, 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
Second approach,
def all_simple_paths(G, source, target, cutoff=None):
if source not in G:
raise nx.NetworkXError('source node %s not in graph'%source)
if target not in G:
raise nx.NetworkXError('target node %s not in graph'%target)
if cutoff is None:
cutoff = len(G)-1
if G.is_multigraph():
raise NetworkXError("astar_path() not implemented for Multi(Di)Graphs")
else:
return _all_simple_paths_graph(G, source, target, cutoff=cutoff)
def _all_simple_paths_graph(G, source, target, cutoff=None):
if cutoff < 1:
return
visited = [source]
stack = [iter(G[source])]
while stack:
children = stack[-1]
child = next(children, None)
if child is None:
stack.pop()
visited.pop()
elif len(visited) < cutoff:
if child == target:
yield visited + [target]
elif child not in visited:
visited.append(child)
stack.append(iter(G[child]))
else: #len(visited) == cutoff:
if child == target or target in children:
yield visited + [target]
stack.pop()
visited.pop()
Third approach,
def printAllPathsUtil(G, u, d, visited, path):
sid = G.node[u]['nodeID']
did = G.node[d]['nodeID']
# Mark the current node as visited and store in path
visited[sid]= True
path.append(u)
# If current vertex is same as destination, then print
# current path[]
if u == d:
global pathlist
pathlist.append(path)
else:
# If current vertex is not destination
#Recur for all the vertices adjacent to this vertex
for i in G.neighbors(u):
j = G.node[i]['nodeID']
if visited[j]==False:
printAllPathsUtil(G, i, d, visited, path)
# Remove current vertex from path[] and mark it as unvisited
path.pop()
visited[sid]= False
def printAllPaths(G,s, d):
# Mark all the vertices as not visited
visited =[False]*G.number_of_nodes()
# Create an array to store paths
path = []
global pathlist
# Call the recursive helper function to print all paths
printAllPathsUtil(G, s, d,visited, path)
return pathlist
Any help in this regard is appreciated.