使用JGraphT拓扑排序如何识别等优先级可并行执行顶点？

JGraphT 原生实现方案 #

你要的可并行资源分层输出本质是Kahn拓扑排序算法每一轮迭代输出的所有入度为0的节点集合，JGraphT没有直接提供返回分层结构的拓扑排序API，但可以基于它提供的基础图操作API几十行代码实现，完全不需要引入额外依赖：

实现步骤 #

1. 先校验输入的依赖图是有向无环图(DAG)，这是拓扑排序的前提，可直接用JGraphT内置的CycleDetector完成校验
2. 基于Kahn算法逻辑遍历图，每一轮收集所有入度为0的节点作为可并行创建的同一层资源

代码示例 #

import org.jgrapht.Graph;
import org.jgrapht.alg.cycle.CycleDetector;
import org.jgrapht.graph.DefaultEdge;
import java.util.*;

public class TopologicalLayerResolver {
    public static <T> List<Set<T>> getParallelCreateLayers(Graph<T, DefaultEdge> dag) {
        // 校验是否存在环
        CycleDetector<T, DefaultEdge> cycleDetector = new CycleDetector<>(dag);
        if (cycleDetector.detectCycles()) {
            throw new IllegalArgumentException("依赖图存在环，无法计算创建顺序");
        }
        // 初始化入度统计表
        Map<T, Integer> inDegreeMap = new HashMap<>();
        for (T vertex : dag.vertexSet()) {
            inDegreeMap.put(vertex, dag.inDegreeOf(vertex));
        }
        // 初始化首轮入度为0的节点队列
        Queue<T> zeroInDegreeQueue = new LinkedList<>();
        for (Map.Entry<T, Integer> entry : inDegreeMap.entrySet()) {
            if (entry.getValue() == 0) {
                zeroInDegreeQueue.add(entry.getKey());
            }
        }
        List<Set<T>> resultLayers = new ArrayList<>();
        while (!zeroInDegreeQueue.isEmpty()) {
            int currentLayerSize = zeroInDegreeQueue.size();
            Set<T> currentLayer = new HashSet<>();
            // 处理当前层所有可并行的节点
            for (int i = 0; i < currentLayerSize; i++) {
                T current = zeroInDegreeQueue.poll();
                currentLayer.add(current);
                // 更新下游节点入度
                for (DefaultEdge edge : dag.outgoingEdgesOf(current)) {
                    T target = dag.getEdgeTarget(edge);
                    int newInDegree = inDegreeMap.get(target) - 1;
                    inDegreeMap.put(target, newInDegree);
                    if (newInDegree == 0) {
                        zeroInDegreeQueue.add(target);
                    }
                }
            }
            resultLayers.add(currentLayer);
        }
        return resultLayers;
    }
}

调用上述方法返回的resultLayers就是你需要的分层结果，你举的示例输入会得到[{A,D}, {B}, {C}]的输出，完全匹配需求。

替代图形库推荐 #

如果不想自行实现分层逻辑，可以选择以下内置该能力的Java图形库：

• Guava common.graph：轻量图操作模块，API简洁，适合仅需要基础图能力的项目，基于它也可以快速实现上述分层逻辑
• Apache Commons Graph：提供了封装好的分层拓扑排序接口，不需要自行实现Kahn算法
• JUNG：全功能Java图计算框架，内置大量图算法实现，适合有更多复杂图计算需求的场景

内容的提问来源于stack exchange，提问作者Przemysław Różycki