Depth in Directed Graph: Finding nodes at k distance from a given node

Question

I am trying to find nodes at k distance from a given node using a function.

This is the code I have:

def depth(graph, start, k):
    def levels(graph, start, visited, current_nodes, k):
        #base case
        if k == 0:
            return current_nodes
        else:
            current_nodes = []
        #if no neighbors, return
        if graph.adjacent_nodes(start) == []:
            return []
        for nodes in graph.adjacent_nodes(start):
            if nodes not in visited:
                visited.append(nodes)
            current_nodes.append(nodes)
        print("visited =", visited)
        print("current_nodes =", current_nodes)
        print("k =", k)
        for nodes in current_nodes:
            return levels(graph, nodes, visited, current_nodes, k-1)

    visited = [start]
    current_nodes = []
    required_nodes = levels(graph, start, visited, current_nodes, k)
    print(required_nodes)
    return required_nodes

This works how it is supposed to in Spyder, but for my online course it is not (I have just begun learning). I am printing the visited, current_nodes and k to see what is happening.

For example for a->b->c->d for start = a and k = 5, it should return an empty list meaning there are no nodes at distance 5 from a. The output from Spyder is as follows:

visited = ['a', 'b']
current_nodes = ['b']
k = 5
visited = ['a', 'b', 'c']
current_nodes = ['c']
k = 4
visited = ['a', 'b', 'c', 'd']
current_nodes = ['d']
k = 3
[]

However, for the online course, the output is as follows:

visited =  ['A', 'B']
current_nodes =  ['B']
k =  5
visited =  ['A', 'B', 'C']
current_nodes =  ['C']
k =  4
visited =  ['A', 'B', 'C', 'D']
current_nodes =  ['D']
k =  3
[]
visited =  ['A', 'B']
current_nodes =  ['B']
k =  4
visited =  ['A', 'B', 'C']
current_nodes =  ['C']
k =  3
visited =  ['A', 'B', 'C', 'D']
current_nodes =  ['D']
k =  2
[]
visited =  ['A', 'B']
current_nodes =  ['B']
k =  3
visited =  ['A', 'B', 'C']
current_nodes =  ['C']
k =  2
visited =  ['A', 'B', 'C', 'D']
current_nodes =  ['D']
k =  1
['D']
visited =  ['A', 'B']
current_nodes =  ['B']
k =  2
visited =  ['A', 'B', 'C']
current_nodes =  ['C']
k =  1
['C']
visited =  ['A', 'B']
current_nodes =  ['B']
k =  1
['B']
[]
visited =  ['A', 'B', 'D']
current_nodes =  ['B', 'D']
k =  3
visited =  ['A', 'B', 'D', 'C']
current_nodes =  ['C']
k =  2
visited =  ['A', 'B', 'D', 'C']
current_nodes =  ['D']
k =  1
['D']

Can someone tell me if there is something wrong with my code?

Answer 1

The issue was that current_nodes should not append the nodes if they have already been visited. And after checking for the adjacent nodes, if current_nodes is empty, then there is nothing else to do, so an empty list is returned (indicating that no node is found at k distance).

def depth(graph, start, k):
    def levels(graph, start, visited, current_nodes, k):
        '''BASE CASE'''
        if k == 0:
            return current_nodes
        else:
            current_nodes = []
        '''IF NO NEIGHBORS, RETURN AN EMPTY LIST'''
        if graph.adjacent_nodes(start) == []:
            return []
        for nodes in graph.adjacent_nodes(start):
            if nodes not in visited:
                visited.append(nodes)
                current_nodes.append(nodes)
        print("visited = ", visited)
        print("current_nodes = ", current_nodes)
        print("k = ", k)
        '''IF ALL ADJACENT NODES ALREADY VISITED, CURRENT NODES WILL BE EMPTY, RETURN []'''
        if current_nodes == []:
            return []
        '''RECURSION'''
        for nodes in current_nodes:
            return levels(graph, nodes, visited, current_nodes, k-1)

    visited = [start]
    current_nodes = []
    required_nodes = levels(graph, start, visited, current_nodes, k)
    print(required_nodes)
    return required_nodes