networkx中图形的遍历级别顺序 [英] Traversing level order for the graph in networkx
问题描述
我试图将DiGraph
转换为n元树,并以级别顺序或BFS显示节点.我的树与此相似,但更大,为了简单起见,使用以下示例:
I am trying to convert a DiGraph
into n-ary tree and displaying the nodes in level order or BFS. My tree is similar to this, but much larger, for simplicity using this example:
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: borrowed the data from this question:
n---->n1--->n11
| |--->n12
| |--->n13
| |--->n131
|--->n2
| |---->n21
| |---->n22
| |--->n221
|--->n3
我正在为此目的使用networkx.DiGraph
并成功创建了图形.这是我创建DiGraph的代码:
I am using networkx.DiGraph
for this purpose and created the graph successfully. Here is my code for creating a 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条边.
I am reading the all the data from a file with about 200 lines in the following format and trying to get a dependency tree. My graph is around 100 nodes with 600 edges.
AAA: BBB,CCC,DDD,
BBB:
DDD: EEE,FFF,GGG,KKK
GGG: AAA,BBB,III,LLL
....
...
..
.
在线查看了networkx文档之后,现在我可以使用以下代码对依赖项树进行拓扑排序,从而获得级别顺序输出.
After looking into the networkx docs online, now I can achieve the the level order output doing a topological sort on the dependency tree, with the below code.
order = nx.topological_sort(G)
print "topological sort"
print order
输出:
['n2', 'n3', 'n1', 'n21', 'n22', 'n11', 'n13', 'n12', 'n221', 'n131']
顺序似乎是正确的,但是由于我需要分批处理作业(这样可以节省时间),而不是按顺序处理,因此我希望按级别排序的输出批次或使用BFS进行输出.实现此目标的最佳方法是什么?
例如:level [0:n],例如:
The order seems correct, but since I need to process the jobs in a batch (which saves time) and not sequentially, I want the output in level ordered output batches or using BFS. What is the best way to achieve this ?
ex: level[0:n], ex:
0. ['n']
1. ['n2', 'n3', 'n1',]
2. ['n21', 'n22', 'n11',]
3. ['n13', 'n12', 'n221', 'n131']
推荐答案
您可以使用bfs_edges()函数以广度优先搜索的顺序获取节点列表.
You could use the bfs_edges() function to get a list of nodes in a breadth-first-search order.
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}
这篇关于networkx中图形的遍历级别顺序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!