max.flow
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 withedgemode
“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
tosink
 edges
 the nodes of the arcs with nonzero capacities
 flows
 the flow values of the arcs with nonzero 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, LieQuan Lee, and Andrew Lumsdaine; (AddisonWesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0201729148
See Also
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)