Search code examples
pythongraphnetworkxedgesconnected-components

Finding Number of Edges on Strongly Connected Component

I have a network graph by name Gmedium, and I've found the largest strongly connected component by this code:

maxstmed = max(nx.strongly_connected_components(Gmedium), key=len)

My question is, how do you find number of edges of this connected network? If you try to find the number of nodes, I have it like this:

newGm = nx.Graph()
newGm.add_nodes_from(list(maxstmed))
newGm.number_of_nodes()

But you can't apply this for edges, as it returns 0 when I used add_edges_from and number_of_edges. I tried to count it manually by this:

count = 0
for u in list(newGm.nodes):
    for v in list(newGm.nodes):
        if u == v:
            continue
        if nx.has_path(Gmedium,u,v) == True:
            count += 1
print(count)

But, for a big network (with over 10.000 nodes), it takes forever. Anyone knows the algorithm or function to handle it efficiently? I am using Python Ver. 3 in Spyder environment. Thank you.

Solution

  • You can use a subgraph function to extract a subgraph with given nodes from the original graph. You send a collection of nodes as attribute and it returns you a subgraph of original graph with these nodes and edges between them:

    G = nx.fast_gnp_random_graph(30, 0.04, directed=True, seed=1)
nx.draw(G)

    enter image description here

    C = max(nx.strongly_connected_components(G), key=len)
print(C)

    {0, 3, 4, 6, 8, 10, 11, 15, 21, 22, 24, 25}

    S = G.subgraph(C)
nx.draw(S)

    enter image description here

    print(list(nx.edges(S)))

    [(0, 3), (3, 4), (3, 21), (4, 6), (6, 11), (6, 15), (8, 0), (10, 6), (11, 8), (11, 15), (15, 24), (15, 25), (21, 8), (21, 22), (21, 15), (22, 24), (22, 25), (22, 15), (24, 10), (25, 0)]