Class NetworkFlowUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.NetworkFlowUtil
public final class NetworkFlowUtil extends Object
Network Flow Util 网络流工具类

Utility class for network flow algorithms.

网络流算法的工具类。

Algorithms | 算法:

  • Ford-Fulkerson (with BFS/Edmonds-Karp) - O(VE²) | Ford-Fulkerson（使用BFS/Edmonds-Karp）
  • Ford-Fulkerson (with DFS) - O(EF) where F is max flow | Ford-Fulkerson（使用DFS）

Concepts | 概念:

  • Residual Graph - Graph representing remaining capacity | 残余图 - 表示剩余容量的图
  • Augmenting Path - Path from source to sink with available capacity | 增广路径 - 从源到汇的有可用容量的路径
  • Min-Cut - Minimum capacity edges that disconnect source from sink | 最小割 - 将源和汇断开的最小容量边

Features | 主要功能:

  • Maximum flow computation (Edmonds-Karp) - 最大流计算（Edmonds-Karp）
  • Per-edge flow extraction - 逐边流量提取
  • Minimum cut identification - 最小割识别
  • Residual graph construction - 残余图构建

Usage Examples | 使用示例:

// Calculate maximum flow
double maxFlow = NetworkFlowUtil.maxFlow(graph, "source", "sink");

// Get flow on each edge
Map<Edge<String>, Double> flows = NetworkFlowUtil.getFlows(graph, "source", "sink");

// Find minimum cut
Set<Edge<String>> minCut = NetworkFlowUtil.minCut(graph, "source", "sink");

Security | 安全性:

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

Performance | 性能特性:

  • Time complexity: O(V * E^2) for Edmonds-Karp - 时间复杂度: O(V * E^2)（Edmonds-Karp算法）
  • Space complexity: O(V + E) - 空间复杂度: O(V + E)
Since:
JDK 25, opencode-base-graph V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final record 
    NetworkFlowUtil.FlowResult<V>
    Flow result containing max flow value, edge flows, and min-cut 包含最大流值、边流量和最小割的流结果

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V> NetworkFlowUtil.FlowResult<V>
    computeFlow(Graph<V> graph, V source, V sink)
    Get the flow result with detailed information 获取包含详细信息的流结果
    static <V> Map<Edge<V>,Double>
    getFlows(Graph<V> graph, V source, V sink)
    Get flow on each edge 获取每条边上的流量
    static <V> double
    maxFlow(Graph<V> graph, V source, V sink)
    Calculate maximum flow using Ford-Fulkerson algorithm with BFS (Edmonds-Karp) 使用BFS的Ford-Fulkerson算法（Edmonds-Karp）计算最大流
    static <V> double
    maxFlowDfs(Graph<V> graph, V source, V sink)
    Calculate maximum flow using Ford-Fulkerson with DFS 使用DFS的Ford-Fulkerson算法计算最大流
    static <V> Set<Edge<V>>
    minCut(Graph<V> graph, V source, V sink)
    Find minimum cut edges 查找最小割边
    static <V> double
    minCutCapacity(Graph<V> graph, V source, V sink)
    Calculate min-cut capacity 计算最小割容量

    Methods inherited from class Object

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

  • Method Details

    • maxFlow

      public static <V> double maxFlow(Graph<V> graph, V source, V sink)
      Calculate maximum flow using Ford-Fulkerson algorithm with BFS (Edmonds-Karp) 使用BFS的Ford-Fulkerson算法（Edmonds-Karp）计算最大流

      Uses BFS to find augmenting paths, which guarantees polynomial time complexity.

      使用BFS查找增广路径，保证多项式时间复杂度。

      Time Complexity | 时间复杂度: O(VE²)

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

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the directed graph with edge weights as capacities | 边权重作为容量的有向图
      source - the source vertex | 源顶点
      sink - the sink vertex | 汇顶点
      Returns:
      the maximum flow value | 最大流值

    • maxFlowDfs

      public static <V> double maxFlowDfs(Graph<V> graph, V source, V sink)
      Calculate maximum flow using Ford-Fulkerson with DFS 使用DFS的Ford-Fulkerson算法计算最大流

      Uses DFS to find augmenting paths. Faster for some graphs but not polynomial.

      使用DFS查找增广路径。对于某些图更快但非多项式。

      Time Complexity | 时间复杂度: O(EF) where F is max flow value

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

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the directed graph | 有向图
      source - the source vertex | 源顶点
      sink - the sink vertex | 汇顶点
      Returns:
      the maximum flow value | 最大流值

    • getFlows

      public static <V> Map<Edge<V>,Double> getFlows(Graph<V> graph, V source, V sink)
      Get flow on each edge 获取每条边上的流量
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the directed graph | 有向图
      source - the source vertex | 源顶点
      sink - the sink vertex | 汇顶点
      Returns:
      map of edge to flow value | 边到流量值的映射

    • computeFlow

      public static <V> NetworkFlowUtil.FlowResult<V> computeFlow(Graph<V> graph, V source, V sink)
      Get the flow result with detailed information 获取包含详细信息的流结果
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the directed graph | 有向图
      source - the source vertex | 源顶点
      sink - the sink vertex | 汇顶点
      Returns:
      the flow result | 流结果

    • minCut

      public static <V> Set<Edge<V>> minCut(Graph<V> graph, V source, V sink)
      Find minimum cut edges 查找最小割边

      The minimum cut is the set of edges with minimum total capacity that separates source from sink.

      最小割是将源和汇分离的最小总容量边集。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the directed graph | 有向图
      source - the source vertex | 源顶点
      sink - the sink vertex | 汇顶点
      Returns:
      set of edges in the minimum cut | 最小割中的边集合

    • minCutCapacity

      public static <V> double minCutCapacity(Graph<V> graph, V source, V sink)
      Calculate min-cut capacity 计算最小割容量
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the directed graph | 有向图
      source - the source vertex | 源顶点
      sink - the sink vertex | 汇顶点
      Returns:
      the min-cut capacity (equals max flow) | 最小割容量（等于最大流）