網絡中的圖形的遍歷級別順序x

Question

我試圖將DiGraph轉換爲n元樹並按級別順序或BFS顯示節點。我的樹與此類似，但要大，使用這個例子簡單：

G = networkx.DiGraph() 
G.add_edges_from([('n', 'n1'), ('n', 'n2'), ('n', 'n3')]) 
G.add_edges_from([('n4', 'n41'), ('n1', 'n11'), ('n1', 'n12'), ('n1', 'n13')]) 
G.add_edges_from([('n2', 'n21'), ('n2', 'n22')]) 
G.add_edges_from([('n13', 'n131'), ('n22', 'n221')]) 

樹：從這個question借來的數據：

n---->n1--->n11 
|  |--->n12 
|  |--->n13 
|   |--->n131 
|--->n2    
|  |---->n21  
|  |---->n22  
|   |--->n221 
|--->n3 

我使用networkx.DiGraph爲此目的而創建的圖成功。這是我創建有向圖碼：

G = nx.DiGraph() 
roots = set() 
for l in raw.splitlines(): 
    if len(l): 
     target, prereq = regex1.split(l) 
     deps = tuple(regex2.split(prereq)) 
     print("Add node:") + target 
     roots.add(target) 
     G.add_node(target) 
     for d in deps: 
      if d: 
       G.add_edge(target, d) 

我從文件中讀取的所有數據與以下格式約200線，並試圖獲得一個依賴關係樹。我的圖形大約有100個有600個邊緣的節點。

AAA: BBB,CCC,DDD, 
BBB: 
DDD: EEE,FFF,GGG,KKK 
GGG: AAA,BBB,III,LLL 
.... 
... 
.. 
. 

展望networkx文檔在線後，我現在可以達到的水平輸出順序上做相關樹拓撲排序，用下面的代碼。

order = nx.topological_sort(G) 
print "topological sort" 
print order 

輸出：

['n2', 'n3', 'n1', 'n21', 'n22', 'n11', 'n13', 'n12', 'n221', 'n131'] 

的順序似乎是正確的，但因爲我需要處理在一個批處理作業（從而節省時間），而不是連續的，我想在一級有序輸出批次輸出或使用BFS。達到此目的的最佳方法是什麼？
例如：水平[0：N]，例如：

0. ['n'] 
1. ['n2', 'n3', 'n1',] 
2. ['n21', 'n22', 'n11',] 
3. ['n13', 'n12', 'n221', 'n131'] 

Answer 1

您可以使用bfs_edges（）函數來獲得在廣度優先搜索順序的節點列表。

In [1]: import networkx 

In [2]: G = networkx.DiGraph() 

In [3]: G.add_edges_from([('n', 'n1'), ('n', 'n2'), ('n', 'n3')]) 

In [4]: G.add_edges_from([('n4', 'n41'), ('n1', 'n11'), ('n1', 'n12'), ('n1', 'n13')]) 

In [5]: G.add_edges_from([('n2', 'n21'), ('n2', 'n22')]) 

In [6]: G.add_edges_from([('n13', 'n131'), ('n22', 'n221')]) 

In [7]: list(networkx.bfs_edges(G,'n')) 
Out[7]: 
[('n', 'n2'), 
('n', 'n3'), 
('n', 'n1'), 
('n2', 'n21'), 
('n2', 'n22'), 
('n1', 'n11'), 
('n1', 'n13'), 
('n1', 'n12'), 
('n22', 'n221'), 
('n13', 'n131')] 

In [8]: [t for (s,t) in networkx.bfs_edges(G,'n')] 
Out[8]: ['n2', 'n3', 'n1', 'n21', 'n22', 'n11', 'n13', 'n12', 'n221', 'n131'] 

In [9]: networkx.single_source_shortest_path_length(G,'n') 
Out[9]: 
{'n': 0, 
'n1': 1, 
'n11': 2, 
'n12': 2, 
'n13': 2, 
'n131': 3, 
'n2': 1, 
'n21': 2, 
'n22': 2, 
'n221': 3, 
'n3': 1}