max.flow {RBGL} | R Documentation |
Compute max flow for a directed graph
edmunds.karp.max.flow(g, source, sink) push.relabel.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.
edmunds.karp.max.flow |
the max flow from source to sink using Edmuns-Karp algorithm |
push.relabel.max.flow |
the max flow from source to sink using Push-Relabel algorithm |
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 by Siek et al.
g <- fromGXL(file(system.file("XML/dijkex.gxl",package="RBGL"))) ans1 <- edmunds.karp.max.flow(g, "B", "D") ans2 <- edmunds.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")