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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/flow.R
\name{edge_connectivity}
\alias{edge_connectivity}
\alias{edge_disjoint_paths}
\alias{adhesion}
\title{Edge connectivity}
\usage{
edge_connectivity(graph, source = NULL, target = NULL, checks = TRUE)
edge_disjoint_paths(graph, source, target)
adhesion(graph, checks = TRUE)
}
\arguments{
\item{graph}{The input graph.}
\item{source}{The id of the source vertex, for \code{edge_connectivity()} it
can be \code{NULL}, see details below.}
\item{target}{The id of the target vertex, for \code{edge_connectivity()} it
can be \code{NULL}, see details below.}
\item{checks}{Logical constant. Whether to check that the graph is connected
and also the degree of the vertices. If the graph is not (strongly)
connected then the connectivity is obviously zero. Otherwise if the minimum
degree is one then the edge connectivity is also one. It is a good idea to
perform these checks, as they can be done quickly compared to the
connectivity calculation itself. They were suggested by Peter McMahan,
thanks Peter.}
}
\value{
A scalar real value.
}
\description{
The edge connectivity of a graph or two vertices, this is recently also
called group adhesion.
}
\section{\code{edge_connectivity()} Edge connectivity}{
The edge connectivity of a pair of vertices (\code{source} and
\code{target}) is the minimum number of edges needed to remove to eliminate
all (directed) paths from \code{source} to \code{target}.
\code{edge_connectivity()} calculates this quantity if both the \code{source}
and \code{target} arguments are given (and not \code{NULL}).
The edge connectivity of a graph is the minimum of the edge connectivity of
every (ordered) pair of vertices in the graph. \code{edge_connectivity()}
calculates this quantity if neither the \code{source} nor the \code{target}
arguments are given (i.e. they are both \code{NULL}).
}
\section{\code{edge_disjoint_paths()} The maximum number of edge-disjoint paths between two vertices}{
A set of paths between two vertices is called edge-disjoint if they do not
share any edges. The maximum number of edge-disjoint paths are calculated
by this function using maximum flow techniques. Directed paths are
considered in directed graphs.
A set of edge disjoint paths between two vertices is a set of paths between
them containing no common edges. The maximum number of edge disjoint paths
between two vertices is the same as their edge connectivity.
When there are no direct edges between the source and the target, the number
of vertex-disjoint paths is the same as the vertex connectivity of
the two vertices. When some edges are present, each one of them
contributes one extra path.
}
\section{\code{adhesion()} Adhesion of a graph}{
The adhesion of a graph is the minimum number of edges needed to remove to
obtain a graph which is not strongly connected. This is the same as the edge
connectivity of the graph.
}
\section{All three functions}{
The three functions documented on this page calculate similar properties,
more precisely the most general is \code{edge_connectivity()}, the others are
included only for having more descriptive function names.
}
\examples{
g <- sample_pa(100, m = 1)
g2 <- sample_pa(100, m = 5)
edge_connectivity(g, 100, 1)
edge_connectivity(g2, 100, 1)
edge_disjoint_paths(g2, 100, 1)
g <- sample_gnp(50, 5 / 50)
g <- as_directed(g)
g <- induced_subgraph(g, subcomponent(g, 1))
adhesion(g)
}
\references{
Douglas R. White and Frank Harary (2001): The cohesiveness of blocks in
social networks: node connectivity and conditional density,
Sociological Methodology, vol. 31, 2001, pp. 305–59.
}
\seealso{
Other flow:
\code{\link{dominator_tree}()},
\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_cuts}()},
\code{\link{st_min_cuts}()},
\code{\link{vertex_connectivity}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{flow}
\keyword{graphs}
|
