[FIXED] How can I find connected components in a directed graph using a list of nodes as input?

Issue

I have a directed graph G, created using networkX in Python. Each edge is bidirectional. I have a certain list of nodes and I am trying to find the connected components within these nodes. Below I have created a sample dataset (the actual graph I am dealing with is much larger).

import networkx as nx
G = nx.DiGraph()
nodeList = range(1,10)

for i in range (0,len(nodeList)):
    G.add_node(nodeList[i])

o_nodes = [1,1,2,3,3,3,3,4,4,5,5,6,7,7,8,9,9,10]
d_nodes = [8,3,3,1,7,2,4,5,3,4,6,5,3,9,1,7,10,9]

for i in range(0, len(o_nodes)):
    G.add_edge(o_nodes[i], d_nodes[i])  
    
nx.draw(G, with_labels = True)

Let's say I have a list of nodes, selectNodeList = [1,2,5,6,7,8,9,10], and I need to find the connected components within these nodes. So, as a result I'd like to get something like [8,1], [7,9,10], [2], [5,6]. I want to get the minimum number of components needed to cover all nodes from the select node list.

I have tried something using a for loop with if nx.shortest_path_length(G, source = selectNodeList[i], target = selectNodeList[j]) == 1: and then append to a list to get the direct neighbors of each node, but I am not sure how to get to the neighbor after that and how to create a readable output.

EDIT: this is the code I have mentioned in the last part. I was reluctant to add it as it is not completely finished. My way of thinking was to first get two nodes that are direct neighbors, and then search for another node that is also a direct neighbor to one of these nodes, and so on. However, this does not output nodes that are not connected at all and it results in a list with duplicate connected nodes (for example [1 8 1 8 1 8 5 6 5 6 ...]. One problem for me is that I don't know how to deal with creating outputs that will not be of the same dimension and how I can solve the problem without creating a very large amount of for-loops.

connected = []
for i in range(0,34):
    for j in range (1,34):
        if nx.shortest_path_length(G, source = selectNodeList[i], target = selectNodeList[j]) == 1:
            connected.append(selectNodeList[i])
            connected.append(selectNodeList[j])
            for k in range(2,34):
                if nx.shortest_path_length(G, source = selectNodeList[j], target = selectNodeList[k]) == 1:
                    connected.append(selectNodeList[k])
                    for l in range (3,34):
                        if nx.shortest_path_length(G, source = selectNodeList[k], target = selectNodeList[l]) == 1:
                            connected.append(selectNodeList[l])
                            for m in range(4,34):
                                if nx.shortest_path_length(G, source = selectNodeList[l], target = selectNodeList[m]) == 1:
                                    connected.append(selectNodeList[m])

Solution

You need to find the connected components (either weak or strong, it doesn't matter since all of your edges are bidirectional) in the subgraph induced by your node subset.

node_subset = [1,2,5,6,7,8,9,10]
[list(cc) for cc in nx.strongly_connected_components(G.subgraph(node_subset))]

[[8, 1], [2], [5, 6], [9, 10, 7]]

Answered By - ComplexGates

Answer Checked By - Timothy Miller (PHPFixing Admin)