# max.flow

0th

Percentile

##### Compute max flow for a directed graph

Compute max flow for a directed graph

Keywords
models
##### Usage
edmonds.karp.max.flow(g, source, sink)
push.relabel.max.flow(g, source, sink)
kolmogorov.max.flow(g, source, sink)
##### Arguments
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
##### Details

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.

##### Value

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

##### References

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

##### Aliases
• edmonds.karp.max.flow
• push.relabel.max.flow
• kolmogorov.max.flow
##### Examples
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)

Documentation reproduced from package RBGL, version 1.48.1, License: Artistic-2.0

### Community examples

Looks like there are no examples yet.