在networkx中遍历图的层次顺序

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')])

关于树：借用自这个问题的数据：

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

我正在使用networkx.DiGraph来实现这一目的，并成功创建了该图。以下是我创建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
....
...
..
.

在查看了网络X在线文档之后，现在我可以通过对依赖树进行拓扑排序来实现级别顺序输出，以下是代码。

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'] 

- askb

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}

- Aric

---

感谢您的努力，我已经更新了问题并提供了更多信息。您的示例非常接近我所寻找的内容。您能否重新查看我的更新问题？任何建议都将不胜感激。 - askb

我更新了答案。你可以使用 networkx.single_source_shortest_path_length 来获取从根节点到其他节点的距离。 - Aric

不确定那是否能解决我的问题，我需要的是树中的节点和层级。无论如何，让我检查一下。 - askb

我所写的内容提供了“树中的节点和层级”，例如，节点'n131'位于第3层。 - Aric

如果我不知道源节点怎么办？ - Hanan Shteingart

Answer 2

你还可以使用bfs_layers，它非常方便，可以同时处理所有深度的节点。

import networkx as nx

G = nx.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")])

for level in nx.bfs_layers(G, "n"):
    print(level)

输出结果为

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

- Josmoor98