maxFlow: Compute max flow for a directed graph
In RBGL: An interface to the BOOST graph library

Description Usage Arguments Details Value Author(s) References See Also Examples

Compute max flow for a directed graph

1
2
3

edmonds.karp.max.flow(g, source, sink)
push.relabel.max.flow(g, source, sink)
kolmogorov.max.flow(g, source, sink)

`g`	an instance of the `graph` class with `edgemode` “directed”
`source`	node name (character) or node number (int) for the source of the flow
`sink`	node name (character) or node number (int) for the sink of the flow

Given a directed graph G=(V, E) of a single connected component with a vertex source and a vertex sink. Each arc has a positive real valued capacity, currently it's equivalent to the weight of the arc. The flow of the network is the net flow entering the vertex sink. The maximum flow problem is to determine the maximum possible value for the flow to the sink and the corresponding flow values for each arc.

See documentation on these algorithms in Boost Graph Library for more details.

A list of

`maxflow`	the max flow from `source` to `sink`
`edges`	the nodes of the arcs with non-zero capacities
`flows`	the flow values of the arcs with non-zero capacities

Li Long <li.long@isb-sib.ch>

Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )

The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8

minCut, edgeConnectivity

con <- file(system.file("XML/dijkex.gxl",package="RBGL"), open="r")
g <- fromGXL(con)
close(con)

ans1 <- edmonds.karp.max.flow(g, "B", "D")
ans2 <- edmonds.karp.max.flow(g, 3, 2)     # 3 and 2 equivalent to "C" and "B"

ans3 <- push.relabel.max.flow(g, 2, 4)     # 2 and 4 equivalent to "B" and "D"
ans4 <- push.relabel.max.flow(g, "C", "B")

# error in the following  now, 14 june 2014
#ans5 <- kolmogorov.max.flow(g, "B", "D")
#ans6 <- kolmogorov.max.flow(g, 3, 2)

Loading required package: graph
Loading required package: BiocGenerics
Loading required package: parallel

Attaching package: 'BiocGenerics'

The following objects are masked from 'package:parallel':

    clusterApply, clusterApplyLB, clusterCall, clusterEvalQ,
    clusterExport, clusterMap, parApply, parCapply, parLapply,
    parLapplyLB, parRapply, parSapply, parSapplyLB

The following objects are masked from 'package:stats':

    IQR, mad, sd, var, xtabs

The following objects are masked from 'package:base':

    Filter, Find, Map, Position, Reduce, anyDuplicated, append,
    as.data.frame, cbind, colMeans, colSums, colnames, do.call,
    duplicated, eval, evalq, get, grep, grepl, intersect, is.unsorted,
    lapply, lengths, mapply, match, mget, order, paste, pmax, pmax.int,
    pmin, pmin.int, rank, rbind, rowMeans, rowSums, rownames, sapply,
    setdiff, sort, table, tapply, union, unique, unsplit, which,
    which.max, which.min