CODEWITHSUNDEEP
algorithmgraph
Dynamite
Dynamite

Reputation: 361

Enumerating all paths in a directed acyclic graph

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

Upvotes: 13

Views: 24132

Answers (3)

Thys Potgieter
Thys Potgieter

Reputation: 141

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

Upvotes: 12

Daniele Cruciani
Daniele Cruciani

Reputation: 623

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)

Upvotes: 0

Vamshi
Vamshi

Reputation: 457

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.

You can check the code http://pastebin.com/p6ciRJCU

Upvotes: 16

Related Questions