Enumerating all paths in a directed acyclic graph

Finding all the possible paths in any graph in Exponential. It can be solved by using Backtracking. For DAG's we can do it using Depth first search(DFS). In DFS code, Start at any node, Go to the extreme dead end path and note down all the nodes visited in that path using some array or list. As soon as you find a dead end print the array containing the visited nodes and pop the last stored node and start in the other path of the (n-1)th node. If all the paths of the (n-1)th node are exhausted pop that node from list and start at (n-2)node. Do this untill you reach all the dead ends and reach the first node. All the Printed paths are the Paths in the given DAG.

Can you modify the solution you gave to a solution using BFS rather than DFS ? I was asked this question in a test. What i proposed was that push all edges of the popped element from queue if the popped element is not the target. I wanted to verify if this was correct. Your solution seems correct.

I dont think, we can enumerate all the paths using BFS. But using DFS is the right idea as it sync's with the way recursion works.

I tried verifying my approach on a few cases and it worked correct. I still cannot find any concrete reason to reject BFS. BFS and DFS only differ in order of visits, which is not important here. Can you provide with a test example where BFS approach fails ?

Here is a short python example of a modified DFS to achieve this:

data = # These nodes are disconnected from the rest of the graph def dfs(data, path, paths): datum = path[-1] if datum in data: for val in data[datum]: new_path = path + [val] paths = dfs(data, new_path, paths) else: paths += [path] return paths def enumerate_paths(graph): nodes = list(graph.keys()) all_paths = [] for node in nodes: node_paths = dfs(graph, [node], []) all_paths += node_paths return all_paths 

enumerate_paths(data) 

[[1, 2, 3, 4, 5], [1, 2, 3, 5], [1, 3, 4, 5], [1, 3, 5], [2, 3, 4, 5], [2, 3, 5], [3, 4, 5], [3, 5], [4, 5], [6, 7], [6, 8]] 

I have generalized it so that a starting point does not need to be provided, and it now works with disconnected digraphs

There's also a bug: if a node has empty dependencies, nothing is emitted. One line should read: for val in data[datum] when data[datum] is not empty (sorry I don't know python).

My idea is to extends all path starting from inserting the first edge when there are no path candidates, then proceeding by extending each edge in the path sets at the head, at the tail, or splitting a path when the edge considered create a divergence (conflicting path).

It is an iterative method base on the idea of stability: each time all edges are considered, and if in a turn there were no action to do, then the turn is stable, and there is no more left to do. One thing this method take care is to not fork path too soon: the first turn is a preparation turn, so the fork-phase is active only on the next turns. I am evaluating if it is better (I mean: more correct) to alternate forks and extends phases, and considering stable_turn as stable couple of turns

(sorry, it is javascript, not really easy to read, but I need this exactly in this language)