Finding many paths in a graph

2018-02-02 21:28:13

I have a graph which we can think of is representing a network of train tracks. Each node is a station and each edge is a piece of track connecting two stations. Each station node may be connected by more than one track and all tracks are one way (i.e the graph is directed).

My job is to find as many routes as possible connecting one node with a set of destination nodes. Routes may contain cycles to the train track analogy breaks down here, but whatever. I have Python code to perform this task, but it is to slow so I would love to get some help in making it faster. Below is my traversal function:

from collections import deque

from itertools import product

def travel(graph, start, dests, count):

queue = deque([[(start, None)]])

paths = []

while queue:

path = queue.popleft()

at = path[-1][0]

if at in dests:

pp = [p[1] for p in path[1:]]

for real_path in product(*pp):