python - 有向图并行排序

Question

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



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

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

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

Answer 1

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 )直接？