How to get node neighbors by using recursion?

Question

I very new with recursion function and i try to get node neighbors in graph by using recursion function and graph is look like this.

The Sequence that i want to get neighbors of each node in this graph.

First, get neighbors of first tree node on the top.

sub_node = [
             [D, E, F], #A neighbors
             [F, G, H], #B neighbors
             [H, I],    #C neighbors
            ]

Here is my problem

Next, get neighbors of previous neighbors and the order to get node neighbors is do with first index of all list first (list in sub_node), then do with the next index of all list again until out of index. if do with sub_node will have the output like this.

sub_node = [ 
             #first
             [D, E, F], #A neighbors
             [F, G, H], #B neighbors
             [H, I],    #C neighbors

             #second --> do with first index in tree list above
             [J, K],    #D neighbors
             [L],       #F neighbors
             [L],       #H neighbors

             # --> second index
             [K, L], #E neighbors
             [G],    #L neighbors
             [M],    #I neighbors

             # --> third index
             [L], #F neighbors
             [L], #H neighbors

            ]

This is my code, and graph libraries that i using is NetworkX. In my function and it much identify initail node first.

import networkx as nx

G = nx.Graph()

G.add_edges_from([('A', 'D'), ('A', 'E'), ('A', 'F'), 
                ('B', 'F'), ('B', 'G'), ('B', 'H'), 
                ('C', 'H'), ('C', 'I'), 
                ('D', 'J'), ('D', 'K'), 
                ('E', 'K'), ('E', 'L'), 
                ('F', 'L'), 
                ('G', 'L'), 
                ('H', 'L'), 
                ('I', 'M')
                ])


def get_neighbors(G, initial_node):
    sub_node = []
    for n in initial_node:
        sub_node.append(list(nx.neighbors(G, n)))


initial_node = ['A', 'B', 'C'] #identify initial node first.
get_neighbors(G, initial_node)

Now i can do only this part.

sub_node = [
             [D, E, F], #A neighbors
             [F, G, H], #B neighbors
             [H, I],    #C neighbors
            ]

And i really don't known how to do the rest past and using recursion function.

user_12197714 · Answer

This method doesn't use recursion, but I think your best bet would be to keep track of the nodes you know about, the nodes you've already checked, and iterate through the nodes you know about but haven't checked yet.

import networkx as nx

# initially setting up the graph
G = nx.Graph()
G.add_edges_from([('A', 'D'), ('A', 'E'), ('A', 'F'), 
                ('B', 'F'), ('B', 'G'), ('B', 'H'), 
                ('C', 'H'), ('C', 'I'), 
                ('D', 'J'), ('D', 'K'), 
                ('E', 'K'), ('E', 'L'), 
                ('F', 'L'), 
                ('G', 'L'), 
                ('H', 'L'), 
                ('I', 'M')
                ])

current_nodes = set(['A', 'B', 'C'])  # our list of known nodes
checked_nodes = set()  # our list of checked nodes

node_neighbors = {}
while len(current_nodes - checked_nodes) > 0:
    # first, randomly select a new node that we know about AND haven't already checked:
    current_node = (current_nodes - checked_nodes).pop()
    # get the neighbors of the node as unique elements:
    neighbors = set(nx.neighbors(G, current_node))

    # add any results we don't already know about to our list of known nodes:
    current_nodes |= neighbors  
    # save our results for this node:
    node_neighbors[current_node] = neighbors
    # finally, mark that we checked the node so we don't check it again:
    checked_nodes.add(current_node)

print(node_neighbors)
# {'C': {'H', 'I'}, 'H': {'C', 'B', 'L'}, 'B': {'G', 'F', 'H'}, 'L': {'G', 'F', 'E', 'H'}, 'A': {'F', 'E', 'D'}, 'D': {'A', 'K', 'J'}, 'J': {'D'}, 'K': {'E', 'D'}, 'G': {'B', 'L'}, 'F': {'B', 'A', 'L'}, 'E': {'A', 'K', 'L'}, 'I': {'M', 'C'}, 'M': {'I'}}

How to get node neighbors by using recursion?

1 Answers