1#   IGraph R package
2#   Copyright (C) 2005-2012  Gabor Csardi <csardi.gabor@gmail.com>
3#   334 Harvard street, Cambridge, MA 02139 USA
4#
5#   This program is free software; you can redistribute it and/or modify
6#   it under the terms of the GNU General Public License as published by
7#   the Free Software Foundation; either version 2 of the License, or
8#   (at your option) any later version.
9#
10#   This program is distributed in the hope that it will be useful,
11#   but WITHOUT ANY WARRANTY; without even the implied warranty of
12#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13#   GNU General Public License for more details.
14#
15#   You should have received a copy of the GNU General Public License
16#   along with this program; if not, write to the Free Software
17#   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA
18#   02110-1301 USA
19#
20###################################################################
21
22###################################################################
23# Connected components, subgraphs, kinda
24###################################################################
25
26#' @export
27
28count_components <- function(graph, mode=c("weak", "strong")) {
29  if (!is_igraph(graph)) {
30    stop("Not a graph object")
31  }
32  mode <- igraph.match.arg(mode)
33  mode <- switch(mode, "weak"=1, "strong"=2)
34
35  on.exit( .Call(C_R_igraph_finalizer) )
36  .Call(C_R_igraph_no_clusters, graph, as.numeric(mode))
37}
38
39#' @rdname components
40#' @param cumulative Logical, if TRUE the cumulative distirubution (relative
41#' frequency) is calculated.
42#' @param mul.size Logical. If TRUE the relative frequencies will be multiplied
43#' by the cluster sizes.
44#' @export
45#' @importFrom graphics hist
46
47component_distribution <- function(graph, cumulative=FALSE, mul.size=FALSE,
48                                 ...) {
49  if (!is_igraph(graph)) {
50    stop("Not a graph object")
51  }
52
53  cs <- components(graph, ...)$csize;
54  hi <- hist(cs, -1:max(cs), plot=FALSE)$density
55  if (mul.size) {
56    hi <- hi*1:max(cs)
57    hi <- hi/sum(hi)
58  }
59  if (!cumulative) {
60    res <- hi
61  } else {
62    res <- rev(cumsum(rev(hi)));
63  }
64
65  res
66}
67
68#' @export
69
70is_connected <- function(graph, mode=c("weak", "strong")) {
71  if (!is_igraph(graph)) {
72    stop("Not a graph object")
73  }
74  mode <- igraph.match.arg(mode)
75  mode <- switch(mode, "weak"=1, "strong"=2)
76
77  on.exit( .Call(C_R_igraph_finalizer) )
78  .Call(C_R_igraph_is_connected, graph, as.numeric(mode))
79}
80
81
82
83#' Decompose a graph into components
84#'
85#' Creates a separate graph for each component of a graph.
86#'
87#' @aliases decompose.graph
88#' @param graph The original graph.
89#' @param mode Character constant giving the type of the components, wither
90#' \code{weak} for weakly connected components or \code{strong} for strongly
91#' connected components.
92#' @param max.comps The maximum number of components to return. The first
93#' \code{max.comps} components will be returned (which hold at least
94#' \code{min.vertices} vertices, see the next parameter), the others will be
95#' ignored. Supply \code{NA} here if you don't want to limit the number of
96#' components.
97#' @param min.vertices The minimum number of vertices a component should
98#' contain in order to place it in the result list. Eg. supply 2 here to ignore
99#' isolate vertices.
100#' @return A list of graph objects.
101#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
102#' @seealso \code{\link{is_connected}} to decide whether a graph is connected,
103#' \code{\link{components}} to calculate the connected components of a graph.
104#' @export
105#' @keywords graphs
106#' @examples
107#'
108#' # the diameter of each component in a random graph
109#' g <- sample_gnp(1000, 1/1000)
110#' components <- decompose(g, min.vertices=2)
111#' sapply(components, diameter)
112#'
113decompose <- function(graph, mode=c("weak", "strong"), max.comps=NA,
114                      min.vertices=0) {
115  if (!is_igraph(graph)) {
116    stop("Not a graph object")
117  }
118  mode <- igraph.match.arg(mode)
119  mode <- switch(mode, "weak"=1, "strong"=2)
120
121  if (is.na(max.comps)) {
122    max.comps=-1
123  }
124  on.exit( .Call(C_R_igraph_finalizer) )
125  .Call(C_R_igraph_decompose, graph, as.numeric(mode),
126        as.numeric(max.comps), as.numeric(min.vertices))
127}
128
129
130#' Articulation points of a graph
131#'
132#' Articuation points or cut vertices are vertices whose removal increases the
133#' number of connected components in a graph.
134#'
135#' Articuation points or cut vertices are vertices whose removal increases the
136#' number of connected components in a graph. If the original graph was
137#' connected, then the removal of a single articulation point makes it
138#' undirected. If a graph contains no articulation points, then its vertex
139#' connectivity is at least two.
140#'
141#' @aliases articulation.points articulation_points
142#' @param graph The input graph. It is treated as an undirected graph, even if
143#' it is directed.
144#' @return A numeric vector giving the vertex ids of the articulation points of
145#' the input graph.
146#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
147#' @seealso \code{\link{biconnected_components}}, \code{\link{components}},
148#' \code{\link{is_connected}}, \code{\link{vertex_connectivity}}
149#' @keywords graphs
150#' @examples
151#'
152#' g <- disjoint_union( make_full_graph(5), make_full_graph(5) )
153#' clu <- components(g)$membership
154#' g <- add_edges(g, c(match(1, clu), match(2, clu)) )
155#' articulation_points(g)
156#' @export
157#' @include auto.R
158
159articulation_points <- articulation_points
160
161
162#' Biconnected components
163#'
164#' Finding the biconnected components of a graph
165#'
166#' A graph is biconnected if the removal of any single vertex (and its adjacent
167#' edges) does not disconnect it.
168#'
169#' A biconnected component of a graph is a maximal biconnected subgraph of it.
170#' The biconnected components of a graph can be given by the partition of its
171#' edges: every edge is a member of exactly one biconnected component. Note
172#' that this is not true for vertices: the same vertex can be part of many
173#' biconnected components.
174#'
175#' @aliases biconnected.components biconnected_components
176#' @param graph The input graph. It is treated as an undirected graph, even if
177#' it is directed.
178#' @return A named list with three components: \item{no}{Numeric scalar, an
179#' integer giving the number of biconnected components in the graph.}
180#' \item{tree_edges}{The components themselves, a list of numeric vectors. Each
181#' vector is a set of edge ids giving the edges in a biconnected component.
182#' These edges define a spanning tree of the component.}
183#' \item{component_edges}{A list of numeric vectors. It gives all edges in the
184#' components.} \item{components}{A list of numeric vectors, the vertices of
185#' the components.} \item{articulation_points}{The articulation points of the
186#' graph. See \code{\link{articulation_points}}.}
187#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
188#' @seealso \code{\link{articulation_points}}, \code{\link{components}},
189#' \code{\link{is_connected}}, \code{\link{vertex_connectivity}}
190#' @keywords graphs
191#' @examples
192#'
193#' g <- disjoint_union( make_full_graph(5), make_full_graph(5) )
194#' clu <- components(g)$membership
195#' g <- add_edges(g, c(which(clu==1), which(clu==2)))
196#' bc <- biconnected_components(g)
197#' @export
198
199biconnected_components <- biconnected_components
200