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
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/flow.R
\name{st_cuts}
\alias{st_cuts}
\title{List all (s,t)-cuts of a graph}
\usage{
st_cuts(graph, source, target)
}
\arguments{
\item{graph}{The input graph. It must be directed.}
\item{source}{The source vertex.}
\item{target}{The target vertex.}
}
\value{
A list with entries: \item{cuts}{A list of numeric vectors
containing edge ids. Each vector is an \eqn{(s,t)}-cut.}
\item{partition1s}{A list of numeric vectors containing vertex ids, they
correspond to the edge cuts. Each vertex set is a generator of the
corresponding cut, i.e. in the graph \eqn{G=(V,E)}, the vertex set \eqn{X}
and its complementer \eqn{V-X}, generates the cut that contains exactly the
edges that go from \eqn{X} to \eqn{V-X}.}
}
\description{
List all (s,t)-cuts in a directed graph.
}
\details{
Given a \eqn{G} directed graph and two, different and non-ajacent vertices,
\eqn{s} and \eqn{t}, an \eqn{(s,t)}-cut is a set of edges, such that after
removing these edges from \eqn{G} there is no directed path from \eqn{s} to
\eqn{t}.
}
\examples{
# A very simple graph
g <- graph_from_literal(a -+ b -+ c -+ d -+ e)
st_cuts(g, source = "a", target = "e")
# A somewhat more difficult graph
g2 <- graph_from_literal(
s --+ a:b, a:b --+ t,
a --+ 1:2:3, 1:2:3 --+ b
)
st_cuts(g2, source = "s", target = "t")
}
\references{
JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in
graphs, \emph{Algorithmica} 15, 351--372, 1996.
}
\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_cut}()},
\code{\link{min_separators}()},
\code{\link{min_st_separators}()},
\code{\link{st_min_cuts}()},
\code{\link{vertex_connectivity}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{flow}
\keyword{graphs}
\section{Related documentation in the C library}{\href{https://igraph.org/c/html/latest/igraph-Flows.html#igraph_all_st_cuts}{\code{igraph_all_st_cuts()}}.}
|
