CODEWITHSUNDEEP
pythonnetworkxgraph-theory
sol
sol

Reputation: 1470

Count the number of nodes and edges in each subgraph connected to one node in a weighted undirected graph with networkx

Let's consider one weighted undirected graph G. Has Networkx an optimised method to get the number of nodes and edges of each subgraph connected to one focused node?

import networkx as nx
import matplotlib.pyplot as plt

listcolor = ['darkblue', 'blue', 'darkred', 'red', 'darkgreen', 'lime', 'gold', 'yellow', 'darkslateblue', 'darkorchid', 'darkorange', 'orange']

G = nx.Graph()

G.add_edge('A', 'B', weight= 1)
G.add_edge('A', 'J', weight= 2)
G.add_edge('K', 'L', weight= 4)
G.add_edge('E', 'F', weight= 7)
G.add_edge('I', 'J', weight= 8)
G.add_edge('B', 'K', weight= 9)
G.add_edge('B', 'E', weight= 17)
G.add_edge('A', 'C', weight= 19)
G.add_edge('H', 'K', weight= 19)
G.add_edge('G', 'H', weight= 20)
G.add_edge('D', 'H', weight= 22)

pos = nx.spring_layout(G, seed=2)
nx.draw(G,node_color = listcolor, with_labels = True)
plt.tight_layout()
plt.axis("off")
plt.show()

For example, let's consider the node B: it has three subgraphs connected, one with 5 nodes (including K,L,D,H,G), one with 4 nodes (including C,A,J,I) and one with 2 nodes (including F,E). Now, imagine I need to get the same list of subgraphs and for each its number of nodes, whatever the considered node (K for another example). How to get this list of subgraphs and their number of nodes and edges efficiently from G? enter image description here

Upvotes: 1

Views: 1487

Answers (1)

sol
sol

Reputation: 1470

Thank to Paul Brodersen which showed me the way to this solution with his rapid comment:

import networkx as nx
import matplotlib.pyplot as plt
import copy

def GetSubGAtt(g,fn):   # get subgraphs attributes : g: a graph, fn: focal node
      wg = copy.deepcopy(g)  # working graph
      wg.remove_node(fn)
      LSubG = list(nx.connected_components(wg)) # get the subgraphs
      dictr = {}   # a dict of results {neighbor node:number of nodes in its subgraph}
      neig = list(g.adj[fn])   # get the neighbors
      for i,j in enumerate(LSubG):
            l=len(j)
            k=set(neig) & set(j)
            dictr[list(k)[0]]=len(j)
      return dictr


listcolor = ['darkblue', 'blue', 'darkred', 'red', 'darkgreen', 'lime', 'gold', 'yellow', 'darkslateblue', 'darkorchid', 'darkorange', 'orange']

G = nx.Graph()

G.add_edge('A', 'B', weight= 1)
G.add_edge('A', 'J', weight= 2)
G.add_edge('K', 'L', weight= 4)
G.add_edge('E', 'F', weight= 7)
G.add_edge('I', 'J', weight= 8)
G.add_edge('B', 'K', weight= 9)
G.add_edge('B', 'E', weight= 17)
G.add_edge('A', 'C', weight= 19)
G.add_edge('H', 'K', weight= 19)
G.add_edge('G', 'H', weight= 20)
G.add_edge('D', 'H', weight= 22)

result = GetSubGAtt(G,'B')

print(result)

GetSubGAtt() returns a dictionary of the subgraph connected to one focal node and the number of nodes in these subgraphs.

Upvotes: 1

Related Questions