1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/flow.R
\name{min_cut}
\alias{min_cut}
\title{Minimum cut in a graph}
\usage{
min_cut(
graph,
source = NULL,
target = NULL,
capacity = NULL,
value.only = TRUE
)
}
\arguments{
\item{graph}{The input graph.}
\item{source}{The id of the source vertex.}
\item{target}{The id of the target vertex (sometimes also called sink).}
\item{capacity}{Vector giving the capacity of the edges. If this is
\code{NULL} (the default) then the \code{capacity} edge attribute is used.}
\item{value.only}{Logical scalar, if \code{TRUE} only the minimum cut value
is returned, if \code{FALSE} the edges in the cut and a the two (or more)
partitions are also returned.}
}
\value{
For \code{min_cut()} a nuieric constant, the value of the minimum
cut, except if \code{value.only = FALSE}. In this case a named list with
components:
\item{value}{Numeric scalar, the cut value.}
\item{cut}{Numeric vector, the edges in the cut.}
\item{partition1}{The vertices in the first partition after the cut
edges are removed. Note that these vertices might be actually in
different components (after the cut edges are removed), as the graph
may fall apart into more than two components.}
\item{partition2}{The vertices in the second partition
after the cut edges are removed. Note that these vertices might be
actually in different components (after the cut edges are removed), as
the graph may fall apart into more than two components.}
}
\description{
\code{min_cut()} calculates the minimum st-cut between two vertices in a graph
(if the \code{source} and \code{target} arguments are given) or the minimum
cut of the graph (if both \code{source} and \code{target} are \code{NULL}).
}
\details{
The minimum st-cut between \code{source} and \code{target} is the minimum
total weight of edges needed to remove to eliminate all paths from
\code{source} to \code{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 \emph{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 \code{max_flow()} and \code{min_cut()} essentially calculate the same
quantity, the only difference is that \code{min_cut()} can be invoked without
giving the \code{source} and \code{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.
}
\examples{
g <- make_ring(100)
min_cut(g, capacity = rep(1, vcount(g)))
min_cut(g, value.only = FALSE, capacity = rep(1, vcount(g)))
g2 <- make_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)
}
\references{
M. Stoer and F. Wagner: A simple min-cut algorithm,
\emph{Journal of the ACM}, 44 585-591, 1997.
}
\seealso{
Other flow:
\code{\link{dominator_tree}()},
\code{\link{edge_connectivity}()},
\code{\link{is_min_separator}()},
\code{\link{is_separator}()},
\code{\link{max_flow}()},
\code{\link{min_separators}()},
\code{\link{min_st_separators}()},
\code{\link{st_cuts}()},
\code{\link{st_min_cuts}()},
\code{\link{vertex_connectivity}()}
}
\concept{flow}
|