CODEWITHSUNDEEP
pythonpython-3.xgraphnetworkx
Will
Will

Reputation: 1845

Find all possible paths using networkx

how can I find all possible path between two nodes in a graph using networks?

import networkx as nx

G = nx.Graph()
edges = ['start-A', 'start-b', 'A-c', 'A-b', 'b-d', 'A-end', 'b-end']

nodes = []
for node in edges:
    n1 = node.split('-')[0]
    n2 = node.split('-')[1]
    
    if n1 not in nodes:
        nodes.append(n1)
        
    if n2 not in nodes:
        nodes.append(n2)
for node in nodes:
    G.add_node(node)
for edge in edges:
    n1 = edge.split('-')[0]
    n2 = edge.split('-')[1]
    
    G.add_edge(n1, n2)


for path in nx.all_simple_paths(G, 'start', 'end'):
    print(path)

This is the result:

['start', 'A', 'b', 'end']
['start', 'A', 'end']
['start', 'b', 'A', 'end']
['start', 'b', 'end']

But I want all possible path so for e.g. start,b,A,c,A,end

Upvotes: 3

Views: 3275

Answers (1)

SultanOrazbayev
SultanOrazbayev

Reputation: 16581

If repeated visits to a node are allowed, then in a graph where at least 2 nodes on the path (not counting start and end) are connected, there is no upper bound to the number of valid paths. If there are 2 nodes on the path that are connected, e.g. nodes A and B, then any number of new paths can be formed by inserting A->B->A into the appropriate section of the valid path between start and end.

If number of repeated visits is restricted, then one might take the all_simple_paths as a starting point and insert any valid paths between two nodes in between, repeating this multiple times depending on the number of repeated visits allowed.

In your example, this would be taking the third output of all_simple_paths(G, 'start', 'end'), i.e. ['start', 'b', 'A', 'end'] and then for all nodes connected to b iterate over the results of all_simple_paths(G, X, 'A'), where X is the iterated node.

Here's rough pseudocode (it won't work but suggests an algo):

for path in nx.all_simple_paths(G, 'start', 'end'):
    print(path)
    for n, X, Y in enumerate(zip(path, path[1:])):
       if X is not 'start' and X is not 'end':
            for sub_path in nx.all_simple_paths(G, X, Y):
                print(path[:n] + sub_path + path[n+2:])

This is not great, since with this formulation it's hard to control the number of repeated visits. One way to fix that is to create an additional filter based on the counts of nodes. However, for any real-world graphs this is not going to be computationally feasible due to the very large number of paths and nodes...

Upvotes: 3

Related Questions