网络中的图形的遍历级别顺序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}