R igraph 手册页

max_flow {igraph}

R 文档

图中的最大流

描述

在图中，如果每条边都有给定的流量容量，则计算两个顶点之间的最大流量。

用法

max_flow(graph, source, target, capacity = NULL)

参数

图	输入图。
来源	源顶点的 ID。
目标	目标顶点的 ID（有时也称为汇点）。
capacity	给出边容量的向量。如果这是 NULL（默认值），则使用 capacity 边属性。请注意，此函数不使用 weight 边属性。

详细信息

max_flow 计算加权图（即赋值图）中两个顶点之间的最大流量。从 source 到 target 的流量是将非负实数分配给图的边，满足两个属性：（1）对于每条边，流量（即分配的数字）不大于边的容量（capacity 参数或边属性），（2）对于每个顶点，除了源和目标，流入量与流出量相同。流量的值是 target 顶点的流入量。最大流量是最大值的流量。

值

一个带有组件的命名列表

value	一个数值标量，最大流量的值。
flow	一个数值向量，流量本身，每条边对应一个条目。对于无向图，此条目有点棘手，因为对于这些图，流量方向不是由边的方向预先确定的。对于这些图，此向量的元素可以为负数，这意味着流量从较大的顶点 ID 流向较小的顶点 ID。正值表示流量从较小的顶点 ID 流向较大的顶点 ID。
cut	一个边 ID 的数值向量，对应于最大流量的最小割。
partition1	一个顶点 ID 的数值向量，对应于最大流量的最小割的第一个分区中的顶点。
partition2	一个顶点 ID 的数值向量，对应于最大流量的最小割的第二个分区中的顶点。
stats	包含来自推送-重标记算法的一些统计信息的列表。目前有五个整数值：nopush 是推送操作的数量，norelabel 是重标记的数量，nogap 是使用间隙启发式的次数，nogapnodes 是由于间隙启发式而省略的间隙节点总数，nobfs 是执行全局广度优先搜索更新以将更好的高度（=距离）值分配给顶点的次数。

参考

A. V. Goldberg and R. E. Tarjan: A New Approach to the Maximum Flow Problem Journal of the ACM 35:921-940, 1988.

参见

min_cut 用于最小割计算，distances, edge_connectivity, vertex_connectivity

示例

E <- rbind( c(1,3,3), c(3,4,1), c(4,2,2), c(1,5,1), c(5,6,2), c(6,2,10))
colnames(E) <- c("from", "to", "capacity")
g1 <- graph_from_data_frame(as.data.frame(E))
max_flow(g1, source=V(g1)["1"], target=V(g1)["2"])

---