Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!
Get Started for Free

maxflow

Calculate Maximum Flows Between Vertices


Description

maxflow calculates a matrix of maximum pairwise flows within a (possibly valued) input network.

Usage

maxflow(dat, src = NULL, sink = NULL, ignore.eval = FALSE)

Arguments

dat

one or more input graphs.

src

optionally, a vector of source vertices; by default, all vertices are selected.

sink

optionally, a vector of sink (or target) vertices; by default, all vertices are selected.

ignore.eval

logical; ignore edge values (i.e., assume unit capacities) when computing flow?

Details

maxflow computes the maximum flow from each source vertex to each sink vertex, assuming infinite vertex capacities and limited edge capacities. If ignore.eval==FALSE, supplied edge values are assumed to contain capacity information; otherwise, all non-zero edges are assumed to have unit capacity.

Note that all flows computed here are pairwise – i.e., when computing the flow from v to v', we ignore any other flows which could also be taking place within the network. As a result, it should not be assumed that these flows can be realized simultaneously. (For the latter purpose, the values returned by maxflow can be treated as upper bounds.)

Value

A matrix of pairwise maximum flows (if multiple sources/sinks selected), or a single maximum flow value (otherwise).

Author(s)

Carter T. Butts buttsc@uci.edu

References

Edmonds, J. and Karp, R.M. (1972). “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM, 19(2), 248-264.

See Also

Examples

g<-rgraph(10,tp=2/9)                     #Generate a sparse random graph
maxflow(g)                               #Compute all-pairs max flow

sna

Tools for Social Network Analysis

v2.6
GPL (>= 2)
Authors
Carter T. Butts [aut, cre, cph]
Initial release
2020-10-5

We don't support your browser anymore

Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.