My code does a DFS on the given graph and prints all possible paths for a given start and end node. My question is how can this be improved?
- Can some form of memoization be used here? There are cases where a path from a certain source - destination is already found and will be an intermediate path for a different source - destination but it is still computed again.
- As it is a generator will that make memoization different?
- Is there an already existing text book algorithm that I am missing? Does not have to be specifically DFS.
- Pythonic / Idiomatic code suggestions are also welcome.
This is my code
from itertools import product
def find_path(g, src, dst):
"""Prints all possible path for a graph `g` for all pairs in `src` and `dst`
Args:
g (list): 2d list, graph
src (list): list of nodes that will be the source
dst (list): list of nodes that will be the destination
"""
graph = {}
# constructing a graph
for from_, to_ in g:
graph.setdefault(from_, set()).add(to_)
graph.setdefault(to_, set()).add(from_) # undirected
def dfs(src, dst, path, seen):
"""Recursive generator that yields all paths from `src` to `dst`
Args:
src (int): source node
dst (int): destination node
path (list): path so far
seen (set): set of visited nodes
Yields:
list: all paths from `src` to `dst`
"""
if src in seen:
return
if src == dst:
yield path + [src]
return
seen.add(src)
for i in graph.get(src, []):
yield from dfs(i, dst, path + [src], seen)
seen.remove(src)
# start finding path for all `src` `dst` pairs
for source, destination in product(src, dst):
print(source, destination, list(dfs(source, destination, [], set())))
g = list(product(range(1, 5), repeat=2)) # a graph for testing purpose
src = dst = range(1, 5) # source and destination, in actual code this will be a list
find_path(g, src, dst)