计算指定距离或更短距离的节点数

Question

我要计算距离种子 r 或更短的节点数 N(r)。

假设我们有以下简单图表：

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 来自源的广度优先搜索中的后继字典。

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

我不知道如何用这个来计算N(r)？我需要这样的东西：

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'

感谢您的任何评论或指导。

Answer 1

你可以用 ego_graph 做你想做的事。来自文档：

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

从这个子图中，您可以像在任何其他图中一样获取节点。

这是一个基于您的代码的示例。它打印距节点 b.

距离为 2（或更小）的所有节点

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())

输出：

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

计算指定距离或更短距离的节点数

count number of nodes with a specified distance or less

python

graph

networkx