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