maxflow: Calculate Maximum Flows Between Vertices

In sna: Tools for Social Network Analysis

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 [e-mail]

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

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

sna documentation built on Sept. 11, 2024, 8:45 p.m.