Get Connected Nodes in NetworkX Graphics

Question

A simple question: I would like to get all the nodes connected to this node within the NetworkX graph to create a subgraph. In the example below, I just want to extract all the nodes inside the circle, given the name of one of them.

I tried the following recursive function, but fell within the Python recursion limit, although there are only 91 nodes on this network.

Regardless of whether the code below is an error, what is the best way to do what I'm trying to achieve? I will run this code on graphs of different sizes and I won’t know what the maximum recursion depth will be.

def fetch_connected_nodes(node, neighbors_list): for neighbor in assembly.neighbors(node): print(neighbor) if len(assembly.neighbors(neighbor)) == 1: neighbors_list.append(neighbor) return neighbors_list else: neighbors_list.append(neighbor) fetch_connected_nodes(neighbor, neighbors_list) neighbors = [] starting_node = 'NODE_1_length_6578_cov_450.665_ID_16281' connected_nodes = fetch_connected_nodes(starting_node, neighbors) 

Answer 1

Assuming the graph is not oriented, there is a built-in networkx command for this:

 node_connected_component(G, n) 

The documentation is here . It returns all nodes in the associated component G containing n .

This is not recursive, but I don’t think you really need or even need this.

---

comments on your code . You have a bug that often leads to infinite recursion. If u and v are neighbors with a power of at least 2, then it will start with u , put v in the list and, when processing v put u in the list and keep repeating. It should only be changed to handle neighbors that are not in neighbors_list . It's expensive to check, so use a kit instead. There is also a small problem if the starting node has degree 1. Your test for degree 1 does not do what you need. If the initial node has degree 1, but its neighbor has a higher degree, it will not find neighboring neighbors.

Here you can change the code:

 def fetch_connected_nodes(G, node, seen = None): if seen == None: seen = set([node]) for neighbor in G.neighbors(node): print(neighbor) if neighbor not in seen: seen.add(neighbor) fetch_connected_nodes(G, neighbor, seen) return seen 

You name it as fetch_connected_nodes(assembly, starting_node) .

Answer 2

You can simply use the first search on Breadth, starting with a given node or any node.

In Networkx, you can get a tree diagram from your initial node using the function:

 bfs_tree(G, source, reverse=False) 

Here is the link to the document: Network bfs_tree .

Answer 3

Here is a recursive algorithm that allows you to connect all nodes to the node input.

 def create_subgraph(G,sub_G,start_node): sub_G.add_node(start_node) for n in G.neighbors_iter(start_node): if n not in sub_G.neighbors(start_node): sub_G.add_path([start_node,n]) create_subgraph(G,sub_G,n) 

I believe that the key thing to prevent infinite recursive calls is to condition that the node that is adjacent in the source graph is not yet connected in the created sub_G. Otherwise, you will always go back and forth and edges between nodes that already have edges.

I tested it as follows:

 G = nx.erdos_renyi_graph(20,0.08) nx.draw(G,with_labels = True) plt.show() sub_G = nx.Graph() create_subgraph(G,sub_G,17) nx.draw(sub_G,with_labels = True) plt.show() 

You will find in the attached image the full graph and sub_graph containing node 17.