我正在尝试转换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')])
Tree:借用了this的数据question https://stackoverflow.com/questions/21866902/networkx-graph-searches-dfs-successors-vs-dfs-predecessors:
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
output:
['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']