Class TopologicalSortUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.TopologicalSortUtil
public final class TopologicalSortUtil extends Object
Topological Sort Util 拓扑排序工具类

Utility class for topological sorting of directed acyclic graphs (DAG).

有向无环图（DAG）拓扑排序的工具类。

Algorithms | 算法:

  • Kahn's algorithm (BFS-based) | Kahn算法（基于BFS）
  • DFS-based algorithm | 基于DFS的算法

Time Complexity | 时间复杂度: O(V + E)

Space Complexity | 空间复杂度: O(V)

Features | 主要功能:

  • Kahn's BFS-based topological sort - 基于BFS的Kahn拓扑排序
  • DFS-based topological sort - 基于DFS的拓扑排序
  • Cycle detection with exception reporting - 带异常报告的环检测
  • All valid orderings enumeration - 所有有效排序枚举

Usage Examples | 使用示例:

// Topological sort
List<String> order = TopologicalSortUtil.sort(dag);

// Get all valid topological orderings
List<List<String>> allOrders = TopologicalSortUtil.allSorts(dag);

Security | 安全性:

  • Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
  • Null-safe: Yes (returns empty results for null inputs) - 空值安全: 是（null输入返回空结果）

Performance | 性能特性:

  • Time complexity: O(V + E) - 时间复杂度: O(V + E)
  • Space complexity: O(V) - 空间复杂度: O(V)
Since:
JDK 25, opencode-base-graph V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V> boolean
    canSort(Graph<V> graph)
    Check if a valid topological ordering exists 检查是否存在有效的拓扑排序
    static <V> Map<V,Integer>
    getDependencyDepths(Graph<V> graph)
    Get the dependency depth (longest path length) for each vertex 获取每个顶点的依赖深度（最长路径长度）
    static <V> Set<V>
    getSinkVertices(Graph<V> graph)
    Get vertices with no dependents (out-degree 0) 获取无被依赖的顶点（出度为0）
    static <V> Set<V>
    getSourceVertices(Graph<V> graph)
    Get vertices with no dependencies (in-degree 0) 获取无依赖的顶点（入度为0）
    static <V> List<V>
    sort(Graph<V> graph)
    Topological sort using Kahn's algorithm 使用Kahn算法进行拓扑排序
    static <V> List<V>
    sortDfs(Graph<V> graph)
    Topological sort using DFS 使用DFS进行拓扑排序

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • sort

      public static <V> List<V> sort(Graph<V> graph)
      Topological sort using Kahn's algorithm 使用Kahn算法进行拓扑排序
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the directed graph | 有向图
      Returns:
      list of vertices in topological order | 拓扑顺序的顶点列表
      Throws:
      GraphException - if graph is not directed | 如果图不是有向图则抛出异常
      CycleDetectedException - if graph contains a cycle | 如果图包含环则抛出异常

    • sortDfs

      public static <V> List<V> sortDfs(Graph<V> graph)
      Topological sort using DFS 使用DFS进行拓扑排序
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the directed graph | 有向图
      Returns:
      list of vertices in topological order | 拓扑顺序的顶点列表
      Throws:
      GraphException - if graph is not directed | 如果图不是有向图则抛出异常
      CycleDetectedException - if graph contains a cycle | 如果图包含环则抛出异常

    • canSort

      public static <V> boolean canSort(Graph<V> graph)
      Check if a valid topological ordering exists 检查是否存在有效的拓扑排序
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      true if topological ordering exists (graph is DAG) | 如果存在拓扑排序（图是DAG）返回true

    • getSourceVertices

      public static <V> Set<V> getSourceVertices(Graph<V> graph)
      Get vertices with no dependencies (in-degree 0) 获取无依赖的顶点（入度为0）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      set of vertices with no incoming edges | 无入边的顶点集合

    • getSinkVertices

      public static <V> Set<V> getSinkVertices(Graph<V> graph)
      Get vertices with no dependents (out-degree 0) 获取无被依赖的顶点（出度为0）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      set of vertices with no outgoing edges | 无出边的顶点集合

    • getDependencyDepths

      public static <V> Map<V,Integer> getDependencyDepths(Graph<V> graph)
      Get the dependency depth (longest path length) for each vertex 获取每个顶点的依赖深度（最长路径长度）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      map of vertex to its dependency depth | 顶点到其依赖深度的映射