dev/R_igraph/bipartite.R

In kbodwin/longnet: What the Package Does (One Line, Title Case)

#   IGraph R package
#   Copyright (C) 2009-2012  Gabor Csardi <csardi.gabor@gmail.com>
#   334 Harvard street, Cambridge, MA 02139 USA
#   
#   This program is free software; you can redistribute it and/or modify
#   it under the terms of the GNU General Public License as published by
#   the Free Software Foundation; either version 2 of the License, or
#   (at your option) any later version.
#
#   This program is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU General Public License for more details.
#   
#   You should have received a copy of the GNU General Public License
#   along with this program; if not, write to the Free Software
#   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA
#   02110-1301 USA
#
###################################################################



#' Project a bipartite graph
#' 
#' A bipartite graph is projected into two one-mode networks
#' 
#' Bipartite graphs have a \code{type} vertex attribute in igraph, this is
#' boolean and \code{FALSE} for the vertices of the first kind and \code{TRUE}
#' for vertices of the second kind.
#' 
#' \code{bipartite_projection_size} calculates the number of vertices and edges
#' in the two projections of the bipartite graphs, without calculating the
#' projections themselves. This is useful to check how much memory the
#' projections would need if you have a large bipartite graph.
#' 
#' \code{bipartite_projection} calculates the actual projections.  You can use
#' the \code{probe1} argument to specify the order of the projections in the
#' result. By default vertex type \code{FALSE} is the first and \code{TRUE} is
#' the second.
#' 
#' \code{bipartite_projection} keeps vertex attributes.
#' 
#' @aliases bipartite.projection bipartite.projection.size bipartite_projection_size bipartite_projection
#' @param graph The input graph. It can be directed, but edge directions are
#' ignored during the computation.
#' @param types An optional vertex type vector to use instead of the
#' \sQuote{\code{type}} vertex attribute. You must supply this argument if the
#' graph has no \sQuote{\code{type}} vertex attribute.
#' @param multiplicity If \code{TRUE}, then igraph keeps the multiplicity of
#' the edges as an edge attribute called \sQuote{weight}.
#' E.g. if there is an A-C-B and also an A-D-B
#' triple in the bipartite graph (but no more X, such that A-X-B is also in the
#' graph), then the multiplicity of the A-B edge in the projection will be 2.
#' @param probe1 This argument can be used to specify the order of the
#' projections in the resulting list. If given, then it is considered as a
#' vertex id (or a symbolic vertex name); the projection containing this vertex
#' will be the first one in the result list.  This argument is ignored if only
#' one projection is requested in argument \code{which}.
#' @param which A character scalar to specify which projection(s) to calculate.
#' The default is to calculate both.
#' @param remove.type Logical scalar, whether to remove the \code{type} vertex
#' attribute from the projections. This makes sense because these graphs are
#' not bipartite any more. However if you want to combine them with each other
#' (or other bipartite graphs), then it is worth keeping this attribute. By
#' default it will be removed.
#' @return A list of two undirected graphs. See details above.
#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
#' @export
#' @keywords graphs
#' @examples
#' 
#' ## Projection of a full bipartite graph is a full graph
#' g <- make_full_bipartite_graph(10,5)
#' proj <- bipartite_projection(g)
#' graph.isomorphic(proj[[1]], make_full_graph(10))
#' graph.isomorphic(proj[[2]], make_full_graph(5))
#' 
#' ## The projection keeps the vertex attributes
#' M <- matrix(0, nr=5, nc=3)
#' rownames(M) <- c("Alice", "Bob", "Cecil", "Dan", "Ethel")
#' colnames(M) <- c("Party", "Skiing", "Badminton")
#' M[] <- sample(0:1, length(M), replace=TRUE)
#' M
#' g2 <- graph_from_incidence_matrix(M)
#' g2$name <- "Event network"
#' proj2 <- bipartite_projection(g2)
#' print(proj2[[1]], g=TRUE, e=TRUE)
#' print(proj2[[2]], g=TRUE, e=TRUE)
#' 
bipartite_projection <- function(graph, types=NULL,
                                 multiplicity=TRUE, probe1=NULL,
				 which=c("both", "true", "false"),
                                 remove.type=TRUE) {
  # Argument checks
  if (!is_igraph(graph)) { stop("Not a graph object") }
  if (is.null(types) && "type" %in% vertex_attr_names(graph)) { 
  types <- V(graph)$type 
  } 
  if (!is.null(types)) {
    if (!is.logical(types)) {
      warning("vertex types converted to logical")
    }
    types <- as.logical(types)
    if (any(is.na(types))) {
      stop("`NA' is not allowed in vertex types")
    }
  } else { 
  stop("Not a bipartite graph, supply `types' argument") 
  }
  if (!is.null(probe1)) {
    probe1 <- as.igraph.vs(graph, probe1)-1
  } else {
    probe1 <- -1
  }
  which <- switch(igraph.match.arg(which), "both"=0L, "false"=1L,
                  "true"=2L)
  if (which != "both" && probe1 != -1) {
    warning("`probe1' ignored if only one projection is requested")
  }

  on.exit( .Call(C_R_igraph_finalizer) )
  # Function call
  res <- .Call(C_R_igraph_bipartite_projection, graph, types,
               as.integer(probe1), which)
  if (remove.type) {
    if (is_igraph(res[[1]])) {
      res[[1]] <- delete_vertex_attr(res[[1]], "type")
    }
    if (is_igraph(res[[2]])) {
      res[[2]] <- delete_vertex_attr(res[[2]], "type")
    }
  }
  if (which == 0L) {
    if (multiplicity) {
      E(res[[1]])$weight <- res[[3]]
      E(res[[2]])$weight <- res[[4]]
    }
    res[1:2]
  } else if (which == 1L) {
    if (multiplicity) { E(res[[1]])$weight <- res[[3]] }
    res[[1]]
  } else {
    if (multiplicity) { E(res[[2]])$weight <- res[[4]] }
    res[[2]]
  }
}


#' Decide whether a graph is bipartite
#' 
#' This function decides whether the vertices of a network can be mapped to two
#' vertex types in a way that no vertices of the same type are connected.
#' 
#' A bipartite graph in igraph has a \sQuote{\code{type}} vertex attribute
#' giving the two vertex types.
#' 
#' This function simply checks whether a graph \emph{could} be bipartite. It
#' tries to find a mapping that gives a possible division of the vertices into
#' two classes, such that no two vertices of the same class are connected by an
#' edge.
#' 
#' The existence of such a mapping is equivalent of having no circuits of odd
#' length in the graph. A graph with loop edges cannot bipartite.
#' 
#' Note that the mapping is not necessarily unique, e.g. if the graph has at
#' least two components, then the vertices in the separate components can be
#' mapped independently.
#' 
#' @aliases bipartite.mapping bipartite_mapping
#' @param graph The input graph.
#' @return A named list with two elements: \item{res}{A logical scalar,
#' \code{TRUE} if the can be bipartite, \code{FALSE} otherwise.} \item{type}{A
#' possibly vertex type mapping, a logical vector. If no such mapping exists,
#' then an empty vector.}
#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
#' @keywords graphs
#' @examples
#' 
#' ## A ring has just one loop, so it is fine
#' g <- make_ring(10)
#' bipartite_mapping(g)
#' 
#' ## A star is fine, too
#' g2 <- make_star(10)
#' bipartite_mapping(g2)
#' 
#' ## A graph containing a triangle is not fine
#' g3 <- make_ring(10)
#' g3 <- add_edges(g3, c(1,3))
#' bipartite_mapping(g3)
#' @export

bipartite_mapping <- bipartite_mapping