CODEWITHSUNDEEP
pythonpython-3.xnetworkxbreadth-first-search
Parth Shah
Parth Shah

Reputation: 63

BFS all paths to specific depth

I'm using networkx library to generate an undirected graph given the parent-child relationship. Given depth x and a starting point for the graph, I can find all the nodes at depth x, but I also want the path taken to get to that node. How do I collect nodes traversed while getting to the path?

Here is my code that gets me all the nodes at depth <= x

def descendants_at_distance(G, source, distance):
    if not G.has_node(source):
        raise nx.NetworkXError(f"The node {source} is not in the graph.")
    current_distance = 0
    current_layer = {source}
    visited = {source}
    layer_with_distance = {}

    while current_distance < distance:
        next_layer = set()
        for node in current_layer:
            # print(G[node])
            for child in G[node]:
                if child not in visited:
                    visited.add(child)
                    next_layer.add(child)
        current_layer = next_layer
        current_distance += 1
        layer_with_distance.update({current_distance: current_layer})
    
    layer_with_distance =  {key:val for (key, val) in layer_with_distance.items() if val}
    return layer_with_distance

The above code is modification to the inbuilt networkx library code since I need all the nodes between depth = 1...x

df_links = [(1,2),(1,3),(1,4),(2,6),(3,9),(4,7),(4,8),(9,7),(9,10),(7,8),(7,10), (15,16)]
Graph = nx.Graph(df_links)

For example above if the source = 1 and distance = 3 the output should be {1: {2, 3, 4}, 2: {8, 9, 6, 7}, 3: {10}} where key = distance and value = nodes at distance.

What I want with this is the nodes traversed at each key-value pair. For example, at depth = 2 the nodes are {8,9,6,7} (order doesn't matter), and the traversed nodes for each are like this. 1-4-8, 1-3-9, 1-2-6, 1-4-7

Let me know if any further clarification is needed.

Upvotes: 1

Views: 361

Answers (1)

Alexander
Alexander

Reputation: 17345

Something like this might work: I added another dictionary that collected each stop along the way and the ouput is identical to what you said it would be (see the bottom for the output)

...
    ...
    layer_with_distance = {}
    tracker = {} # added this
    while current_distance < distance:
        tracker[source] = {} # added this
        next_layer = set()
        for node in current_layer:
            # print(G[node])
            tracker[source][node] = []  # added this
            for child in G[node]:
                if child not in visited:
                    tracker[source][node].append(child) #added this
                    visited.add(child)
                    next_layer.add(child)
        current_layer = next_layer
        current_distance += 1
        layer_with_distance.update({current_distance: current_layer})

    layer_with_distance =  {key:val for (key, val) in layer_with_distance.items() if val}
    return layer_with_distance, tracker # added to this


df_links = [(1,2),(1,3),(1,4),(2,6),(3,9),(4,7),(4,8),(9,7),(9,10),(7,8),(7,10), (15,16)]
Graph = nx.Graph(df_links)
print(descendants_at_distance(Graph, 1, 2))

output

layer_with_distance: {1: {2, 3, 4}, 2: {8, 9, 6, 7}}

tracker: {1: {2: [6], 3: [9], 4: [7, 8]}}

Upvotes: 1

Related Questions