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
graphclass 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
sourcetosink - 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
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)