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