CODEWITHSUNDEEP
pythongraphnetworkxcentralized
Lion Kuo
Lion Kuo

Reputation: 239

Largest weakly connected component in networkX

I have two questions.

  1. In undirected graph, I want to find the largest connected component. And I read the API documents of networkX, finding this function nx.connected_component_subgraphs(). But I don't know how to use it, since its return value is a generator and I cant derive a subgraph of largest connected component.

  2. It is same as one. But the graph is directed. And I want to find the largest weakly connected component of directed graph. Therefore, I use nx.weakly_connected_component_subgraphs(), this function. There has a same problem in question 1.

How can I use the built-in function in networkX to find the largest connected component in undirected graph and the largest weakly connected component in directed graph?

I use NetworkX 1.9.1.

Upvotes: 8

Views: 8389

Answers (2)

Ariel A
Ariel A

Reputation: 604

Currently, the solution offered no longer works since weakly_connected_component_subgraphs has been deprecated on networkx.

TLDR: use subgraph(original_graph, weakly_connected_component_set)

Instead of using an older version of networkx, it's possible to get the largest weakly connected component by doing the following:

#create an example graph
import networkx as nx
G = nx.lollipop_graph(10, 5)
G = G.to_directed() #weakly connected component needs a directed graph.

You can collect all of the weakly connected subgraphs or you can select the maximum subgraph by doing the following:

#list of all weakly connected subgraphs, each one is a set. 
#If you don't list them, you'll get a generator.
list_of_subgraphs = list(nx.weakly_connected_components(G))

list_of_digraphs = []

for subgraph in list_of_subgraphs:
    list_of_digraphs.append(nx.subgraph(G, subgraph)) #this is the relevant part.

Each one of those subgraphs will now be an nx digraph stored in list_of_digraphs.

If you want the max weakly connected subgraph,

max_wcc = max(nx.weakly_connected_components(G), key=len)
max_wcc = nx.subgraph(G, max_wcc)

Upvotes: 1

Aric
Aric

Reputation: 25319

The NetworkX component functions return Python generators. You can create a list of items in the generator using the Python list function. Here is an example showing that and also finding the largest weakly connected component.

In [1]: import networkx as nx

In [2]: G = nx.DiGraph()

In [3]: G.add_path([1,2,3,4])

In [4]: G.add_path([10,11,12])

You can use e.g. list to turn the generator into a list of subgraphs:

In [5]: list(nx.weakly_connected_component_subgraphs(G))
Out[5]: 
[<networkx.classes.digraph.DiGraph at 0x278bc10>,
 <networkx.classes.digraph.DiGraph at 0x278ba90>]

The max operator takes a key argument which you can set to the Python function len which calls len(g) on each subgraph to compute the number of nodes. So to get the component with the largest number of nodes you can write

In [6]: largest = max(nx.weakly_connected_component_subgraphs(G),key=len)

In [7]: largest.nodes()
Out[7]: [1, 2, 3, 4]

In [8]: largest.edges()
Out[8]: [(1, 2), (2, 3), (3, 4)]

Upvotes: 7

Related Questions