pythongraphnetworkxcentralized

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.

Solution

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