Straightforward question: I would like to retrieve all the nodes connected to a given node within a NetworkX graph in order to create a subgraph. In the example shown below, I just want to extract all the nodes inside the circle, given the name of one of any one of them.

NetworkX graph

I've tried the following recursive function, but hit Python's recursion limit, even though there are only 91 nodes in this network.

Regardless of whether or not the below code is buggy, what is the best way to do what I'm trying to achieve? I will be running this code on graphs of various sizes, and will not know beforehand what the maximum recursion depth will be.

def fetch_connected_nodes(node, neighbors_list):
    for neighbor in assembly.neighbors(node):
        if len(assembly.neighbors(neighbor)) == 1:
            return neighbors_list
            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)
  • 1
    Is it a directed graph ? or a non directed one ? – Abdallah Sobehy Oct 12 '15 at 19:04
  • @AbdallahSobehy Undirected, although it's debatable whether the data I'm dealing with is directed or not. – Bede Constantinides Oct 12 '15 at 23:01

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

node_connected_component(G, n)

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

It's not recursive, but I don't think you actually need or even want that.

comments on your code: You've got a bug that will often result an infinite recursion. If u and v are neighbors both with degree 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 needs to change to only process neighbors that are not in neighbors_list. It's expensive to check that, so instead use a set. There's also a small problem if the starting node has degree 1. Your test for degree 1 doesn't do what you're after. If the initial node has degree 1, but its neighbor has higher degree it won't find the neighbor's neighbors.

Here's a modification of your code:

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

You call this like fetch_connected_nodes(assembly, starting_node).

  • Superb answer. I'd expected there to be a networkx function to do this but had failed to find it – thank you! The bug in my code seems blindingly obvious. – Bede Constantinides Oct 12 '15 at 23:11

You can simply use a Breadth-first search starting from your given node or any node.

In Networkx you can have the tree-graph from your starting node using the function:

bfs_tree(G, source, reverse=False)

Here is a link to the doc: Network bfs_tree.

  • Thank you Kikhos. Along similar lines I also think [v for u,v in nx.bfs_edges(G, source)] would give me a list of nodes as required. – Bede Constantinides Oct 12 '15 at 23:21

Here is a recursive algorithm to get all nodes connected to an input node.

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

I believe the key thing here to prevent infinite recursive calls is the condition to check that node which is neighbor in the original graph is not already connected in the sub_G that is being created. Otherwise, you will always be going 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)
sub_G = nx.Graph()
nx.draw(sub_G,with_labels = True)

You will find in the attached image, the full graph and the sub_graph that contains node 17.enter image description here

  • Great answer that teaches the algorithm rather than using the built-in library function like @Joel did. Thank you. – Bede Constantinides Oct 12 '15 at 23:24

Your Answer

