# Finding all simple (without internal cycles) paths in a directed graph with total >1.0 weight

Assume directed graph with each edge being weighted by some positive float.

Problem: find all simple paths (in other words, [0, 1, 2, 0] is simple while [0, 1, 0, 1, 2, 0] is not due to internal [0, 1, 0] cycle) with length <= cutoff and "push" them using pusher callback.

P.S. There exists some realtime engine (abstracted out by pusher) that does such traversal frequently and algorithm should be optimized to be as fast as possible.

from collections import deque
def algorithm(G, source_node, target_node, pusher, cutoff=5):
queue = deque([[source_node]] if source_node in G else deque())
while len(queue):
path = queue.popleft()
if len(path) == cutoff:  # no sense to keep this path, it not gonna fit the limit
continue
adjacency_nodes = G[path[-1]]  # all the neighbours from the latest node in this path
if not len(adjacency_nodes):  # deadend reached: you can't get any further from this node and it doesn't fit the requirement, so just forgetting it
continue
extended_path = path.copy() + [adjacency_node]  # might some smart linked list do any better here?
pusher(extended_path)  # wow! found one! does not make sense to keep it, since any other path from here will introduce an internal cycle, right?
else:
queue.append(extended_path)  # stay calm and keep trying

• Why did you write this code? What is it being used for? What would you like out of a review? – Reinderien Sep 15 '19 at 13:35
• @Reinderien, I'd like community to review it in terms of "Python ideomatic code" (which I am not good with) and, more importantly, algorithm preformance. For example, knowledgeble people might suggest a better datasctructure or whatever. – Sereja Bogolubov Sep 15 '19 at 13:36

An empty container like a list or deque is False, so it isn't necessary to use len() on them. This is more "pythonic"

while queue:
...

...


It seems wasteful to add a path to the queue only to discard it because it is too long. It would be better to check the length before making a copy of the path and adding it to the queue. Moreover, if len(path) == is cutoff - 1 the only possible solution is if target_node is in adjacency_nodes. So, something like this might be faster:

from collections import deque

def algorithm(G, source_node, target_node, pusher, cutoff=5):

if source_node not in G:
return

queue = deque([[source_node]])

while queue:
path = queue.popleft()

continue

if len(path) == cutoff - 1:

Lastly, the networkx library provides all_simple_paths(G, source, target, cutoff=None) which is a generator of all simple paths from source to target with a maximum length cuttoff. FYI, networkx uses a DFS search (source code).