Flow & Cut 流与割算子集
算子类别：Flow & Cut（网络流与割）
描述：用于解决“最大能流多少 / 在哪些地方会成为瓶颈 / 切断网络最小代价是多少 / 任意两点之间的最小割结构”等问题，是网络容量分析、资源调度与系统韧性评估的核心算法族。
一、算子集概述
Flow & Cut 算子集主要围绕三类核心问题：
-
最大流（Max Flow）
- 从源点到汇点，最多能通过多少流量？
- 哪些边/节点会首先成为瓶颈？
-
最小割（Min Cut）
- 至少切断哪些边（或容量）才能阻断连通？
- 网络的“最薄弱位置”在哪里？
-
全局割结构
- 任意两点之间的最小割是多少？
- 是否能用一棵树压缩表示所有两两最小割？
二、算子列表
| 算子 | 核心能力 |
|---|---|
edmonds_karp | 经典最大流算法，基于 BFS 的增广路径 |
shortest_augmenting_path | 最短增广路最大流，适合中高密度网络 |
preflow_push | 预流推进算法，适合高并发/高连接复杂网络 |
capacity_scaling | 容量分级的最小费用/最大流问题 |
gomory_hu_tree | 全对最小割结构的压缩表示（割树） |
三、通用输入输出约定
3.1 输入
- G：有向或无向图（部分算法仅适用于有向图）
- capacity：边容量属性名（默认
"capacity"） - s / t：源点与汇点（最大流相关算法）
- demand / weight：最小费用流与容量分级问题使用
3.2 输出
- 最大流算法：残量网络（Residual Network）或流值
- 容量/费用算法：最优流方案 + 总成本
- Gomory–Hu Tree：一棵无向树，编码所有两点最小割
四、算子详细说明
4.1 edmonds_karp —— 经典最大流算法
功能说明
基于 Ford–Fulkerson 方法，始终选择 最短（按边数）增广路径 来逐步增加从源点 s 到汇点 t 的流量。
适用场景
- 中小规模网络的最大流计算
- 教学、调试、可解释性强的流分析
- 需要输出完整增广路径与残量网络的场景
参数要点
- capacity：边容量属性
- cutoff：提前终止阈值（达到某流量即停止）
原理与复杂度
- 每次用 BFS 找增广路径
- 时间复杂度：
O(V · E²)
可回答问题
- 从 A 到 B 的最大运输能力是多少？
- 哪些管道/链路在最大流下被完全占满？
4.2 shortest_augmenting_path —— 最短增广路最大流
功能说明
利用距离标号（distance labeling），优先选择“最短代价”的增广路径来提高效率。
适用场景
- 中到大规模网络
- 需要比 Edmonds–Karp 更快的最大流求解
- 电信、交通、物流骨干网络
参数要点
- two_phase：对单位容量网络显著加速
- cutoff：最小可接受流量阈值
原理与复杂度
- 基于最短路思想的增广路径搜索
- 复杂度：
O(V² · E)（实际表现通常更优）
4.3 preflow_push —— 预流推进算法
功能说明
不要求中间节点流量守恒，允许“预流”，通过 Push / Relabel 操作逐步逼近最大流。
适用场景
- 极其复杂、连通度高的大型网络
- 高并发、高密度图（如数据中心、芯片布线）
- 对性能要求极高的最大流计算
参数要点
- global_relabel_freq：全局重标记频率（重要性能调优参数）
- value_only：仅关心最大流值而不关心路径
原理与复杂度
- 局部推进 + 高度标号
- 复杂度：
O(V² · E)（实践中常优于路径型算法）
4.4 capacity_scaling —— 容量分级流算法
功能说明
按容量等级（Δ-scaling）逐步放大可用容量，解决 带需求（demand）与费用（cost）约束 的流问题。
适用场景
- 供需平衡问题（多源多汇）
- 成本最优的运输/调度问题
- 能源、物流、云资源分配
参数要点
- demand：节点需求属性（供给为负，需求为正）
- capacity：边容量属性
- weight：单位流量成本
原理与复杂度
- 逐级放宽容量限制，寻找最优流
- 复杂度：
O(E² log C)
4.5 gomory_hu_tree —— Gomory–Hu 割树
功能说明
用 一棵树 表示图中 任意两点之间的最小割值，支持快速两点割/流查询。
树上任意两点路径中的 最小边权 = 原图中这两点的最小割。
适用场景
- 全局网络韧性分析
- 找“最弱连接对”
- 快速回答任意两点的最小割/最大流
参数要点
- capacity：边容量属性
- flow_func：底层最大流算法（稀疏图推荐
edmonds_karp，稠密图推荐shortest_augmenting_path）
原理与复杂度
- 构造
n-1次最大流 - 复杂度：
O(V · MaxFlow)
五、选型指南（怎么选）
- 想算 s → t 最大流（中小图）：
edmonds_karp - 想更快算最大流（较大图）：
shortest_augmenting_path - 极复杂高并发网络：
preflow_push - 有供需 + 成本约束：
capacity_scaling - 想一次性支持任意两点最小割查询：
gomory_hu_tree
六、可直接回答的典型问题
- “这条网络从 A 到 B 的最大承载能力是多少？”
- “哪些链路是系统的瓶颈？”
- “最小代价切断系统需要破坏哪些连接？”
- “任意两个节点之间，最少切掉多少容量才能隔离？”
- “整个网络中，最脆弱的连接对是哪一组？”