1# IGraph R package 2# Copyright (C) 2009-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 24#' Project a bipartite graph 25#' 26#' A bipartite graph is projected into two one-mode networks 27#' 28#' Bipartite graphs have a \code{type} vertex attribute in igraph, this is 29#' boolean and \code{FALSE} for the vertices of the first kind and \code{TRUE} 30#' for vertices of the second kind. 31#' 32#' \code{bipartite_projection_size} calculates the number of vertices and edges 33#' in the two projections of the bipartite graphs, without calculating the 34#' projections themselves. This is useful to check how much memory the 35#' projections would need if you have a large bipartite graph. 36#' 37#' \code{bipartite_projection} calculates the actual projections. You can use 38#' the \code{probe1} argument to specify the order of the projections in the 39#' result. By default vertex type \code{FALSE} is the first and \code{TRUE} is 40#' the second. 41#' 42#' \code{bipartite_projection} keeps vertex attributes. 43#' 44#' @aliases bipartite.projection bipartite.projection.size bipartite_projection_size bipartite_projection 45#' @param graph The input graph. It can be directed, but edge directions are 46#' ignored during the computation. 47#' @param types An optional vertex type vector to use instead of the 48#' \sQuote{\code{type}} vertex attribute. You must supply this argument if the 49#' graph has no \sQuote{\code{type}} vertex attribute. 50#' @param multiplicity If \code{TRUE}, then igraph keeps the multiplicity of 51#' the edges as an edge attribute called \sQuote{weight}. 52#' E.g. if there is an A-C-B and also an A-D-B 53#' triple in the bipartite graph (but no more X, such that A-X-B is also in the 54#' graph), then the multiplicity of the A-B edge in the projection will be 2. 55#' @param probe1 This argument can be used to specify the order of the 56#' projections in the resulting list. If given, then it is considered as a 57#' vertex id (or a symbolic vertex name); the projection containing this vertex 58#' will be the first one in the result list. This argument is ignored if only 59#' one projection is requested in argument \code{which}. 60#' @param which A character scalar to specify which projection(s) to calculate. 61#' The default is to calculate both. 62#' @param remove.type Logical scalar, whether to remove the \code{type} vertex 63#' attribute from the projections. This makes sense because these graphs are 64#' not bipartite any more. However if you want to combine them with each other 65#' (or other bipartite graphs), then it is worth keeping this attribute. By 66#' default it will be removed. 67#' @return A list of two undirected graphs. See details above. 68#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 69#' @export 70#' @keywords graphs 71#' @examples 72#' 73#' ## Projection of a full bipartite graph is a full graph 74#' g <- make_full_bipartite_graph(10,5) 75#' proj <- bipartite_projection(g) 76#' graph.isomorphic(proj[[1]], make_full_graph(10)) 77#' graph.isomorphic(proj[[2]], make_full_graph(5)) 78#' 79#' ## The projection keeps the vertex attributes 80#' M <- matrix(0, nr=5, nc=3) 81#' rownames(M) <- c("Alice", "Bob", "Cecil", "Dan", "Ethel") 82#' colnames(M) <- c("Party", "Skiing", "Badminton") 83#' M[] <- sample(0:1, length(M), replace=TRUE) 84#' M 85#' g2 <- graph_from_incidence_matrix(M) 86#' g2$name <- "Event network" 87#' proj2 <- bipartite_projection(g2) 88#' print(proj2[[1]], g=TRUE, e=TRUE) 89#' print(proj2[[2]], g=TRUE, e=TRUE) 90#' 91bipartite_projection <- function(graph, types=NULL, 92 multiplicity=TRUE, probe1=NULL, 93 which=c("both", "true", "false"), 94 remove.type=TRUE) { 95 # Argument checks 96 if (!is_igraph(graph)) { stop("Not a graph object") } 97 types <- handle_vertex_type_arg(types, graph) 98 if (!is.null(probe1)) { 99 probe1 <- as.igraph.vs(graph, probe1)-1 100 } else { 101 probe1 <- -1 102 } 103 which <- switch(igraph.match.arg(which), "both"=0L, "false"=1L, 104 "true"=2L) 105 if (which != "both" && probe1 != -1) { 106 warning("`probe1' ignored if only one projection is requested") 107 } 108 109 on.exit( .Call(C_R_igraph_finalizer) ) 110 # Function call 111 res <- .Call(C_R_igraph_bipartite_projection, graph, types, 112 as.integer(probe1), which) 113 if (remove.type) { 114 if (is_igraph(res[[1]])) { 115 res[[1]] <- delete_vertex_attr(res[[1]], "type") 116 } 117 if (is_igraph(res[[2]])) { 118 res[[2]] <- delete_vertex_attr(res[[2]], "type") 119 } 120 } 121 if (which == 0L) { 122 if (multiplicity) { 123 E(res[[1]])$weight <- res[[3]] 124 E(res[[2]])$weight <- res[[4]] 125 } 126 res[1:2] 127 } else if (which == 1L) { 128 if (multiplicity) { E(res[[1]])$weight <- res[[3]] } 129 res[[1]] 130 } else { 131 if (multiplicity) { E(res[[2]])$weight <- res[[4]] } 132 res[[2]] 133 } 134} 135 136 137#' Decide whether a graph is bipartite 138#' 139#' This function decides whether the vertices of a network can be mapped to two 140#' vertex types in a way that no vertices of the same type are connected. 141#' 142#' A bipartite graph in igraph has a \sQuote{\code{type}} vertex attribute 143#' giving the two vertex types. 144#' 145#' This function simply checks whether a graph \emph{could} be bipartite. It 146#' tries to find a mapping that gives a possible division of the vertices into 147#' two classes, such that no two vertices of the same class are connected by an 148#' edge. 149#' 150#' The existence of such a mapping is equivalent of having no circuits of odd 151#' length in the graph. A graph with loop edges cannot bipartite. 152#' 153#' Note that the mapping is not necessarily unique, e.g. if the graph has at 154#' least two components, then the vertices in the separate components can be 155#' mapped independently. 156#' 157#' @aliases bipartite.mapping bipartite_mapping 158#' @param graph The input graph. 159#' @return A named list with two elements: \item{res}{A logical scalar, 160#' \code{TRUE} if the can be bipartite, \code{FALSE} otherwise.} \item{type}{A 161#' possible vertex type mapping, a logical vector. If no such mapping exists, 162#' then an empty vector.} 163#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 164#' @keywords graphs 165#' @examples 166#' 167#' ## Rings with an even number of vertices are bipartite 168#' g <- make_ring(10) 169#' bipartite_mapping(g) 170#' 171#' ## All star graphs are bipartite 172#' g2 <- make_star(10) 173#' bipartite_mapping(g2) 174#' 175#' ## A graph containing a triangle is not bipartite 176#' g3 <- make_ring(10) 177#' g3 <- add_edges(g3, c(1,3)) 178#' bipartite_mapping(g3) 179#' @export 180 181bipartite_mapping <- bipartite_mapping 182