CODEWITHSUNDEEP
pythonrecursiongraph
Mohammad Abdollahi
Mohammad Abdollahi

Reputation: 55

Recursive function to calculate simple path from start to end in a graph

I wrote a recursive function to find a simple path in a graph (there exists only one path), given list of graph edges as tuples. for example:

edges = [(0, 10),(2, 16),(4, 5),(6, 24),(7, 6),(8, 23),(9, 25),(10, 14),(11, 1),(12, 19),(13, 22),(14, 15),(15, 11),(16, 7),(17, 21),(18, 13),(19, 17),(20, 8),(21, 3),(22, 20),(23, 12),(24, 9),(25, 18)]

def get_path(sol, start, end):
    out = []
    for i,j in sol:
        if i == start:
            out.append(i)
            out += get_path(sol, j, end)
        if j == end:
            out.append(j)
    return out

However if I cannot get the end node correctly in my return list. If I remove line 7 and 8 the last node will not be present in my solution, and also if I have those lines in the code I get more than one end node in my solution. As an example:

get_path(edges, 2, 3)
path = [2, 16, 7, 11, 15, 14, 10, 22, 13, 18, 25, 21, 17, 19, 12, 9, 24, 6, 8, 20, 23]

As we can see end node is 3 which should be last element of the list. I highly appreciate your inputs. Thanks

Upvotes: 2

Views: 1528

Answers (2)

trincot
trincot

Reputation: 350310

Each recursive call in your code will have one iteration where j == end is true, and so you will indeed get it added multiple times: just as many as you have recursion depth.

It will work better if you put the end-condition outside of the loop, like this:

if start == end:
    return [start]

So with that little modification your code would look like this:

def get_path(sol, start, end):
    if start == end:
        return [start]
    out = []
    for i,j in sol:
        if i == start:
            out.append(i)
            out += get_path(sol, j, end)
    return out

A few other remarks:

  • You can perform the two list operations in the if block in one go:

       out += [i] + get_path(sol, j, end)

  • It is very inefficient to iterate through the complete list in each recursive call. It would be better to first build a dictionary, keyed by the start number. That way you don't have to iterate to find the corresponding edge.

  • It seems that your code expects the graph to be a chain, without any nodes where you have 2 or more outgoing edges. If that would happen, the if i == start: block would execute multiple times resulting in an awkward output. It is not too hard to cover for such situations as well

Code:

from collections import defaultdict 

def get_path(sol, start, end):
    # Transform to dict
    d = defaultdict(list)
    for i,j in sol:
        d[i] += [j]

    def recur(start):
        if start == end:
            return [start]
        for nxt in d[start]:
            path = recur(nxt)
            if path is not None: 
                return [start] + path
    return recur(start)

edges = [(0, 10),(2, 16),(4, 5),(6, 24),(7, 6),(8, 23),(9, 25),(10, 14),
         (11, 1),(12, 19),(13, 22),(14, 15),(15, 11),(16, 7),(17, 21),
         (18, 13),(19, 17),(20, 8),(21, 3),(22, 20),(23, 12),(24, 9),(25, 18)]

path = get_path(edges, 2, 3)
print (path)

Cyclic graph

Your question is about acyclic graphs since you wrote:

there exists only one path

But for anyone coming here looking for a solution for cyclic graphs, the above solution would need to be extended so it does not get stuck in a cycle. This can be done by marking nodes as visited:

from collections import defaultdict 

def get_path(sol, start, end):
    # Transform to dict
    d = defaultdict(list)
    for i,j in sol:
        d[i] += [j]

    visited = set()
    def recur(start):
        if start == end:
            return [start]
        visited.add(start)
        for nxt in d[start]:
            if nxt not in visited:
                path = recur(nxt)
                if path is not None: 
                    return [start] + path
        visited.remove(start)
    return recur(start)

edges =  [(0,1),(1,0),(0,2),(2,0),(2,3),(3,2)]

path = get_path(edges, 2, 3)
print (path)

Note that neither solutions guarantee that the found path is the shortest. But if it is known that there is only one path, it is a memory efficient algorithm.

If there are multiple paths, then a depth-first search cannot stop the search when it finds a path, as there still might be shorter paths to be found. If on the other hand you use a breadth-first search, then you can stop as soon as you find a path.

Upvotes: 1

yatu
yatu

Reputation: 88236

You can use networkX for that. You can define a network from the edges and obtain the simple paths between two given nodes. I'm using nx.shortest_simple_paths, but you could use all_simple_paths to obtain them all:

import networkx as nx

G=nx.Graph()
G.add_edges_from(edges)
next(nx.shortest_simple_paths(G, 2, 3))
# [2, 16, 7, 6, 24, 9, 25, 18, 13, 22, 20, 8, 23, 12, 19, 17, 21, 3]

Upvotes: 3

Related Questions