# Chapter 13. Bipartite, i.e. two-mode graphs

## 1. Bipartite networks in igraph

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.

## 2. Create two-mode networks

### 2.1. `igraph_create_bipartite` — Create a bipartite graph.

    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:

`graph`: | Pointer to an uninitialized graph object, the result is created here.
`types`: | Boolean vector giving the vertex types. The length of the vector defines the number of vertices in the graph.
`edges`: | Vector giving the edges of the graph. The highest vertex ID in this vector must be smaller than the length of the `types` vector.
`directed`: | Boolean, whether to create a directed graph.

Returns:

`` | Error code.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

Example 13.1. File `examples/simple/igraph_bipartite_create.c`

    #include <igraph.h>

    int main(void) {
        igraph_t g;
        igraph_int_t edges_array[] = {0, 1, 1, 2, 3, 4, 5, 6, 6, 5, 1, 4, 1, 6, 0, 3 };
        igraph_vector_int_t edges =
            igraph_vector_int_view(edges_array, sizeof(edges_array) / sizeof(edges_array[0]));
        igraph_vector_bool_t types;

        /* Initialize the library. */
        igraph_setup();

        igraph_vector_bool_init(&types, igraph_vector_int_max(&edges) + 1);
        for (igraph_int_t i = 0; i < igraph_vector_bool_size(&types); i++) {
            VECTOR(types)[i] = i % 2;
        }
        igraph_create_bipartite(&g, &types, &edges, IGRAPH_DIRECTED);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_vector_bool_destroy(&types);
        igraph_destroy(&g);

        return 0;
    }

### 2.2. `igraph_full_bipartite` — Creates a complete bipartite graph.

    igraph_error_t igraph_full_bipartite(igraph_t *graph,
                              igraph_vector_bool_t *types,
                              igraph_int_t n1, igraph_int_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:

`graph`: | Pointer to an uninitialized graph object, the graph will be created here.
`types`: | Pointer to a boolean vector. If not a null pointer, then the vertex types will be stored here.
`n1`: | Integer, the number of vertices of the first kind.
`n2`: | Integer, the number of vertices of the second kind.
`directed`: | Boolean, whether to create a directed graph.
`mode`: | A constant that gives the type of connections for directed graphs. If `IGRAPH_OUT`, then edges point from vertices of the first kind to vertices of the second kind; if `IGRAPH_IN`, then the opposite direction is realized; if `IGRAPH_ALL`, then mutual edges will be created.

Returns:

`` | Error code.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

See also:

`` | `igraph_full()` for non-bipartite complete graphs, `igraph_full_multipartite()` for complete multipartite graphs.

### 2.3. `igraph_bipartite_game_gnm` — Generate a random bipartite graph with a fixed number of edges.

    igraph_error_t igraph_bipartite_game_gnm(
            igraph_t *graph,
            igraph_vector_bool_t *types,
            igraph_int_t n1, igraph_int_t n2, igraph_int_t m,
            igraph_bool_t directed, igraph_neimode_t mode,
            igraph_edge_type_sw_t allowed_edge_types,
            igraph_bool_t edge_labeled);

The `G(n1, n2, m)` model uniformly samples bipartite graphs with `n1` bottom vertices and `n2` top vertices, and precisely `m` edges.

Arguments:

`graph`: | Pointer to an uninitialized igraph graph, the result is stored here.
`types`: | 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.
`n1`: | The number of bottom vertices.
`n2`: | The number of top vertices.
`m`: | The number of edges.
`directed`: | Boolean, whether to generate a directed graph. See also the `mode` argument.

`mode`:

Specifies how to direct the edges in directed graphs. If it is `IGRAPH_OUT`, then directed edges point from bottom vertices to top vertices. If it is `IGRAPH_IN`, edges point from top vertices to bottom vertices. `IGRAPH_OUT` and `IGRAPH_IN` do not generate mutual edges. If this argument is `IGRAPH_ALL`, then each edge direction is considered independently and mutual edges might be generated. This argument is ignored for undirected graphs. *

`allowed_edge_types`:

The types of edges to allow in the graph.

`IGRAPH_SIMPLE_SW` | simple graph (i.e. no multi-edges allowed).
`IGRAPH_MULTI_SW` | multi-edges are allowed

`edge_labeled`: | If true, the sampling is done uniformly from the set of ordered edge lists. See `igraph_bipartite_iea_game()` for more information. Set this to `false` to select the classic Erdős-Rényi model. The constants `IGRAPH_EDGE_UNLABELED` and `IGRAPH_EDGE_LABELED` may be used instead of `false` and `true` for better readability.

Returns:

`` | Error code.

See also:

`` | `igraph_erdos_renyi_game_gnm()` for the unipartite version, `igraph_bipartite_game_gnp()` for the `G(n1, n2, p)` model.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

### 2.4. `igraph_bipartite_game_gnp` — Generates a random bipartite graph with a fixed connection probability.

    igraph_error_t igraph_bipartite_game_gnp(
            igraph_t *graph,
            igraph_vector_bool_t *types,
            igraph_int_t n1, igraph_int_t n2, igraph_real_t p,
            igraph_bool_t directed, igraph_neimode_t mode,
            igraph_edge_type_sw_t allowed_edge_types,
            igraph_bool_t edge_labeled);

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`. This is equivalent to a maximum entropy model with a constraint on the expected total edge count. This view allows a multigraph extension, in which case `is` interpreted as the expected number of edges between any vertex pair. See `igraph_erdos_renyi_game_gnp()` for more details.

Arguments:

`graph`: | Pointer to an uninitialized igraph graph, the result is stored here.
`types`: | Pointer to an initialized boolean vector, or a null pointer. If not `NULL`, then the vertex types are stored here. Bottom vertices come first, `n1` of them, then `n2` top vertices.
`n1`: | The number of bottom vertices.
`n2`: | The number of top vertices.
`p`: | The expected number of edges between any vertex pair. When multi-edges are disallowed, this is equivalent to the probability of having a connection between any two vertices.
`directed`: | Whether to generate a directed graph. See also the `mode` argument.

`mode`:

Specifies how to direct the edges in directed graphs. If it is `IGRAPH_OUT`, then directed edges point from bottom vertices to top vertices. If it is `IGRAPH_IN`, edges point from top vertices to bottom vertices. `IGRAPH_OUT` and `IGRAPH_IN` do not generate mutual edges. If this argument is `IGRAPH_ALL`, then each edge direction is considered independently and mutual edges might be generated. This argument is ignored for undirected graphs. *

`allowed_edge_types`:

The types of edges to allow in the graph.

`IGRAPH_SIMPLE_SW` | simple graph (i.e. no multi-edges allowed).
`IGRAPH_MULTI_SW` | multi-edges are allowed

`edge_labeled`: | If true, the model is defined over the set of ordered edge lists, i.e. over the set of edge-labeled graphs. Set it to `false` to select the classic bipartite Erdős-Rényi model. The constants `IGRAPH_EDGE_UNLABELED` and `IGRAPH_EDGE_LABELED` may be used instead of `false` and `true` for better readability.

Returns:

`` | Error code.

See also:

`` | `igraph_erdos_renyi_game_gnp()` for the unipartite version, `igraph_bipartite_game_gnm()` for the `G(n1, n2, m)` model.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

### 2.5. `igraph_bipartite_iea_game` — Generates a random bipartite multigraph through independent edge assignment.

    igraph_error_t igraph_bipartite_iea_game(
            igraph_t *graph, igraph_vector_bool_t *types,
            igraph_int_t n1, igraph_int_t n2, igraph_int_t m,
            igraph_bool_t directed, igraph_neimode_t mode);

### Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

This model generates random multigraphs with `n1` bottom vertices, `n2` top vertices and `m` edges through independent edge assignment (IEA). Each of the `m` edges is assigned uniformly at random to a vertex pair, independently of each other.

This model does not sample multigraphs uniformly. Undirected graphs are generated with probability proportional to

`(prod_(i<j) A_ij !)^(-1)`,

where `A` denotes the adjacency matrix. The corresponding expression for directed graphs is

`(prod_(i,j) A_ij !)^(-1)`.

Thus the probability of all simple graphs (which only have 0s and 1s in the adjacency matrix) is the same, while that of non-simple ones depends on their edge and self-loop multiplicities.

Arguments:

`graph`: | Pointer to an uninitialized igraph graph, the result is stored here.
`types`: | Pointer to an initialized boolean vector, or a `NULL` pointer. If not `NULL`, then the vertex types are stored here. Bottom vertices come first, `n1` of them, then `n2` top vertices.
`n1`: | The number of bottom vertices.
`n2`: | The number of top vertices.
`m`: | The number of edges.
`directed`: | Whether to generate a directed graph. See also the `mode` argument.

`mode`:

Specifies how to direct the edges in directed graphs. If it is `IGRAPH_OUT`, then directed edges point from bottom vertices to top vertices. If it is `IGRAPH_IN`, edges point from top vertices to bottom vertices. `IGRAPH_OUT` and `IGRAPH_IN` do not generate mutual edges. If this argument is `IGRAPH_ALL`, then each edge direction is considered independently and mutual edges might be generated. This argument is ignored for undirected graphs.

Returns:

`` | Error code.

See also:

`` | `igraph_iea_game()` for the unipartite version; `igraph_bipartite_game_gnm()` to uniformly sample bipartite graphs with a given number of vertices and edges.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

## 3. Bipartite adjacency matrices

### 3.1. `igraph_biadjacency` — Creates a bipartite graph from a bipartite adjacency matrix.

    igraph_error_t igraph_biadjacency(
            igraph_t *graph,
            igraph_vector_bool_t *types,
            const igraph_matrix_t *biadjmatrix,
            igraph_bool_t directed,
            igraph_neimode_t mode,
            igraph_bool_t multiple);

A bipartite (or two-mode) 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.

This function can operate in two modes, depending on the `multiple` argument. If it is `false`, then a single edge is created for every non-zero element in the bipartite adjacency matrix. If `multiple` is `true`, then as many edges are created between two vertices as the corresponding matrix element. When `multiple` is set to `true`, matrix elements should be whole numbers. Otherwise their fractional part will be discarded.

Arguments:

`graph`: | Pointer to an uninitialized graph object.
`types`: | 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.
`biadjmatrix`: | The bipartite adjacency matrix that serves as an input to this function.
`directed`: | Specifies whether to create an undirected or a directed graph.
`mode`: | Specifies the direction of the edges in a directed graph. If `IGRAPH_OUT`, then edges point from vertices of the first kind (corresponding to rows) to vertices of the second kind (corresponding to columns); if `IGRAPH_IN`, then the opposite direction is realized; if `IGRAPH_ALL`, then mutual edges will be created.
`multiple`: | Whether to interpret matrix entries as edge multiplicities, see details above.

Returns:

`` | Error code.

Time complexity: O(n*m), the size of the bipartite adjacency matrix.

### 3.2. `igraph_weighted_biadjacency` — Creates a bipartite graph from a weighted bipartite adjacency matrix.

    igraph_error_t igraph_weighted_biadjacency(
            igraph_t *graph,
            igraph_vector_bool_t *types,
            igraph_vector_t *weights,
            const igraph_matrix_t *biadjmatrix,
            igraph_bool_t directed,
            igraph_neimode_t mode);

A bipartite (or two-mode) 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.

Arguments:

`graph`: | Pointer to an uninitialized graph object.
`types`: | 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.
`weights`: | Pointer to an initialized vector, the weights will be stored here.
`biadjmatrix`: | The bipartite adjacency matrix that serves as an input to this function.
`directed`: | Specifies whether to create an undirected or a directed graph.
`mode`: | Specifies the direction of the edges in a directed graph. If `IGRAPH_OUT`, then edges point from vertices of the first kind (corresponding to rows) to vertices of the second kind (corresponding to columns); if `IGRAPH_IN`, then the opposite direction is realized; if `IGRAPH_ALL`, then mutual edges will be created.

Returns:

`` | Error code.

Time complexity: O(n*m), the size of the bipartite adjacency matrix.

### 3.3. `igraph_get_biadjacency` — Converts a bipartite graph into a bipartite adjacency matrix.

    igraph_error_t igraph_get_biadjacency(
        const igraph_t *graph, const igraph_vector_bool_t *types,
        const igraph_vector_t *weights,
        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:

`graph`: | The input graph, edge directions are ignored.
`types`: | Boolean vector containing the vertex types. Vertices belonging to the first partition have type `false`, the one in the second partition type `true`.
`weights`: | A vector specifying a weight for each edge or `NULL`. If `NULL`, all edges are assumed to have weight 1.
`res`: | Pointer to an initialized matrix, the result is stored here. An element of the matrix gives the number of edges (irrespectively of their direction), or sum of edge weights, between the two corresponding vertices. The rows will correspond to vertices with type `false`, the columns correspond to vertices with type `true`.
`row_ids`: | Pointer to an initialized vector or `NULL`. If not a null pointer, then the IDs of vertices with type `false` are stored here, with the same ordering as the rows of the biadjacency matrix.
`col_ids`: | Pointer to an initialized vector or `NULL`. If not a null pointer, then the IDs of vertices with type `true` are stored here, with the same ordering as the columns of the biadjacency matrix.

Returns:

`` | Error code.

Time complexity: O(|E|) where |E| is the number of edges.

See also:

`` | `igraph_biadjacency()` for the opposite operation.

## 4. Project two-mode graphs

### 4.1. `igraph_bipartite_projection_size` — Calculate the number of vertices and edges in the bipartite projections.

    igraph_error_t igraph_bipartite_projection_size(const igraph_t *graph,
                                         const igraph_vector_bool_t *types,
                                         igraph_int_t *vcount1,
                                         igraph_int_t *ecount1,
                                         igraph_int_t *vcount2,
                                         igraph_int_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:

`graph`: | The input graph.
`types`: | Boolean vector giving the vertex types of the graph.
`vcount1`: | Pointer to an `igraph_int_t`, the number of vertices in the first projection is stored here. May be `NULL` if not needed.
`ecount1`: | Pointer to an `igraph_int_t`, the number of edges in the first projection is stored here. May be `NULL` if not needed.
`vcount2`: | Pointer to an `igraph_int_t`, the number of vertices in the second projection is stored here. May be `NULL` if not needed.
`ecount2`: | Pointer to an `igraph_int_t`, the number of edges in the second projection is stored here. May be `NULL` if not needed.

Returns:

`` | Error code.

See also:

`` | `igraph_bipartite_projection()` to calculate the actual projection.

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.

### 4.2. `igraph_bipartite_projection` — Create one or both projections of a bipartite (two-mode) network.

    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_int_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:

`graph`: | The bipartite input graph. Directedness of the edges is ignored.
`types`: | Boolean vector giving the vertex types of the graph.
`proj1`: | Pointer to an uninitialized graph object, the first projection will be created here. It a null pointer, then it is ignored, see also the `probe1` argument.
`proj2`: | Pointer to an uninitialized graph object, the second projection is created here, if it is not a null pointer. See also the `probe1` argument.
`multiplicity1`: | 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 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.
`multiplicity2`: | The same as `multiplicity1`, but for the other projection.

`probe1`:

This argument can be used to specify the order of the projections in the resulting list. When it is non-negative, 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 non-negative value implies that `proj1` must be a non-null pointer. If you don't care about the ordering of the projections, pass -1 here.

Returns:

`` | Error code.

See also:

`` | `igraph_bipartite_projection_size()` to calculate the number of vertices and edges in the projections, without creating the projection graphs themselves.

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.

## 5. Other operations on bipartite graphs

### 5.1. `igraph_is_bipartite` — Check whether a graph is bipartite.

    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:

`graph`: | The input graph.
`res`: | Pointer to a boolean, the result is stored here.
`types`: | 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.

See also:

`` | igraph_is_bipartite_coloring() to determine if all edges connect vertices of different types, given a specific type vector.