如果您从 R 中使用 igraph,请使用此选项
max_flow {igraph} | R 文档 |
在图中,如果每条边都有给定的流量容量,则计算两个顶点之间的最大流量。
max_flow(graph, source, target, capacity = NULL)
图 |
输入图。 |
来源 |
源顶点的 ID。 |
目标 |
目标顶点的 ID(有时也称为汇点)。 |
capacity |
给出边容量的向量。如果这是 |
max_flow
计算加权图(即赋值图)中两个顶点之间的最大流量。从 source
到 target
的流量是将非负实数分配给图的边,满足两个属性:(1)对于每条边,流量(即分配的数字)不大于边的容量(capacity
参数或边属性),(2)对于每个顶点,除了源和目标,流入量与流出量相同。流量的值是 target
顶点的流入量。最大流量是最大值的流量。
一个带有组件的命名列表
value |
一个数值标量,最大流量的值。 |
flow |
一个数值向量,流量本身,每条边对应一个条目。对于无向图,此条目有点棘手,因为对于这些图,流量方向不是由边的方向预先确定的。对于这些图,此向量的元素可以为负数,这意味着流量从较大的顶点 ID 流向较小的顶点 ID。正值表示流量从较小的顶点 ID 流向较大的顶点 ID。 |
cut |
一个边 ID 的数值向量,对应于最大流量的最小割。 |
partition1 |
一个顶点 ID 的数值向量,对应于最大流量的最小割的第一个分区中的顶点。 |
partition2 |
一个顶点 ID 的数值向量,对应于最大流量的最小割的第二个分区中的顶点。 |
stats |
包含来自推送-重标记算法的一些统计信息的列表。目前有五个整数值: |
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"])