Enumerating all paths in a directed acyclic graph

Question

Is there any standard algorithm that finds all possible paths in a directed a-cyclic graph. If not, how can i make changes in BFS/Dijkstra/any other algorithm to enumerate all paths in a DAG

Answer 1

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

data = {1 : [2,3],   # Directed acyclic graph adjacency list
        2 : [3],
        3 : [4,5],
        4 : [5],
        6 : [7,8]}   # 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

Input:

enumerate_paths(data)

Output:

[[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]]

Answer 2

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

Here the code:

https://gist.github.com/danielecr/6abd8ad48461347238ad1caf3714fe6a

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