For using the igraph C library
A bipartite network contains two kinds of vertices and connections are only possible between two vertices of different kinds. There are many natural examples, e.g. movies and actors as vertices and a movie is connected to all participating actors, etc.
igraph does not have direct support for bipartite networks, at
least not at the C language level. In other words the igraph_t
structure does not contain information about the vertex types.
The C functions for bipartite networks usually have an additional
input argument to graph, called types
, a boolean vector giving
the vertex types.
Most functions creating bipartite networks are able to create this extra vector, you just need to supply an initialized boolean vector to them.
igraph_create_bipartite
— Create a bipartite graph.igraph_full_bipartite
— Creates a complete bipartite graph.igraph_bipartite_game_gnm
— Generate a random bipartite graph with a fixed number of edges.igraph_bipartite_game_gnp
— Generates a random bipartite graph with a fixed connection probability.
igraph_error_t igraph_create_bipartite(igraph_t *graph, const igraph_vector_bool_t *types, const igraph_vector_int_t *edges, igraph_bool_t directed);
This is a simple wrapper function to create a bipartite graph. It
does a little more than igraph_create()
, e.g. it checks that
the graph is indeed bipartite with respect to the given types
vector. If there is an edge connecting two vertices of the same
kind, then an error is reported.
Arguments:

Pointer to an uninitialized graph object, the result is created here. 

Boolean vector giving the vertex types. The length of the vector defines the number of vertices in the graph. 

Vector giving the edges of the graph. The highest
vertex ID in this vector must be smaller than the length of the


Boolean, whether to create a directed graph. 
Returns:
Error code. 
Time complexity: O(V+E), linear in the number of vertices and edges.
Example 30.1. File examples/simple/igraph_bipartite_create.c
#include <igraph.h> int main(void) { igraph_integer_t edges2[] = {0, 1, 1, 2, 3, 4, 5, 6, 6, 5, 1, 4, 1, 6, 0, 3 }; igraph_t g; igraph_vector_bool_t types; igraph_vector_int_t edges; igraph_integer_t i; igraph_vector_int_view(&edges, edges2, sizeof(edges2) / sizeof(edges2[0])); igraph_vector_bool_init(&types, igraph_vector_int_max(&edges) + 1); for (i = 0; i < igraph_vector_bool_size(&types); i++) { VECTOR(types)[i] = i % 2; } igraph_create_bipartite(&g, &types, &edges, /*directed=*/ 1); igraph_write_graph_edgelist(&g, stdout); igraph_vector_bool_destroy(&types); igraph_destroy(&g); return 0; }
igraph_error_t igraph_full_bipartite(igraph_t *graph, igraph_vector_bool_t *types, igraph_integer_t n1, igraph_integer_t n2, igraph_bool_t directed, igraph_neimode_t mode);
A bipartite network contains two kinds of vertices and connections are only possible between two vertices of different kind. There are many natural examples, e.g. movies and actors as vertices and a movie is connected to all participating actors, etc.
igraph does not have direct support for bipartite networks, at
least not at the C language level. In other words the igraph_t
structure does not contain information about the vertex types.
The C functions for bipartite networks usually have an additional
input argument to graph, called types
, a boolean vector giving
the vertex types.
Most functions creating bipartite networks are able to create this extra vector, you just need to supply an initialized boolean vector to them.
Arguments:

Pointer to an uninitialized graph object, the graph will be created here. 

Pointer to a boolean vector. If not a null pointer, then the vertex types will be stored here. 

Integer, the number of vertices of the first kind. 

Integer, the number of vertices of the second kind. 

Boolean, whether to create a directed graph. 

A constant that gives the type of connections for
directed graphs. If 
Returns:
Error code. 
Time complexity: O(V+E), linear in the number of vertices and edges.
See also:

igraph_error_t igraph_bipartite_game_gnm(igraph_t *graph, igraph_vector_bool_t *types, igraph_integer_t n1, igraph_integer_t n2, igraph_integer_t m, igraph_bool_t directed, igraph_neimode_t mode);
The G(n1, n2, m)
model uniformly samples bipartite graphs with
n1
bottom vertices and n2
top vertices, and precisely m
edges.
Arguments:

Pointer to an uninitialized igraph graph, the result is stored here. 

Pointer to an initialized boolean vector, or a null
pointer. If not a null pointer, then the vertex types are stored
here. Bottom vertices come first, 

The number of bottom vertices. 

The number of top vertices. 

The number of edges. 

Boolean, whether to generate a directed graph. See
also the 

Specifies how to direct the edges in directed
graphs. If it is 
Returns:
Error code. 
See also:

Time complexity: O(V+E), linear in the number of vertices and edges.
igraph_error_t igraph_bipartite_game_gnp(igraph_t *graph, igraph_vector_bool_t *types, igraph_integer_t n1, igraph_integer_t n2, igraph_real_t p, igraph_bool_t directed, igraph_neimode_t mode);
In the G(n1, n2, p)
model, every possible edge between the n1
bottom vertices and n2
top vertices is realized independently with
probability p
.
Arguments:

Pointer to an uninitialized igraph graph, the result is stored here. 

Pointer to an initialized boolean vector, or a null
pointer. If not 

The number of bottom vertices. 

The number of top vertices. 

The connection probability. 

Boolean, whether to generate a directed graph. See
also the 

Specifies how to direct the edges in directed
graphs. If it is 
Returns:
Error code. 
See also:

Time complexity: O(V+E), linear in the number of vertices and edges.
igraph_error_t igraph_biadjacency( igraph_t *graph, igraph_vector_bool_t *types, const igraph_matrix_t *input, igraph_bool_t directed, igraph_neimode_t mode, igraph_bool_t multiple );
A bipartite (or twomode) graph contains two types of vertices and edges always connect vertices of different types. A bipartite adjacency matrix is an n x m matrix, n and m are the number of vertices of the two types, respectively. Nonzero elements in the matrix denote edges between the two corresponding vertices.
Note that this function can operate in two modes, depending on the
multiple
argument. If it is false
, then a single edge is
created for every nonzero element in the bipartite adjacency matrix. If multiple
is true
, then the matrix elements are rounded up
to the closest nonnegative integer to get the number of edges to
create between a pair of vertices.
This function does not create multiple edges if multiple
is
false
, but might create some if it is true
.
Arguments:

Pointer to an uninitialized graph object. 

Pointer to an initialized boolean vector, or a null pointer. If not a null pointer, then the vertex types are stored here. It is resized as needed. 

The bipartite adjacency matrix that serves as an input to this function. 

Specifies whether to create an undirected or a directed graph. 

Specifies the direction of the edges in a directed
graph. If 

How to interpret the matrix elements. See details above. 
Returns:
Error code. 
Time complexity: O(n*m), the size of the bipartite adjacency matrix.
igraph_error_t igraph_get_biadjacency( const igraph_t *graph, const igraph_vector_bool_t *types, igraph_matrix_t *res, igraph_vector_int_t *row_ids, igraph_vector_int_t *col_ids );
In a bipartite adjacency matrix A
, element A_ij
gives the number of edges between the i
th vertex of the
first partition and the j
th vertex of the second partition.
If the graph contains edges within the same partition, this function issues a warning.
Arguments:

The input graph, edge directions are ignored. 

Boolean vector containing the vertex types. Vertices belonging
to the first partition have type 

Pointer to an initialized matrix, the result is stored
here. An element of the matrix gives the number of edges
(irrespectively of their direction) between the two corresponding
vertices. The rows will correspond to vertices with type 

Pointer to an initialized vector or 

Pointer to an initialized vector or 
Returns:
Error code. 
Time complexity: O(E) where E is the number of edges.
See also:

igraph_error_t igraph_bipartite_projection_size(const igraph_t *graph, const igraph_vector_bool_t *types, igraph_integer_t *vcount1, igraph_integer_t *ecount1, igraph_integer_t *vcount2, igraph_integer_t *ecount2);
This function calculates the number of vertices and edges in the two projections of a bipartite network. This is useful if you have a big bipartite network and you want to estimate the amount of memory you would need to calculate the projections themselves.
Arguments:

The input graph. 

Boolean vector giving the vertex types of the graph. 

Pointer to an 

Pointer to an 

Pointer to an 

Pointer to an 
Returns:
Error code. 
See also:

Time complexity: O(V*d^2+E), V is the number of vertices, E is the number of edges, d is the average (total) degree of the graphs.
igraph_error_t igraph_bipartite_projection(const igraph_t *graph, const igraph_vector_bool_t *types, igraph_t *proj1, igraph_t *proj2, igraph_vector_int_t *multiplicity1, igraph_vector_int_t *multiplicity2, igraph_integer_t probe1);
Creates one or both projections of a bipartite graph.
A graph is called bipartite if its vertices can be partitioned into
two sets, V1 and V2, so that connections only run between V1 and V2,
but not within V1 or within V2. The types
parameter specifies
which vertex should be considered a member of one or the other
partition. The projection to V1 has vertex set V1, and two vertices
are connected if they have at least one common neighbour in V2.
The number of common neighbours is returned in multiplicity1
,
if requested.
Arguments:

The bipartite input graph. Directedness of the edges is ignored. 

Boolean vector giving the vertex types of the graph. 

Pointer to an uninitialized graph object, the first
projection will be created here. It a null pointer, then it is
ignored, see also the 

Pointer to an uninitialized graph object, the second
projection is created here, if it is not a null pointer. See also
the 

Pointer to a vector, or a null pointer. If not the latter, then the multiplicity of the edges is stored here. E.g. if there is an ACB and also an ADB triple in the bipartite graph (but no more X, such that AXB is also in the graph), then the multiplicity of the AB edge in the projection will be 2. 

The same as 

This argument can be used to specify the order of the
projections in the resulting list. When it is nonnegative, then
it is considered as a vertex ID and the projection containing
this vertex will be the first one in the result. Setting this
argument to a nonnegative value implies that 
Returns:
Error code. 
See also:

Time complexity: O(V*d^2+E), V is the number of vertices, E is the number of edges, d is the average (total) degree of the graphs.
igraph_error_t igraph_is_bipartite(const igraph_t *graph, igraph_bool_t *res, igraph_vector_bool_t *types);
This function checks whether a graph is 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 be 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.
Arguments:

The input graph. 

Pointer to a boolean, the result is stored here. 

Pointer to an initialized boolean vector, or a null pointer. If not a null pointer and a mapping was found, then it is stored here. If not a null pointer, but no mapping was found, the contents of this vector is invalid. 
Returns:
Error code. 
Time complexity: O(V+E), linear in the number of vertices and edges.
igraph_bipartite_game
— Generate a bipartite random graph (similar to ErdősRényi).igraph_incidence
— Creates a bipartite graph from a bipartite adjacency matrix (deprecated alias).igraph_get_incidence
— Convert a bipartite graph into a bipartite adjacency matrix (deprecated alias).
igraph_error_t igraph_bipartite_game(igraph_t *graph, igraph_vector_bool_t *types, igraph_erdos_renyi_t type, igraph_integer_t n1, igraph_integer_t n2, igraph_real_t p, igraph_integer_t m, igraph_bool_t directed, igraph_neimode_t mode);
This function is deprecated; use igraph_bipartite_game_gnm()
or
igraph_bipartite_game_gnp()
instead.
Arguments:

Pointer to an uninitialized igraph graph, the result is stored here. 


Pointer to an initialized boolean vector, or a null pointer. If not a null pointer, then the vertex types are stored here. Bottom vertices come first, n1 of them, then n2 top vertices. 


The type of the random graph, possible values:



The number of bottom vertices. 


The number of top vertices. 


The connection probability for G(n,p) graphs. It is ignored for G(n,m) graphs. 


The number of edges for G(n,m) graphs. It is ignored for G(n,p) graphs. 


Boolean, whether to generate a directed graph. See
also the 


Specifies how to direct the edges in directed
graphs. If it is 
Returns:
Error code. 
See also:
Time complexity: O(V+E), linear in the number of vertices and edges.
igraph_error_t igraph_incidence( igraph_t *graph, igraph_vector_bool_t *types, const igraph_matrix_t *incidence, igraph_bool_t directed, igraph_neimode_t mode, igraph_bool_t multiple );
Deprecated since version 0.10.5. Please do not use this function in new
code; use igraph_biadjacency()
instead.
igraph_error_t igraph_get_incidence(const igraph_t *graph, const igraph_vector_bool_t *types, igraph_matrix_t *res, igraph_vector_int_t *row_ids, igraph_vector_int_t *col_ids);
Deprecated since version 0.10.5. Please do not use this function in new
code; use igraph_get_biadjacency()
instead.
← Chapter 29. Using BLAS, LAPACK and ARPACK for igraph matrices and graphs  Chapter 31. Advanced igraph programming → 