get all possible paths in directed cyclic graph

July 5, 2024

I’ve a directed cyclic graph, want to find all possible paths starting from given (or by default root) node without repeating the same path again.

Here, node "B", "D", and "C" is cyclic.

My code :

def find_all_possible_paths(graph, start, path=[]):
    path = path + [start]
    paths = [path]
   
    if len(graph[start]) == 0:
        return [path]
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_possible_paths(graph, node, path)
            for newpath in newpaths:
                paths.append(newpath)
        else:
            return paths
    return paths

direct_cyclic_graph = nx.DiGraph()
direct_cyclic_graph.add_edge('A','B')
direct_cyclic_graph.add_edge('A','C')
direct_cyclic_graph.add_edge('A','E')
direct_cyclic_graph.add_edge('B','D')
direct_cyclic_graph.add_edge('C','B')
direct_cyclic_graph.add_edge('D','C')
direct_cyclic_graph.add_edge('D','F')

print(find_all_possible_paths(direct_cyclic_graph , 'A'))

**Output** 

[
 ['A'], 
 ['A', 'B'], 
 ['A', 'B', 'D'], 
 ['A', 'B', 'D', 'C'], 
 ['A', 'B', 'D', 'F'], 
 ['A', 'C'], 
 ['A', 'C', 'B'], 
 ['A', 'C', 'B', 'D'], 
 ['A', 'E']
]

**Expected **

I’m just missing one path i.e. [‘A’, ‘C’, ‘B’, ‘D’, ‘F’] apart from that I’m able to get all.

Not sure what am I missing in my code. Pls help.

>Solution :

The problem is in this part:

    else:
        return paths

That breaks the loop, while there might be more neighbors to visit. You should just do nothing in the current iteration, but still have the loop continue. So remove these two lines of code, so you get this:

import networkx as nx

def find_all_possible_paths(graph, start, path=[]):
    path = path + [start]
    paths = [path]

    if len(graph[start]) == 0:
        return [path]
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_possible_paths(graph, node, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

direct_cyclic_graph = nx.DiGraph()
direct_cyclic_graph.add_edge('A','B')
direct_cyclic_graph.add_edge('A','C')
direct_cyclic_graph.add_edge('A','E')
direct_cyclic_graph.add_edge('B','D')
direct_cyclic_graph.add_edge('C','B')
direct_cyclic_graph.add_edge('D','C')
direct_cyclic_graph.add_edge('D','F')

for path in find_all_possible_paths(direct_cyclic_graph , 'A'):
    print(path)

The output of the above program is:

['A']
['A', 'B']
['A', 'B', 'D']
['A', 'B', 'D', 'C']
['A', 'B', 'D', 'F']
['A', 'C']
['A', 'C', 'B']
['A', 'C', 'B', 'D']
['A', 'C', 'B', 'D', 'F']
['A', 'E']

… including the missing path near the end.

Other remarks

The default for the path parameter should better not be a mutable type. path=[] can be the cause of trouble if you call this function on more than one graph. Instead, define that parameter as path=None and change the first statement in the function body to:
```
    path = (path or []) + [start]
```
You don’t actually need the if len(graph[start]) == 0: block. It is implicitly already taken care of by the loop that will not make any iterations in that case.