CODEWITHSUNDEEP
pythongraphnetworkx
Abolfazl
Abolfazl

Reputation: 453

count number of nodes with a specified distance or less

I am going to count the number of nodes N(r) with distance r or less from a seed.

suppose we have the following simple graph:

enter image description here

G = nx.Graph()
G.add_nodes_from(['a','b','c','d','e','f','g','h'])
G.add_edges_from([('a','b'),('a','c'),('b','d'),('b','e'),
                  ('e','h'),('c','f'),('c','g')])

bfs_successors return dictionary of successors in breadth-first-search from source.

print nx.bfs_successors(G,'b')
{'a': ['c'], 'c': ['g', 'f'], 'b': ['a', 'e', 'd'], 'e': ['h']}

I do't know how to use this to calculate N(r)? I need sth like this:

seed='b'
r=1,           'a','e','d'     , N = 3
-----------------------------------
r<=2,          'a','c'         , N = 5
               'e','h'    
               'd',
-----------------------------------
r<=3,          'a','c','f','g' , N = 7
               'e', 'h',
               'd'

Thank you for any comment or guide.

Upvotes: 0

Views: 567

Answers (1)

edo
edo

Reputation: 1879

You can do what you want with ego_graph. From the docs:

Returns induced subgraph of neighbors centered at node n within a given radius.

From this subgraph you can get the nodes as in any other graph.

Here's an example based on your code. It prints all nodes at distance 2 (or less) from node b.

import networkx as nx

G = nx.Graph()
G.add_nodes_from(['a','b','c','d','e','f','g','h'])
G.add_edges_from([('a','b'),('a','c'),('b','d'),('b','e'),
                  ('e','h'),('c','f'),('c','g')])

ego = nx.ego_graph(G, 'b', radius=2, center=False)
print(ego.nodes())

Output:

['d', 'c', 'h', 'a', 'e']

Upvotes: 3

Related Questions