Memorising Depth of Recursive Function Inside Class

Question

In order to make my small script working i need to memorise the depth of each recursive function inside a class.

Suppose we have a list of dependencies like this:

package1:
package2: package1
package3: package1 | package2

Which simply means that package1 depends on nothing, package2 depends on package1 and package3 depends on package1 or package2.

I have found problems while trying to implement a counter inside a class. The recursive part consist in entering the current node (self), incrementing the counter by 1, calling the previous node and so on until the top of the graph. I need to count the depth because in the or i need to choose the package with less dependency needed, in this case package1 since it has no dependencies.

What i tried are the following operations:

class Node:
...
counter = 0
def dep_resolve(self, resolved, unresolved):
    unresolved.append(self)
    counter += 1
    for edge in self.edges:
        if edge not in resolved:
            if edge in unresolved:
                raise Exception('Circular')
            edge.dep_resolve(resolved, unresolved)
    resolved.append(self)
    unresolved.remove(self)

the same but with the counter outside the Class;

counter = 0
class Node:
...

and with the counter as global variable. But I still get errors((ie.UnboundLocalError: local variable 'counter' referenced before assignment))

Is there correct way to memorise the dependency in a class?

Answer 1

You might tackle this problem in a different location.

Your packages and dependencies is basically a graph, where the packages are vertices and the dependencies are edges.

Your approach is basically doing a DFS on this graph, which is fine, and can find the depth of each package (though if it's not a tree - you might find a depth which is not the shortest one).

Another approach, which is designed to find the "shortest path" (or minimal depth in your case) is running a BFS, instead.
This is very easy to maintain the current depth of a BFS, and all packages that are of depth k, will be developed together in the algorithm, so it's pretty easy to find the depth using this approach.

python-like Pseudo code for the BFS approach:

q = new queue
q.add((source,0))
visited = {}
visited[source] = 1
while not q.empty():
    (curr,d) = q.poll()
    for each dependency (curr,next):
        if next not in visited:
             visited[next] = 1
             q.add(next,d+1)
             #the depth of next is d+1, do something with it