How to store values from a recursive graph function?

Question

I have the following recursive function - The function works well to print out all the paths of a tree/graph. But trying to add ROUTES as a global variable and appending to it results in a bunch of empty nested lists: [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [],...etc

A better solution to using a global variable and a better solution to storing the paths is what I'm looking for and this is my function:

 def printAllPathsUtil(self, u, d, visited, path):
        # Mark the current node as visited and store in path
        visited[u] = True
        path.append(u)
        # If current vertex is same as destination, then print
        # current path[]
        if u == d:
            print(path)
            ROUTES.append(path)
        else:
            # If current vertex is not destination
            # Recur for all the vertices adjacent to this vertex
            for i in self.graph[u]:
                if visited[i] == False:
                    self.printAllPathsUtil(i, d, visited, path)
                    # Remove current vertex from path[] and mark it as unvisited

        path.pop()
        visited[u] = False

ROUTES.append(i for i in path) Seems to output [<generator object Graph.printAllPathsUtil.<locals>.<genexpr> at 0x03B27F30>, <generator object Graph.printAllPathsUtil.<locals>.<genexpr> at 0x03B27F70>, <generator object Graph.printAllPathsUtil.<locals>. — leopardxpreload
– leopardxpreload, Commented Mar 1, 2020 at 23:56

Alain T. · Accepted Answer · 2020-03-02 00:16:57Z

1

The source of your problem is that the path variable you are adding to ROUTES is a reference to the same object that you are using to control the traversal. This same object is added every time you find a destination so, when the process is over (and path is empty again), your ROUTE list contains multiple references to the (now empty) path object.

Your correction ROUTES.append([i for i in path]) creates a new instance of the path variable to store in the ROUTES list. That's why it works.

It is a common mistake in Python to store lists in variables assuming that you are holding a copy when in fact it is only a reference and the content may be modified by other parts of the program that change the original.

Note that you could also use ROUTES.append(path.copy()) or ROUTES.append(list(path)) or ROUTES.append([*path])

edited Mar 2, 2020 at 0:16

answered Mar 2, 2020 at 0:09

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to store values from a recursive graph function?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related