CODEWITHSUNDEEP
pythonpython-3.xlistrecursion
leopardxpreload
leopardxpreload

Reputation: 768

How to store values from a recursive graph function?

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

Upvotes: 0

Views: 154

Answers (1)

Alain T.
Alain T.

Reputation: 42143

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])

Upvotes: 1

Related Questions