11

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

Dynamite
  • 341
  • 2
  • 5
  • 17

3 Answers3

14

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

Vamshi
  • 437
  • 6
  • 14
  • 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. – Dynamite Nov 28 '13 at 17:42
  • 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. – Vamshi Nov 28 '13 at 18:27
  • 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 ? – Dynamite Nov 29 '13 at 20:32
  • Do you know if it is possible to do it with NetworkX? – hipoglucido Jan 24 '20 at 10:19
13

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]]
Thys Potgieter
  • 151
  • 1
  • 4
0

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)

Daniele Cruciani
  • 623
  • 1
  • 8
  • 15