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

Question

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)

Picture of the resulting graph

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])

What does your result look like for your current solution? Can you provide the actual code you described in that last paragraph? — wwii
– wwii, Commented Sep 27, 2019 at 15:37
Use the existing functions: networkx.github.io/documentation/stable/reference/algorithms/… — Dan D.
– Dan D., Commented Sep 27, 2019 at 15:55
@wwii I have added the code from the last part. @Dan D. nx.connected_components does not work because the graph is directed. I have tried nx.strongly_connected_components, but this results in a list of all node numbers of the graph, not only the node numbers of the node list. I am not sure why. — Zasu
– Zasu, Commented Sep 27, 2019 at 16:08
Could you provide an example graph, where casting the graph to an undirected graph and then computing the connected components would result in a different result than your desired output? — Paul Brodersen
– Paul Brodersen, Commented Sep 27, 2019 at 16:48
Is there a reason you want to keep this as a DiGraph? Since "each edge is bidirectional" you could easily cast this as a Graph. — ComplexGates
– ComplexGates, Commented Sep 27, 2019 at 21:47

ComplexGates · Accepted Answer · 2019-10-02 01:03:36Z

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]]

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related