graph.maxflow(graph, source, target, capacity=NULL)
graph.mincut(graph, source=NULL, target=NULL, capacity=NULL,
value.only = TRUE)
NULL
(the default) then the capacity
edge attribute is
used.TRUE
only the minumum cut
value is returned, if FALSE
the edges in the cut and a the
two (or more) partitions are also returned.graph.maxflow
a named list with components:nopush
is the
number of push operations, norelabel
the number of
relabelings, nogap
is the number of times the gap heuristics
was used, nogapnodes
is the total number of gap nodes omitted
because of the gap heuristics and nobfs
is the number of
times a global breadth-first-search update was performed to assign
better height (=distance) values to the vertices.graph.mincut
a numeric constant, the value of the minimum
cut, except if value.only=FALSE
. In this case a named list with
components:graph.maxflow
calculates the maximum flow between two vertices
in a weighted (ie. valued) graph. A flow from source
to
target
is an assignment of non-negative real numbers to the
edges of the graph, satisfying two properties: (1) for each edge the
flow (ie. the assigned number) is not more than the capacity of the
edge (the capacity
parameter or edge attribute), (2) for every
vertex, except the source and the target the incoming flow is the same
as the outgoing flow. The value of the flow is the incoming flow of
the target
vertex. The maximum flow is the flow of maximum
value. graph.mincut
calculates the minimum st-cut between two vertices
in a graph (if the source
and target
arguments are
given) or the minimum cut of the graph (if both source
and
target
are NULL
).
The minimum st-cut between source
and target
is the
minimum total weight of edges needed to remove to eliminate all paths from
source
to target
.
The minimum cut of a graph is the minimum total weight of the edges
needed to remove to separate the graph into (at least) two
components. (Which is to make the graph not strongly connected
in the directed case.)
The maximum flow between two vertices in a graph is the same as the minimum
st-cut, so graph.maxflow
and graph.mincut
essentially
calculate the same quantity, the only difference is that
graph.mincut
can be invoked without giving the source
and target
arguments and then minimum of all possible minimum
cuts is calculated.
For undirected graphs the Stoer-Wagner algorithm (see reference below) is used to calculate the minimum cut.
shortest.paths
, edge.connectivity
,
vertex.connectivity
E <- rbind( c(1,3,3), c(3,4,1), c(4,2,2), c(1,5,1), c(5,6,2), c(6,2,10))
colnames(E) <- c("from", "to", "capacity")
g1 <- graph.data.frame(as.data.frame(E))
graph.maxflow(g1, source=V(g1)["1"], target=V(g1)["2"])
g <- graph.ring(100)
graph.mincut(g, capacity=rep(1,vcount(g)))
graph.mincut(g, value.only=FALSE, capacity=rep(1,vcount(g)))
g2 <- graph( c(1,2,2,3,3,4, 1,6,6,5,5,4, 4,1) )
E(g2)$capacity <- c(3,1,2, 10,1,3, 2)
graph.mincut(g2, value.only=FALSE)
Run the code above in your browser using DataCamp Workspace