gpt4 book ai didi

python - 有向图并行排序

转载 作者:行者123 更新时间:2023-12-04 01:06:29 25 4
gpt4 key购买 nike

我有这种具有多个根的有向无环图:

DiGraph

我需要得到一个列表,其中包含按方向排序并按步骤分组的节点,如下所示:

ordering = [
[1, 3],
[2],
[4],
[5, 6],
[7]
]

也许有一些现成的算法?我试过 networkx.algorithm但他们都只能返回一个没有按步骤分组的平面列表。

最佳答案

nx.topological_sort 几乎做你想做的;唯一的区别是它不会对同时进入队列的项目进行分组,但可以直接适应 the source让它这样做:

def topological_sort_grouped(G):
indegree_map = {v: d for v, d in G.in_degree() if d > 0}
zero_indegree = [v for v, d in G.in_degree() if d == 0]
while zero_indegree:
yield zero_indegree
new_zero_indegree = []
for v in zero_indegree:
for _, child in G.edges(v):
indegree_map[child] -= 1
if not indegree_map[child]:
new_zero_indegree.append(child)
zero_indegree = new_zero_indegree

以你的例子:
In [21]: list(nx.topological_sort(G))
Out[21]: [3, 1, 2, 4, 6, 7, 5]

In [22]: list(topological_sort_grouped(G))
Out[22]: [[1, 3], [2], [4], [5, 6], [7]]

在实践中,我不得不怀疑是否存在这种构造比仅使用 nx.topological_sort 更有用的情况。 (或 nx.lexicographical_topological_sort )直接?

关于python - 有向图并行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56802797/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com