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
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/flow.R
\name{min_st_separators}
\alias{min_st_separators}
\title{Minimum size vertex separators}
\usage{
min_st_separators(graph)
}
\arguments{
\item{graph}{The input graph. It may be directed, but edge directions are
ignored.}
}
\value{
A list of numeric vectors. Each vector contains a vertex set
(defined by vertex ids), each vector is an (s,t) separator of the input
graph, for some \eqn{s} and \eqn{t}.
}
\description{
List all vertex sets that are minimal \eqn{(s,t)} separators for some
\eqn{s} and \eqn{t}, in an undirected graph.
}
\details{
A \eqn{(s,t)} vertex separator is a set of vertices, such that after their
removal from the graph, there is no path between \eqn{s} and \eqn{t} in the
graph.
A \eqn{(s,t)} vertex separator is minimal if none of its proper subsets is
an \eqn{(s,t)} vertex separator for the same \eqn{s} and \eqn{t}.
}
\section{Note}{
Note that the code below returns \verb{\{1, 3\}} despite its subset \code{{1}} being a
separator as well. This is because \verb{\{1, 3\}} is minimal with respect to
separating vertices 2 and 4.
\if{html}{\out{<div class="sourceCode r">}}\preformatted{g <- make_graph(~ 0-1-2-3-4-1)
min_st_separators(g)
}\if{html}{\out{</div>}}
\if{html}{\out{<div class="sourceCode">}}\preformatted{#> [[1]]
#> + 1/5 vertex, named:
#> [1] 1
#>
#> [[2]]
#> + 2/5 vertices, named:
#> [1] 2 4
#>
#> [[3]]
#> + 2/5 vertices, named:
#> [1] 1 3
}\if{html}{\out{</div>}}
}
\examples{
ring <- make_ring(4)
min_st_separators(ring)
chvatal <- make_graph("chvatal")
min_st_separators(chvatal)
# https://github.com/r-lib/roxygen2/issues/1092
}
\references{
Anne Berry, Jean-Paul Bordat and Olivier Cogis: Generating All
the Minimal Separators of a Graph, In: Peter Widmayer, Gabriele Neyer and
Stephan Eidenbenz (editors): \emph{Graph-theoretic concepts in computer
science}, 1665, 167--172, 1999. Springer.
}
\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{st_cuts}()},
\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-Separators.html#igraph_all_minimal_st_separators}{\code{igraph_all_minimal_st_separators()}}.}
|
