CODEWITHSUNDEEP
pythonrecursiongraphnodes
Gabriel Saul
Gabriel Saul

Reputation: 65

Building a collection across recursive iterations

I am attempting to implement an "all paths" algorithm described in this question's top answer using Python.

So far, I have defined the function as such:

def AllPaths(start, end, edges):
    print(start)
    if (start == end):
        return

    for i in range(0, len(edges)):
        if edges[i][1] == start:
            AllPaths(edges[i][0], end, edges)

I have included print(start) to try give myself an idea of the function's behaviour. For example, if the initial function call is as such:

edges = [ (1, 2), (1, 3), (2, 3), (3, 4) ]
AllPaths(edges[len(edges) - 1][1], edges[0][0], edges)

With the starting node being 4 and the ending node being 1, the output of the function is:

4
3
1
2
1

Somewhere in that output, it is telling me that all paths between node 4 and node 1 consists of:

[ (4, 3), (3, 1) ]
[ (4, 3), (3, 2), (2, 1) ]

But how do I form these collections during execution and, if I wanted to keep track of how many distinct paths there are, how would this be counted during execution?

Upvotes: 0

Views: 40

Answers (1)

Timus
Timus

Reputation: 11331

If you don't mind that I won't follow the backward traversal route, which I find rather odd, then here's a suggestion on how to modify your function to see what's going on:

def all_paths(start, end, edges):
    if start == end:
        return [[end]]
    paths = []
    for edge in edges:
        if edge[0] == start:
            paths += [[start] + path
                      for path in all_paths(edge[1], end, edges)]
    return paths

Output for edges = [(1, 2), (1, 3), (2, 3), (3, 4)] and start = 1; end = 4:

[[1, 2, 3, 4],
 [1, 3, 4]]

If you want a direct edges-result then I'd suggest:

def all_paths(start, end, edges):
    paths = []
    for edge in edges:
        if edge[0] == start:
            if edge[1] == end:
                return [[edge]]
            else:
                paths += [[edge] + path
                          for path in all_paths(edge[1], end, edges)]
    return paths

Output for the same input:

[[(1, 2), (2, 3), (3, 4)],
 [(1, 3), (3, 4)]]

But a warning: If you have loops in the graph, e.g. edges = [(1, 2), (1, 3), (3, 1), (2, 3), (3, 4)], then these algorithms will crash (recursion won't stop). In these cases something like

def all_paths(start, end, edges):
    edges = set(edges)
    paths = []
    for edge in edges:
        if edge[0] == start:
            if edge[1] == end:
                paths += [[start, end]]
            else:
                new_edges = edges.difference({edge})
                paths += [[start] + path
                          for path in all_paths(edge[1], end, new_edges)]
    return paths

which removes visited edges is better. Result for start = 1; end = 4:

[[1, 2, 3, 1, 3, 4],
 [1, 2, 3, 4],
 [1, 3, 1, 2, 3, 4],
 [1, 3, 4]]

I hope that this is at least a little bit what you were looking for.

Upvotes: 1

Related Questions