1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
# 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. 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("R_igraph_finalizer", PACKAGE="igraph") )
# Function call
res <- .Call("R_igraph_bipartite_projection", graph, types,
as.integer(probe1), which, PACKAGE="igraph")
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
|
