return the number of nodes in a python file by a path of length

Question

I got a hard problem in python for my last question of project.

Imagine you get a file like it :

1 2
2 3
3 4

• if node 1 is linked to node 2 by an edge then 2 is accessible by a path of length 1 from 1: 1-2

• if 1 is linked to 2 itself to 3 and itself to 4 then 4 is accessible by a path of length 4 from 1: 1-2-3-4

• I want to return the number of nodes accessible from a given node by a path of length 3 by default

thanks for advice and help !!!!

EDIT :

def bfs(graph, start_node, distance):
    if distance == 0:
        return [start_node]
    visited = []
    queue = []
    nodes_at_dist = []

    level = 0
    visited.append(start_node)
    queue.append((start_node, level))

Answer 1

First, we rebuild the data structure to simplify the lookup, i.e., which nodes are reachable. I assume that our graph is undirected.

graph = [(1, 2), (2, 3), (3, 4), (1, 4), (2, 6), (6, 7)]

# we restructure our input to simplify the lookup
graph_dict = {}
for n1, n2 in graph:
    if n1 not in graph_dict:
        graph_dict[n1] = set()
    if n2 not in graph_dict:
          graph_dict[n2] = set()
    graph_dict[n1].add(n2)
    graph_dict[n2].add(n1)

As a result, we have a dict where the keys are all existing nodes and the corresponding value is a set of all nodes which are directly connected:

{1: {2, 4}, 2: {1, 3, 6}, 3: {2, 4}, 4: {1, 3}, 6: {2, 7}, 7: {6}}

The next part is essentially our method which finds the reachable nodes in respect of a fixed distance:

def bfs(graph_dict, start_node, distance):
    # We reached the end and return the current node
    if distance == 0:
        return {start_node}
        
    # We look-up all nodes which are reachable with one step
    reachable = graph_dict[start_node]
        
    # Now we iterate through this set and call our method again (recursively)
    result=set()
    for node in reachable:
        tmp=bfs(graph_dict, node, distance-1)
        result=result.union(tmp)
    return result 

Example Output 1: distance=2, start_node=1

{1, 3, 6}

Please note that "1" is in our result set because we can walk 1-2-1 (which are two steps).

Example Output 2: distance=3, start_node=1

{2, 4, 7}

Please note that "2" is in our result set because we can walk 1-2-1-2 (which are three steps).