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
94
95
96
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/flow.R
\name{min_separators}
\alias{min_separators}
\title{Minimum size vertex separators}
\usage{
min_separators(graph)
}
\arguments{
\item{graph}{The input graph. It may be directed, but edge directions are
ignored.}
}
\value{
A list of numeric vectors. Each numeric vector is a vertex
separator.
}
\description{
Find all vertex sets of minimal size whose removal separates the graph into
more components
}
\details{
This function implements the Kanevsky algorithm for finding all minimal-size
vertex separators in an undirected graph. See the reference below for the
details.
In the special case of a fully connected input graph with \eqn{n} vertices,
all subsets of size \eqn{n-1} are listed as the result.
}
\examples{
# The graph from the Moody-White paper
mw <- graph_from_literal(
1 - 2:3:4:5:6, 2 - 3:4:5:7, 3 - 4:6:7, 4 - 5:6:7,
5 - 6:7:21, 6 - 7, 7 - 8:11:14:19, 8 - 9:11:14, 9 - 10,
10 - 12:13, 11 - 12:14, 12 - 16, 13 - 16, 14 - 15, 15 - 16,
17 - 18:19:20, 18 - 20:21, 19 - 20:22:23, 20 - 21,
21 - 22:23, 22 - 23
)
# Cohesive subgraphs
mw1 <- induced_subgraph(mw, as.character(c(1:7, 17:23)))
mw2 <- induced_subgraph(mw, as.character(7:16))
mw3 <- induced_subgraph(mw, as.character(17:23))
mw4 <- induced_subgraph(mw, as.character(c(7, 8, 11, 14)))
mw5 <- induced_subgraph(mw, as.character(1:7))
min_separators(mw)
min_separators(mw1)
min_separators(mw2)
min_separators(mw3)
min_separators(mw4)
min_separators(mw5)
# Another example, the science camp network
camp <- graph_from_literal(
Harry:Steve:Don:Bert - Harry:Steve:Don:Bert,
Pam:Brazey:Carol:Pat - Pam:Brazey:Carol:Pat,
Holly - Carol:Pat:Pam:Jennie:Bill,
Bill - Pauline:Michael:Lee:Holly,
Pauline - Bill:Jennie:Ann,
Jennie - Holly:Michael:Lee:Ann:Pauline,
Michael - Bill:Jennie:Ann:Lee:John,
Ann - Michael:Jennie:Pauline,
Lee - Michael:Bill:Jennie,
Gery - Pat:Steve:Russ:John,
Russ - Steve:Bert:Gery:John,
John - Gery:Russ:Michael
)
min_separators(camp)
}
\references{
Arkady Kanevsky: Finding all minimum-size separating vertex sets
in a graph. \emph{Networks} 23 533--541, 1993.
JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs,
\emph{Algorithmica} 15, 351--372, 1996.
J. Moody and D. R. White. Structural cohesion and embeddedness: A
hierarchical concept of social groups. \emph{American Sociological Review},
68 103--127, Feb 2003.
}
\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_st_separators}()},
\code{\link{st_cuts}()},
\code{\link{st_min_cuts}()},
\code{\link{vertex_connectivity}()}
}
\concept{flow}
\section{Related documentation in the C library}{\href{https://igraph.org/c/html/latest/igraph-Separators.html#igraph_minimum_size_separators}{\code{igraph_minimum_size_separators()}}.}
|
