sna (version 2.7-2)

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)

Value

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

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?

Author

Carter T. Butts buttsc@uci.edu

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.)

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

flowbet, geodist

Examples

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

Run the code above in your browser using DataLab