min_cut
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
).min_cut(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.min_cut
a numeric constant, the value of the minimum
cut, except if value.only = FALSE
. In this case a named list with
components: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 max_flow
and min_cut
essentially calculate the same
quantity, the only difference is that min_cut
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.
max_flow
for the related maximum flow
problem, distances
, edge_connectivity
,
vertex_connectivity
g <- make_ring(100)
min_cut(g, capacity=rep(1,vcount(g)))
min_cut(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)
min_cut(g2, value.only=FALSE)
Run the code above in your browser using DataCamp Workspace