流

最大流

maximum_flow(flowG, _s, _t[, capacity, ...])	查找最大单商品流。
maximum_flow_value(flowG, _s, _t[, ...])	查找最大单商品流的值。
minimum_cut(flowG, _s, _t[, capacity, flow_func])	计算最小(s, t)割的值和节点划分。
minimum_cut_value(flowG, _s, _t[, capacity, ...])	计算最小(s, t)割的值。

Edmonds-Karp

edmonds_karp(G, s, t[, capacity, residual, ...])

使用Edmonds-Karp算法查找最大单商品流。

最短增广路径

shortest_augmenting_path(G, s, t[, ...])

使用最短增广路径算法查找最大单商品流。

预流推进

preflow_push(G, s, t[, capacity, residual, ...])

使用最高标号预流推进算法查找最大单商品流。

Dinitz

dinitz(G, s, t[, capacity, residual, ...])

使用Dinitz算法查找最大单商品流。

Boykov-Kolmogorov

boykov_kolmogorov(G, s, t[, capacity, ...])

使用Boykov-Kolmogorov算法查找最大单商品流。

Gomory-Hu树

gomory_hu_tree(G[, capacity, flow_func])

返回无向图G的Gomory-Hu树。

工具函数

build_residual_network(G, capacity)

构建残差网络并初始化零流。

网络单纯形

network_simplex(G[, demand, capacity, weight])	查找满足有向图G中所有需求的最小费用流。
min_cost_flow_cost(G[, demand, capacity, weight])	查找满足有向图G中所有需求的最小费用流的费用。
min_cost_flow(G[, demand, capacity, weight])	返回满足有向图G中所有需求的最小费用流。
cost_of_flow(G, flowDict[, weight])	计算给定flowDict在图G上的流的费用。
max_flow_min_cost(G, s, t[, capacity, weight])	返回具有最小费用的最大(s, t)流。

容量标度最小费用流

capacity_scaling(G[, demand, capacity, ...])

查找满足有向图G中所有需求的最小费用流。