igraph Reference Manual

For using the igraph C library

Search the manual:

Chapter 31. 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.

int igraph_create_bipartite(igraph_t *graph, const igraph_vector_bool_t *types,
                            const igraph_vector_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 scalar, whether to create a directed graph.

Returns: 

Error code.

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

Example 31.1.  File examples/simple/igraph_bipartite_create.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2008-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

*/

#include <igraph.h>

int main() {

    igraph_real_t edges2[] = {0, 1, 1, 2, 3, 4, 5, 6, 6, 5, 1, 4, 1, 6, 0, 3 };
    igraph_real_t edges3[] = {0, 1, 1, 2, 3, 4, 5, 6, 6, 5, 2, 4, 1, 6, 0, 3 };
    igraph_t g;
    igraph_vector_bool_t types;
    igraph_vector_t edges;
    long int i;
    int ret;

    igraph_vector_view(&edges, edges2, sizeof(edges2) / sizeof(igraph_real_t));
    igraph_vector_bool_init(&types, igraph_vector_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);

    /* Error handling */
    igraph_set_error_handler(igraph_error_handler_ignore);

    igraph_vector_view(&edges, edges3, sizeof(edges3) / sizeof(igraph_real_t));
    igraph_vector_bool_init(&types, igraph_vector_max(&edges) + 1);
    for (i = 0; i < igraph_vector_bool_size(&types); i++) {
        VECTOR(types)[i] = i % 2;
    }
    ret = igraph_create_bipartite(&g, &types, &edges, /*directed=*/ 1);
    if (ret != IGRAPH_EINVAL) {
        return 1;
    }
    igraph_vector_bool_destroy(&types);
    igraph_destroy(&g);

    return 0;
}


2.2. igraph_full_bipartite — Create a full bipartite network.

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

graph:

Pointer to an igraph_t 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 full graphs.

2.3. igraph_bipartite_game — Generate a bipartite random graph (similar to Erdős-Rényi).

int 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);

Similarly to unipartite (one-mode) networks, we can define the G(n,p), and G(n,m) graph classes for bipartite graphs, via their generating process. In G(n,p) every possible edge between top and bottom vertices is realized with probablity p, independently of the rest of the edges. In G(n,m), we uniformly choose m edges to realize.

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.

type:

The type of the random graph, possible values:

IGRAPH_ERDOS_RENYI_GNM

G(n,m) graph, m edges are selected uniformly randomly in a graph with n vertices.

IGRAPH_ERDOS_RENYI_GNP

G(n,p) graph, every possible edge is included in the graph with probability p.

n1:

The number of bottom vertices.

n2:

The number of top verices.

p:

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

m:

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

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.

Returns: 

Error code.

See also: 

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

3. Incidence matrices

3.1. igraph_incidence — Creates a bipartite graph from an incidence matrix.

int 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);

A bipartite (or two-mode) graph contains two types of vertices and edges always connect vertices of different types. An incidence matrix is an nxm 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 (i.e. 0), then a single edge is created for every non-zero element in the incidence matrix. If multiple is TRUE (i.e. 1), then the matrix elements are rounded up to the closest non-negative 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: 

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.

incidence:

The incidence matrix.

directed:

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

How to interpret the incidence matrix elements. See details below.

Returns: 

Error code.

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

3.2. igraph_get_incidence — Convert a bipartite graph into an incidence matrix.

int igraph_get_incidence(const igraph_t *graph,
                         const igraph_vector_bool_t *types,
                         igraph_matrix_t *res,
                         igraph_vector_t *row_ids,
                         igraph_vector_t *col_ids);

Arguments: 

graph:

The input graph, edge directions are ignored.

types:

Boolean vector containing the vertex types. All vertices in one part of the graph should have type 0, the others type 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) between the two corresponding vertices. The rows will correspond to vertices with type 0, the columns correspond to vertices with type 1.

row_ids:

Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex ids (in the graph) corresponding to the rows of the result matrix are stored here.

col_ids:

Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex ids corresponding to the columns of the result matrix are stored here.

Returns: 

Error code.

Time complexity: O(n*m), n and m are number of vertices of the two different kind.

See also: 

igraph_incidence() 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.

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

graph:

The input graph.

types:

Boolean vector giving the vertex types of the graph.

vcount1:

Pointer to an igraph_integer_t, the number of vertices in the first projection is stored here.

ecount1:

Pointer to an igraph_integer_t, the number of edges in the first projection is stored here.

vcount2:

Pointer to an igraph_integer_t, the number of vertices in the second projection is stored here.

ecount2:

Pointer to an igraph_integer_t, the number of edges in the second projection is stored here.

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.

Example 31.2.  File examples/simple/igraph_bipartite_projection.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2008-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

*/

#include <igraph.h>
#include <stdlib.h>

int check_projection(const igraph_t *graph,
                     const igraph_vector_bool_t *types,
                     const igraph_t *proj1,
                     const igraph_t *proj2) {
    igraph_integer_t vcount1, ecount1, vcount2, ecount2;
    igraph_bipartite_projection_size(graph, types, &vcount1, &ecount1,
                                     &vcount2, &ecount2);
    if (proj1 && igraph_vcount(proj1) != vcount1) {
        exit(10);
    }
    if (proj1 && igraph_ecount(proj1) != ecount1) {
        exit(11);
    }
    if (proj2 && igraph_vcount(proj2) != vcount2) {
        exit(12);
    }
    if (proj2 && igraph_ecount(proj2) != ecount2) {
        exit(13);
    }
    return 0;
}

int main() {

    igraph_t g, p1, p2, full, ring;
    igraph_vector_bool_t types;
    igraph_bool_t iso;
    long int i, m2 = 0, w, f, t;
    igraph_vector_t mult1, mult2;

    /*******************************************************/
    /* Full bipartite graph -> full graphs                 */
    /*******************************************************/

    igraph_vector_bool_init(&types, 0);
    igraph_full_bipartite(&g, &types, 5, 3, /*directed=*/ 0,
                          /*mode=*/ IGRAPH_ALL);

    /* Get both projections */
    igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
    check_projection(&g, &types, &p1, &p2);

    /* Check first projection */
    igraph_full(&full, igraph_vcount(&p1), /*directed=*/0, /*loops=*/0);
    igraph_isomorphic_bliss(&p1, &full, 0, 0, &iso, 0, 0,
                            IGRAPH_BLISS_FM, 0, 0);
    if (!iso) {
        return 1;
    }
    igraph_destroy(&full);

    /* Check second projection */
    igraph_full(&full, igraph_vcount(&p2), /*directed=*/0, /*loops=*/0);
    igraph_isomorphic_bliss(&p2, &full, 0, 0, &iso, 0, 0,
                            IGRAPH_BLISS_FM, 0, 0);
    if (!iso) {
        return 2;
    }
    igraph_destroy(&full);

    igraph_destroy(&p1);
    igraph_destroy(&p2);
    igraph_destroy(&g);
    igraph_vector_bool_destroy(&types);

    /*******************************************************/
    /* More sophisticated test                             */
    /*******************************************************/

    igraph_ring(&g, 100, /*directed=*/ 1, /*mutual=*/ 1,
                /*circular=*/ 1);
    igraph_vector_bool_init(&types, igraph_vcount(&g));
    for (i = 0; i < igraph_vector_bool_size(&types); i++) {
        VECTOR(types)[i] = i % 2 ? 0 : 1;
    }

    /* Get both projections */
    igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
    check_projection(&g, &types, &p1, &p2);

    /* Check first projection */
    igraph_ring(&ring, igraph_vcount(&g) / 2, /*directed=*/ 0,
                /*mutual=*/ 0, /*circular=*/ 1);
    igraph_isomorphic_bliss(&p1, &ring, 0, 0, &iso, 0, 0,
                            IGRAPH_BLISS_FM, 0, 0);
    if (!iso) {
        return 1;
    }

    /* Check second projection */
    igraph_isomorphic_bliss(&p2, &ring, 0, 0, &iso, 0, 0,
                            IGRAPH_BLISS_FM, 0, 0);
    if (!iso) {
        return 2;
    }
    igraph_destroy(&ring);

    igraph_destroy(&p1);
    igraph_destroy(&p2);
    igraph_destroy(&g);
    igraph_vector_bool_destroy(&types);

    /*******************************************************/
    /* Multiplicity test                                   */
    /*******************************************************/

    igraph_small(&g, 10, IGRAPH_UNDIRECTED,
                 0, 8, 1, 8, 2, 8, 3, 8, 4, 8, 4, 9, 5, 9, 6, 9, 7, 9, 0, 9,
                 -1);
    igraph_vector_bool_init(&types, igraph_vcount(&g));
    igraph_vector_bool_fill(&types, 1);
    VECTOR(types)[8] = VECTOR(types)[9] = 0;

    igraph_vector_init(&mult1, 0);
    igraph_vector_init(&mult2, 0);
    igraph_bipartite_projection(&g, &types, &p1, &p2, &mult1, &mult2,
                                /*probe=*/ -1);
    check_projection(&g, &types, &p1, &p2);

    if (igraph_vector_size(&mult1) != igraph_ecount(&p1)) {
        return 21;
    }
    if (igraph_vector_size(&mult2) != igraph_ecount(&p2)) {
        return 22;
    }
    if (VECTOR(mult1)[0] != 2) {
        return 23;
    }
    for (i = 0; i < igraph_vector_size(&mult2); i++) {
        if (VECTOR(mult2)[i] != 1 && VECTOR(mult2)[i] != 2) {
            return 24;
        }
        if (VECTOR(mult2)[i] == 2) {
            m2++;
            w = i;
        }
    }
    if (m2 != 1) {
        return 25;
    }
    f = IGRAPH_FROM(&p2, w);
    t = IGRAPH_TO(&p2, w);
    if (fmin(f, t) != 0 || fmax(f, t) != 4) {
        return 26;
    }

    igraph_vector_destroy(&mult1);
    igraph_vector_destroy(&mult2);
    igraph_destroy(&p1);
    igraph_destroy(&p2);
    igraph_destroy(&g);
    igraph_vector_bool_destroy(&types);

    return 0;
}


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

int igraph_bipartite_projection(const igraph_t *graph,
                                const igraph_vector_bool_t *types,
                                igraph_t *proj1,
                                igraph_t *proj2,
                                igraph_vector_t *multiplicity1,
                                igraph_vector_t *multiplicity2,
                                igraph_integer_t probe1);

Creates one or both projections of a bipartite graph.

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.

Example 31.3.  File examples/simple/igraph_bipartite_projection.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2008-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

*/

#include <igraph.h>
#include <stdlib.h>

int check_projection(const igraph_t *graph,
                     const igraph_vector_bool_t *types,
                     const igraph_t *proj1,
                     const igraph_t *proj2) {
    igraph_integer_t vcount1, ecount1, vcount2, ecount2;
    igraph_bipartite_projection_size(graph, types, &vcount1, &ecount1,
                                     &vcount2, &ecount2);
    if (proj1 && igraph_vcount(proj1) != vcount1) {
        exit(10);
    }
    if (proj1 && igraph_ecount(proj1) != ecount1) {
        exit(11);
    }
    if (proj2 && igraph_vcount(proj2) != vcount2) {
        exit(12);
    }
    if (proj2 && igraph_ecount(proj2) != ecount2) {
        exit(13);
    }
    return 0;
}

int main() {

    igraph_t g, p1, p2, full, ring;
    igraph_vector_bool_t types;
    igraph_bool_t iso;
    long int i, m2 = 0, w, f, t;
    igraph_vector_t mult1, mult2;

    /*******************************************************/
    /* Full bipartite graph -> full graphs                 */
    /*******************************************************/

    igraph_vector_bool_init(&types, 0);
    igraph_full_bipartite(&g, &types, 5, 3, /*directed=*/ 0,
                          /*mode=*/ IGRAPH_ALL);

    /* Get both projections */
    igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
    check_projection(&g, &types, &p1, &p2);

    /* Check first projection */
    igraph_full(&full, igraph_vcount(&p1), /*directed=*/0, /*loops=*/0);
    igraph_isomorphic_bliss(&p1, &full, 0, 0, &iso, 0, 0,
                            IGRAPH_BLISS_FM, 0, 0);
    if (!iso) {
        return 1;
    }
    igraph_destroy(&full);

    /* Check second projection */
    igraph_full(&full, igraph_vcount(&p2), /*directed=*/0, /*loops=*/0);
    igraph_isomorphic_bliss(&p2, &full, 0, 0, &iso, 0, 0,
                            IGRAPH_BLISS_FM, 0, 0);
    if (!iso) {
        return 2;
    }
    igraph_destroy(&full);

    igraph_destroy(&p1);
    igraph_destroy(&p2);
    igraph_destroy(&g);
    igraph_vector_bool_destroy(&types);

    /*******************************************************/
    /* More sophisticated test                             */
    /*******************************************************/

    igraph_ring(&g, 100, /*directed=*/ 1, /*mutual=*/ 1,
                /*circular=*/ 1);
    igraph_vector_bool_init(&types, igraph_vcount(&g));
    for (i = 0; i < igraph_vector_bool_size(&types); i++) {
        VECTOR(types)[i] = i % 2 ? 0 : 1;
    }

    /* Get both projections */
    igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
    check_projection(&g, &types, &p1, &p2);

    /* Check first projection */
    igraph_ring(&ring, igraph_vcount(&g) / 2, /*directed=*/ 0,
                /*mutual=*/ 0, /*circular=*/ 1);
    igraph_isomorphic_bliss(&p1, &ring, 0, 0, &iso, 0, 0,
                            IGRAPH_BLISS_FM, 0, 0);
    if (!iso) {
        return 1;
    }

    /* Check second projection */
    igraph_isomorphic_bliss(&p2, &ring, 0, 0, &iso, 0, 0,
                            IGRAPH_BLISS_FM, 0, 0);
    if (!iso) {
        return 2;
    }
    igraph_destroy(&ring);

    igraph_destroy(&p1);
    igraph_destroy(&p2);
    igraph_destroy(&g);
    igraph_vector_bool_destroy(&types);

    /*******************************************************/
    /* Multiplicity test                                   */
    /*******************************************************/

    igraph_small(&g, 10, IGRAPH_UNDIRECTED,
                 0, 8, 1, 8, 2, 8, 3, 8, 4, 8, 4, 9, 5, 9, 6, 9, 7, 9, 0, 9,
                 -1);
    igraph_vector_bool_init(&types, igraph_vcount(&g));
    igraph_vector_bool_fill(&types, 1);
    VECTOR(types)[8] = VECTOR(types)[9] = 0;

    igraph_vector_init(&mult1, 0);
    igraph_vector_init(&mult2, 0);
    igraph_bipartite_projection(&g, &types, &p1, &p2, &mult1, &mult2,
                                /*probe=*/ -1);
    check_projection(&g, &types, &p1, &p2);

    if (igraph_vector_size(&mult1) != igraph_ecount(&p1)) {
        return 21;
    }
    if (igraph_vector_size(&mult2) != igraph_ecount(&p2)) {
        return 22;
    }
    if (VECTOR(mult1)[0] != 2) {
        return 23;
    }
    for (i = 0; i < igraph_vector_size(&mult2); i++) {
        if (VECTOR(mult2)[i] != 1 && VECTOR(mult2)[i] != 2) {
            return 24;
        }
        if (VECTOR(mult2)[i] == 2) {
            m2++;
            w = i;
        }
    }
    if (m2 != 1) {
        return 25;
    }
    f = IGRAPH_FROM(&p2, w);
    t = IGRAPH_TO(&p2, w);
    if (fmin(f, t) != 0 || fmax(f, t) != 4) {
        return 26;
    }

    igraph_vector_destroy(&mult1);
    igraph_vector_destroy(&mult2);
    igraph_destroy(&p1);
    igraph_destroy(&p2);
    igraph_destroy(&g);
    igraph_vector_bool_destroy(&types);

    return 0;
}


5. Other operations on bipartite graphs

5.1. igraph_is_bipartite — Check whether a graph is bipartite.

int 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.