Class DagUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.DagUtil
public final class DagUtil extends Object
DAG (Directed Acyclic Graph) Utility 有向无环图工具类

Provides operations specific to directed acyclic graphs (DAGs), including longest path (critical path), transitive reduction/closure, and ancestor/descendant queries. All methods verify the input is a DAG before processing.

提供有向无环图（DAG）专用操作，包括最长路径（关键路径）、传递归约/闭包 和祖先/后代查询。所有方法在处理前验证输入是否为DAG。

Features | 主要功能:

  • Longest path (critical path) computation - 最长路径（关键路径）计算
  • Longest path between specific source and target - 指定源和目标之间的最长路径
  • Transitive reduction (remove redundant edges) - 传递归约（移除冗余边）
  • Transitive closure (add implied edges) - 传递闭包（添加隐含边）
  • Ancestor and descendant queries - 祖先和后代查询

Usage Examples | 使用示例:

Graph<String> dag = OpenGraph.directed();
dag.addEdge("A", "B", 2.0);
dag.addEdge("B", "C", 3.0);
dag.addEdge("A", "C", 1.0);

List<String> longest = DagUtil.longestPath(dag);
double length = DagUtil.longestPathLength(dag);

Graph<String> reduced = DagUtil.transitiveReduction(dag);
Graph<String> closure = DagUtil.transitiveClosure(dag);

Set<String> anc = DagUtil.ancestors(dag, "C");   // {"A", "B"}
Set<String> desc = DagUtil.descendants(dag, "A"); // {"B", "C"}

Performance | 性能特性:

  • longestPath: O(V + E) - 时间复杂度: O(V + E)
  • transitiveReduction/Closure: O(V * (V + E)) - 时间复杂度: O(V * (V + E))
  • ancestors/descendants: O(V + E) - 时间复杂度: O(V + E)
Since:
JDK 25, opencode-base-graph V1.0.3
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Details

    • longestPath

      public static <V> List<V> longestPath(Graph<V> graph)
      Find the longest path in the DAG (critical path). 查找DAG中的最长路径（关键路径）。

      Uses topological sort + dynamic programming. Returns vertex sequence of the longest path by edge weight sum. If multiple paths have the same length, any one of them may be returned.

      使用拓扑排序+动态规划。返回按边权重和计算的最长路径的顶点序列。 如果多条路径长度相同，可能返回其中任意一条。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the DAG | 有向无环图
      Returns:
      vertex sequence of the longest path | 最长路径的顶点序列
      Throws:
      GraphException - if graph is not a DAG | 如果图不是DAG则抛出异常

    • longestPath

      public static <V> List<V> longestPath(Graph<V> graph, V source, V target)
      Find the longest path between two specific vertices in the DAG. 查找DAG中两个指定顶点之间的最长路径。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the DAG | 有向无环图
      source - the source vertex | 源顶点
      target - the target vertex | 目标顶点
      Returns:
      vertex sequence of the longest path, or empty list if no path | 最长路径的顶点序列，无路径时返回空列表
      Throws:
      GraphException - if graph is not a DAG | 如果图不是DAG则抛出异常

    • longestPathLength

      public static <V> double longestPathLength(Graph<V> graph)
      Compute the length (sum of edge weights) of the longest path in the DAG. 计算DAG中最长路径的长度（边权重之和）。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the DAG | 有向无环图
      Returns:
      the length of the longest path | 最长路径的长度
      Throws:
      GraphException - if graph is not a DAG | 如果图不是DAG则抛出异常

    • transitiveReduction

      public static <V> Graph<V> transitiveReduction(Graph<V> graph)
      Compute the transitive reduction of a DAG. 计算DAG的传递归约。

      Removes redundant edges: if A->B->C and A->C exist, removes A->C. Returns a new graph instance. O(V*(V+E)).

      移除冗余边：如果A->B->C和A->C同时存在，则移除A->C。 返回新图实例。时间复杂度O(V*(V+E))。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the DAG | 有向无环图
      Returns:
      new graph with redundant edges removed | 移除冗余边的新图
      Throws:
      GraphException - if graph is not a DAG | 如果图不是DAG则抛出异常

    • transitiveClosure

      public static <V> Graph<V> transitiveClosure(Graph<V> graph)
      Compute the transitive closure of a DAG. 计算DAG的传递闭包。

      Adds implied edges: if A->B->C exists but A->C does not, adds A->C. Returns a new graph instance. O(V*(V+E)).

      添加隐含边：如果A->B->C存在但A->C不存在，则添加A->C。 返回新图实例。时间复杂度O(V*(V+E))。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the DAG | 有向无环图
      Returns:
      new graph with implied edges added | 添加隐含边的新图
      Throws:
      GraphException - if graph is not a DAG | 如果图不是DAG则抛出异常

    • ancestors

      public static <V> Set<V> ancestors(Graph<V> graph, V vertex)
      Find all ancestors of a vertex (vertices that can reach this vertex). 查找顶点的所有祖先（能够到达此顶点的顶点）。

      Does not include the vertex itself.

      不包含顶点自身。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the DAG | 有向无环图
      vertex - the vertex | 顶点
      Returns:
      set of ancestor vertices | 祖先顶点集合
      Throws:
      GraphException - if graph is not a DAG | 如果图不是DAG则抛出异常

    • descendants

      public static <V> Set<V> descendants(Graph<V> graph, V vertex)
      Find all descendants of a vertex (vertices reachable from this vertex). 查找顶点的所有后代（从此顶点可达的顶点）。

      Does not include the vertex itself.

      不包含顶点自身。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the DAG | 有向无环图
      vertex - the vertex | 顶点
      Returns:
      set of descendant vertices | 后代顶点集合
      Throws:
      GraphException - if graph is not a DAG | 如果图不是DAG则抛出异常