build_residual_network

build_residual_network(G, capacity)

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

残差网络 R 来自输入图 G ，具有与 G 相同的节点。R 是一个有向图，如果 (u, v) 不是自环，并且 (u, v) 和 (v, u) 中至少有一个存在于 G 中，则 R 包含一对边 (u, v) 和 (v, u) 。

对于 R 中的每条边 (u, v) ，如果 (u, v) 在 G 中存在，则 R[u][v]['capacity'] 等于 (u, v) 在 G 中的容量，否则为零。如果容量是无限的，R[u][v]['capacity'] 将有一个高任意有限值，该值不影响问题的解决方案。此值存储在 R.graph['inf'] 中。对于 R 中的每条边 (u, v) ，R[u][v]['flow'] 表示 (u, v) 的流函数，并且满足 R[u][v]['flow'] == -R[v][u]['flow'] 。

定义为流入汇点 t 的总流量的流值存储在 R.graph['flow_value'] 中。如果未指定 cutoff ，则仅使用满足 R[u][v]['flow'] < R[u][v]['capacity'] 的边 (u, v) 到达 t 的可达性会诱导一个最小 s -t 割。