計算指定距離或更少的節點數

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從源廣度優先搜索接班人的回報字典。

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

我do't知道如何使用這個來計算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做你想做的。從該文檔：

返回誘導在節點N A 給定半徑內的中心鄰居子圖。

從這個子圖你可以得到任何其他圖中的節點。

下面是一個基於你的代碼的例子。它打印距節點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']