有向图并行排序

Question

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

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

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

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

Answer 1

nx.topological_sort几乎做你想做的；唯一的区别是它不会对同时进入队列的项目进行分组，但是调整源以使其这样做很简单：

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)更有用的情况？

Answer 2

尝试NetworkX 的拓扑生成

DG = nx.DiGraph([(1,2), (2,4), (3,4), (4,5), (4,6), (6,7)])
[sorted(generation) for generation in nx.topological_generations(DG)]

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