# Chapter 15. Graph operators

## 1. Union and intersection

### 1.1. `igraph_disjoint_union` — Creates the union of two disjoint graphs.

    igraph_error_t igraph_disjoint_union(igraph_t *res,
                                         const igraph_t *left,
                                         const igraph_t *right);

First the vertices of the second graph will be relabeled with new vertex IDs to have two disjoint sets of vertex IDs, then the union of the two graphs will be formed. If the two graphs have |V1| and |V2| vertices and |E1| and |E2| edges respectively then the new graph will have |V1|+|V2| vertices and |E1|+|E2| edges.

The vertex and edge ordering of the graphs will be preserved. In other words, the vertex and edge IDs of the first graph map to identical values in the new graph, while the vertex and edge IDs of the second graph map to IDs incremented by the vertex and edge count of the first graph.

Both graphs need to have the same directedness, i.e. either both directed or both undirected.

The current version of this function cannot handle graph, vertex and edge attributes, they will be lost.

Arguments:

`res`: | Pointer to an uninitialized graph object, the result will stored here.
`left`: | The first graph.
`right`: | The second graph.

Returns:

`` | Error code.

See also:

`` | `igraph_disjoint_union_many()` for creating the disjoint union of more than two graphs, `igraph_union()` for non-disjoint union.

Time complexity: O(|V1|+|V2|+|E1|+|E2|).

Example 15.1. File `examples/simple/igraph_disjoint_union.c`

    #include <igraph.h>
    #include <stdio.h>

    int main(void) {
        igraph_t left, right, uni;
        igraph_vector_ptr_t glist;
        igraph_int_t i, n;

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

        igraph_small(&left, 4, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,2, 2,3, -1);
        igraph_small(&right, 5, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,2, 2,4, -1);

        igraph_disjoint_union(&uni, &left, &right);
        igraph_write_graph_edgelist(&uni, stdout);
        printf("\n");

        igraph_destroy(&left);
        igraph_destroy(&right);
        igraph_destroy(&uni);

        /* Empty graph list; the result is the directed null graph. */
        igraph_vector_ptr_init(&glist, 0);
        igraph_disjoint_union_many(&uni, &glist);
        if (!igraph_is_directed(&uni) || igraph_vcount(&uni) != 0) {
            return 1;
        }
        igraph_vector_ptr_destroy(&glist);
        igraph_destroy(&uni);

        /* Non-empty graph list. */
        igraph_vector_ptr_init(&glist, 10);
        n = igraph_vector_ptr_size(&glist);
        for (i = 0; i < n; i++) {
            VECTOR(glist)[i] = calloc(1, sizeof(igraph_t));
            igraph_small(VECTOR(glist)[i], 2, IGRAPH_DIRECTED, 0,1, 1,0, -1);
        }
        if (!igraph_is_directed(&uni)) {
            return 2;
        }

        igraph_disjoint_union_many(&uni, &glist);
        igraph_write_graph_edgelist(&uni, stdout);
        printf("\n");

        /* Destroy and free the graph list. */
        n = igraph_vector_ptr_size(&glist);
        for (i = 0; i < n; i++) {
            igraph_destroy(VECTOR(glist)[i]);
            free(VECTOR(glist)[i]);
        }
        igraph_vector_ptr_destroy(&glist);
        igraph_destroy(&uni);

        return 0;
    }

### 1.2. `igraph_disjoint_union_many` — The disjoint union of many graphs.

    igraph_error_t igraph_disjoint_union_many(igraph_t *res,
                                              const igraph_vector_ptr_t *graphs);

First the vertices in the graphs will be relabeled with new vertex IDs to have pairwise disjoint vertex ID sets and then the union of the graphs is formed. The number of vertices and edges in the result is the total number of vertices and edges in the graphs.

The vertex and edge ordering of the input graphs is preserved in the output graph.

All graphs need to have the same directedness, i.e. either all directed or all undirected. If the graph list has length zero, the result will be a directed graph with no vertices.

The current version of this function cannot handle graph, vertex and edge attributes, they will be lost.

Arguments:

`res`: | Pointer to an uninitialized graph object, the result of the operation will be stored here.
`graphs`: | Pointer vector, contains pointers to initialized graph objects.

Returns:

`` | Error code.

See also:

`` | `igraph_disjoint_union()` for an easier syntax if you have only two graphs, `igraph_union_many()` for non-disjoint union.

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

### 1.3. `igraph_join` — Creates the join of two disjoint graphs.

    igraph_error_t igraph_join(igraph_t *res,
                               const igraph_t *left,
                               const igraph_t *right);

First the vertices of the second graph will be relabeled with new vertex IDs to have two disjoint sets of vertex IDs, then the union of the two graphs will be formed. Finally, the vertces from the first graph will have edges added to each vertex from the second. If the two graphs have |V1| and |V2| vertices and |E1| and |E2| edges respectively then the new graph will have |V1|+|V2| vertices and |E1|+|E2|+|V1|*|V2| edges.

The vertex ordering of the graphs will be preserved. In other words, the vertex IDs of the first graph map to identical values in the new graph, while the vertex IDs of the second graph map to IDs incremented by the vertex count of the first graph. The new edges will be grouped with the other edges that share a from vertex.

Both graphs need to have the same directedness, i.e. either both directed or both undirected. If both graphs are directed, then for each vertex v, u in graphs G1, G2 we add edges (v, u), (u, v) to maintain completeness.

The current version of this function cannot handle graph, vertex and edge attributes, they will be lost.

Arguments:

`res`: | Pointer to an uninitialized graph object, the result will be stored here.
`left`: | The first graph.
`right`: | The second graph.

Returns:

`` | Error code.

Time complexity: O(|V1|*|V2|+|E1|+|E2|).

### 1.4. `igraph_union` — Calculates the union of two graphs.

    igraph_error_t igraph_union(
            igraph_t *res,
            const igraph_t *left, const igraph_t *right,
            igraph_vector_int_t *edge_map1, igraph_vector_int_t *edge_map2);

The number of vertices in the result is that of the larger graph from the two arguments. The result graph contains edges which are present in at least one of the operand graphs.

The directedness of the operand graphs must be the same.

Edge multiplicities are handled by taking the larger of the two multiplicities in the input graphs. In other words, if the first graph has N edges between a vertex pair (u, v) and the second graph has M edges, the result graph will have max(N, M) edges between them.

Arguments:

`res`: | Pointer to an uninitialized graph object, the result will be stored here.
`left`: | The first graph.
`right`: | The second graph.
`edge_map1`: | Pointer to an initialized vector or a null pointer. If not a null pointer, it will contain a mapping from the edges of the first argument graph (`left`) to the edges of the result graph.
`edge_map2`: | The same as `edge_map1`, but for the second graph, `right`.

Returns:

`` | Error code.

See also:

`` | `igraph_union_many()` for the union of many graphs, `igraph_intersection()` and `igraph_difference()` for other operators.

Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| the number of edges in the result graph.

Example 15.2. File `examples/simple/igraph_union.c`

    #include <igraph.h>
    #include <stdio.h>

    int main(void) {
        igraph_t left, right, uni;
        igraph_vector_int_t edge_map1, edge_map2;

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

        igraph_vector_int_init(&edge_map1, 0);
        igraph_vector_int_init(&edge_map2, 0);

        igraph_small(&left, 4, IGRAPH_DIRECTED,
                     0,1, 1,2, 2,2, 2,3, 2,3, 3,2,
                     -1);

        igraph_small(&right, 6, IGRAPH_DIRECTED,
                     0,1, 1,2, 2,2, 2,3, 5,2,
                     -1);

        igraph_union(&uni, &left, &right, &edge_map1, &edge_map2);
        igraph_write_graph_edgelist(&uni, stdout);
        igraph_vector_int_print(&edge_map1);
        igraph_vector_int_print(&edge_map2);

        igraph_destroy(&uni);
        igraph_destroy(&left);
        igraph_destroy(&right);

        igraph_vector_int_destroy(&edge_map2);
        igraph_vector_int_destroy(&edge_map1);

        return 0;
    }

### 1.5. `igraph_union_many` — Creates the union of many graphs.

    igraph_error_t igraph_union_many(
        igraph_t *res, const igraph_vector_ptr_t *graphs,
        igraph_vector_int_list_t *edgemaps
    );

The result graph will contain as many vertices as the largest graph among the arguments does, and an edge will be included in it if it is part of at least one operand graph.

The number of vertices in the result graph will be the maximum number of vertices in the argument graphs.

The directedness of the argument graphs must be the same. If the graph list has length zero, the result will be a directed graph with no vertices.

Edge multiplicities are handled by taking the maximum multiplicity of the all multiplicities for the same vertex pair (u, v) in the input graphs; this will be the multiplicity of (u, v) in the result graph.

Arguments:

`res`: | Pointer to an uninitialized graph object, this will contain the result.
`graphs`: | Pointer vector, contains pointers to the operands of the union operator, graph objects of course.
`edgemaps`: | If not a null pointer, then it must be an initialized list of integer vectors, and the mappings of edges from the graphs to the result graph will be stored here, in the same order as `graphs`. Each mapping is stored in a separate igraph_vector_int_t object.

Returns:

`` | Error code.

See also:

`` | `igraph_union()` for the union of two graphs, `igraph_intersection_many()`, `igraph_intersection()` and `igraph_difference` for other operators.

Time complexity: O(|V|+|E|), |V| is the number of vertices in largest graph and |E| is the number of edges in the result graph.

### 1.6. `igraph_intersection` — Collect the common edges from two graphs.

    igraph_error_t igraph_intersection(
            igraph_t *res,
            const igraph_t *left, const igraph_t *right,
            igraph_vector_int_t *edge_map1, igraph_vector_int_t *edge_map2);

The result graph contains only edges present both in the first and the second graph. The number of vertices in the result graph is the same as the larger from the two arguments.

The directedness of the operand graphs must be the same.

Edge multiplicities are handled by taking the smaller of the two multiplicities in the input graphs. In other words, if the first graph has N edges between a vertex pair (u, v) and the second graph has M edges, the result graph will have min(N, M) edges between them.

Arguments:

`res`: | Pointer to an uninitialized graph object. This will contain the result of the operation.
`left`: | The first operand, a graph object.
`right`: | The second operand, a graph object.
`edge_map1`: | Null pointer, or an initialized vector. If the latter, then a mapping from the edges of the result graph, to the edges of the `left` input graph is stored here. For the edges that are not in the intersection, -1 is stored.
`edge_map2`: | Null pointer, or an initialized vector. The same as `edge_map1`, but for the `right` input graph. For the edges that are not in the intersection, -1 is stored.

Returns:

`` | Error code.

See also:

`` | `igraph_intersection_many()` to calculate the intersection of many graphs at once, `igraph_union()`, `igraph_difference()` for other operators.

Time complexity: O(|V|+|E|), |V| is the number of nodes, |E| is the number of edges in the smaller graph of the two. (The one containing less vertices is considered smaller.)

Example 15.3. File `examples/simple/igraph_intersection.c`

    #include <igraph.h>

    void print_vector(igraph_vector_t *v) {
        igraph_int_t i, l = igraph_vector_size(v);
        for (i = 0; i < l; i++) {
            printf(" %" IGRAPH_PRId "", (igraph_int_t) VECTOR(*v)[i]);
        }
        printf("\n");
    }

    int main(void) {

        igraph_t left, right, isec;
        igraph_vector_int_t v;
        igraph_vector_ptr_t glist;
        igraph_t g1, g2, g3;
        igraph_vector_int_t edge_map1, edge_map2;

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

        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 3, -1);
        igraph_create(&left, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_vector_int_init_int_end(&v, -1, 1, 0, 5, 4, 1, 2, 3, 2, -1);
        igraph_create(&right, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_vector_int_init(&edge_map1, 0);
        igraph_vector_int_init(&edge_map2, 0);

        igraph_intersection(&isec, &left, &right, &edge_map1, &edge_map2);
        igraph_vector_int_init(&v, 0);
        igraph_get_edgelist(&isec, &v, 0);
        printf("---\n");
        igraph_vector_int_print(&v);
        igraph_vector_int_print(&edge_map1);
        igraph_vector_int_print(&edge_map2);
        printf("---\n");
        igraph_vector_int_destroy(&v);
        igraph_destroy(&left);
        igraph_destroy(&right);
        igraph_destroy(&isec);
        igraph_vector_int_destroy(&edge_map1);
        igraph_vector_int_destroy(&edge_map2);

        /* empty graph list */
        igraph_vector_ptr_init(&glist, 0);
        igraph_intersection_many(&isec, &glist, 0);
        if (igraph_vcount(&isec) != 0 || !igraph_is_directed(&isec)) {
            return 1;
        }
        igraph_destroy(&isec);
        igraph_vector_ptr_destroy(&glist);

        /* graph list with an empty graph */
        igraph_vector_ptr_init(&glist, 3);
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 3, -1);
        igraph_create(&g1, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 3, -1);
        igraph_create(&g2, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);
        igraph_empty(&g3, 10, IGRAPH_DIRECTED);

        VECTOR(glist)[0] = &g1;
        VECTOR(glist)[1] = &g2;
        VECTOR(glist)[2] = &g3;
        igraph_intersection_many(&isec, &glist, 0);
        if (igraph_ecount(&isec) != 0 || igraph_vcount(&isec) != 10) {
            return 2;
        }
        igraph_destroy(&g1);
        igraph_destroy(&g2);
        igraph_destroy(&g3);
        igraph_destroy(&isec);
        igraph_vector_ptr_destroy(&glist);

        /* "proper" graph list */
        igraph_vector_ptr_init(&glist, 3);
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 3, -1);
        igraph_create(&g1, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 3, 3, 2, 4, 5, 6, 5, -1);
        igraph_create(&g2, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);
        igraph_vector_int_init_int_end(&v, -1, 2, 3, 1, 0, 1, 2, 3, 2, 4, 5, 6, 5, 2, 3, -1);
        igraph_create(&g3, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        VECTOR(glist)[0] = &g1;
        VECTOR(glist)[1] = &g2;
        VECTOR(glist)[2] = &g3;
        igraph_intersection_many(&isec, &glist, 0);
        igraph_write_graph_edgelist(&isec, stdout);
        igraph_destroy(&g1);
        igraph_destroy(&g2);
        igraph_destroy(&g3);
        igraph_destroy(&isec);
        igraph_vector_ptr_destroy(&glist);

        return 0;
    }

### 1.7. `igraph_intersection_many` — The intersection of more than two graphs.

    igraph_error_t igraph_intersection_many(
        igraph_t *res, const igraph_vector_ptr_t *graphs,
        igraph_vector_int_list_t *edgemaps
    );

This function calculates the intersection of the graphs stored in the `graphs` argument. Only those edges will be included in the result graph which are part of every graph in `graphs`.

The number of vertices in the result graph will be the maximum number of vertices in the argument graphs.

The directedness of the argument graphs must be the same. If the graph list has length zero, the result will be a directed graph with no vertices.

Edge multiplicities are handled by taking the minimum multiplicity of the all multiplicities for the same vertex pair (u, v) in the input graphs; this will be the multiplicity of (u, v) in the result graph.

Arguments:

`res`: | Pointer to an uninitialized graph object, the result of the operation will be stored here.
`graphs`: | Pointer vector, contains pointers to graphs objects, the operands of the intersection operator.
`edgemaps`: | If not a null pointer, then it must be an initialized list of integer vectors, and the mappings of edges from the graphs to the result graph will be stored here, in the same order as `graphs`. Each mapping is stored in a separate igraph_vector_int_t object. For the edges that are not in the intersection, -1 is stored.

Returns:

`` | Error code.

See also:

`` | `igraph_intersection()` for the intersection of two graphs, `igraph_union_many()`, `igraph_union()` and `igraph_difference()` for other operators.

Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| is the number of edges in the smallest graph (i.e. the graph having the less vertices).

## 2. Other set-like operators

### 2.1. `igraph_difference` — Calculates the difference of two graphs.

    igraph_error_t igraph_difference(igraph_t *res,
                          const igraph_t *orig, const igraph_t *sub);

The number of vertices in the result is the number of vertices in the original graph, i.e. the left, first operand. In the results graph only edges will be included from `orig` which are not present in `sub`.

Arguments:

`res`: | Pointer to an uninitialized graph object, the result will be stored here.
`orig`: | The left operand of the operator, a graph object.
`sub`: | The right operand of the operator, a graph object.

Returns:

`` | Error code.

See also:

`` | `igraph_intersection()` and `igraph_union()` for other operators.

Time complexity: O(|V|+|E|), |V| is the number vertices in the smaller graph, |E| is the number of edges in the result graph.

Example 15.4. File `examples/simple/igraph_difference.c`

    #include <igraph.h>

    int main(void) {
        igraph_t orig, sub, diff;
        igraph_vector_int_t v;

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

        /* Subtract from itself */
        printf("subtract itself\n");
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 1, 4, 5, -1);
        igraph_create(&orig, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_difference(&diff, &orig, &orig);
        igraph_write_graph_edgelist(&diff, stdout);
        if (igraph_ecount(&diff) != 0 ||
            igraph_vcount(&diff) != igraph_vcount(&orig)) {
            return 1;
        }

        igraph_destroy(&orig);
        igraph_destroy(&diff);

        /* Same for undirected graph */
        printf("subtract itself, undirected\n");
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 1, 4, 5, -1);
        igraph_create(&orig, &v, 0, IGRAPH_UNDIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_vector_int_init_int_end(&v, -1, 1, 0, 1, 2, 2, 1, 4, 5, -1);
        igraph_create(&sub, &v, 0, IGRAPH_UNDIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_difference(&diff, &orig, &sub);
        igraph_write_graph_edgelist(&diff, stdout);
        if (igraph_ecount(&diff) != 0 ||
            igraph_vcount(&diff) != igraph_vcount(&orig)) {
            return 2;
        }

        igraph_destroy(&orig);
        igraph_destroy(&sub);
        igraph_destroy(&diff);

        /* Subtract the empty graph */
        printf("subtract empty\n");
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 1, 4, 5, -1);
        igraph_create(&orig, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_empty(&sub, 3, IGRAPH_DIRECTED);
        igraph_difference(&diff, &orig, &sub);
        igraph_write_graph_edgelist(&diff, stdout);
        if (igraph_ecount(&diff) != igraph_ecount(&orig) ||
            igraph_vcount(&diff) != igraph_vcount(&orig)) {
            return 3;
        }

        igraph_destroy(&orig);
        igraph_destroy(&sub);
        igraph_destroy(&diff);

        /* A `real' example */
        printf("real example\n");
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 1, 4, 5, 8, 9, -1);
        igraph_create(&orig, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_vector_int_init_int_end(&v, -1, 0, 1, 5, 4, 2, 1, 6, 7, -1);
        igraph_create(&sub, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_difference(&diff, &orig, &sub);
        igraph_write_graph_edgelist(&diff, stdout);

        igraph_destroy(&diff);
        igraph_destroy(&orig);
        igraph_destroy(&sub);

        /* undirected version */
        printf("real example, undirected\n");
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 1, 4, 5, 8, 9, 8, 10, 8, 13, 8, 11, 8, 12, -1);
        igraph_create(&orig, &v, 0, IGRAPH_UNDIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_vector_int_init_int_end(&v, -1, 0, 1, 5, 4, 2, 1, 6, 7, 8, 10, 8, 13, -1);
        igraph_create(&sub, &v, 0, IGRAPH_UNDIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_difference(&diff, &orig, &sub);
        igraph_write_graph_edgelist(&diff, stdout);

        igraph_destroy(&diff);
        igraph_destroy(&orig);
        igraph_destroy(&sub);

        /* undirected version with loop edge, tests Github issue #597 */
        printf("Github issue #597, undirected\n");
        igraph_vector_int_init_int_end(&v, -1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 0, -1);
        igraph_create(&orig, &v, 0, IGRAPH_UNDIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 2, 3, 3, 4, 4, 0, -1);
        igraph_create(&sub, &v, 0, IGRAPH_UNDIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_difference(&diff, &orig, &sub);
        igraph_write_graph_edgelist(&diff, stdout);

        igraph_destroy(&diff);
        igraph_destroy(&orig);
        igraph_destroy(&sub);

        return 0;
    }

### 2.2. `igraph_complementer` — Creates the complementer of a graph.

    igraph_error_t igraph_complementer(igraph_t *res, const igraph_t *graph,
                            igraph_bool_t loops);

The complementer graph means that all edges which are not part of the original graph will be included in the result.

Arguments:

`res`: | Pointer to an uninitialized graph object.
`graph`: | The original graph.
`loops`: | Whether to add loop edges to the complementer graph.

Returns:

`` | Error code.

See also:

`` | `igraph_union()`, `igraph_intersection()` and `igraph_difference()`.

Time complexity: O(|V|+|E1|+|E2|), |V| is the number of vertices in the graph, |E1| is the number of edges in the original and |E2| in the complementer graph.

Example 15.5. File `examples/simple/igraph_complementer.c`

    #include <igraph.h>

    int main(void) {

        igraph_t g1, g2;

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

        /* complementer of the empty graph */
        igraph_empty(&g1, 5, IGRAPH_DIRECTED);
        igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
        igraph_write_graph_edgelist(&g2, stdout);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        printf("---\n");

        /* the same without loops */
        igraph_empty(&g1, 5, IGRAPH_DIRECTED);
        igraph_complementer(&g2, &g1, IGRAPH_NO_LOOPS);
        igraph_write_graph_edgelist(&g2, stdout);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        printf("---\n");

        /* complementer of the full graph */
        igraph_full(&g1, 5, IGRAPH_DIRECTED, IGRAPH_LOOPS);
        igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
        if (igraph_ecount(&g2) != 0) {
            return 1;
        }
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        printf("---\n");

        /* complementer of the full graph, results loops only */
        igraph_full(&g1, 5, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
        igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
        igraph_write_graph_edgelist(&g2, stdout);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        printf("---\n");

        /**************
         * undirected *
         *************/

        /* complementer of the empty graph */
        igraph_empty(&g1, 5, IGRAPH_UNDIRECTED);
        igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
        igraph_write_graph_edgelist(&g2, stdout);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        printf("---\n");

        /* the same without loops */
        igraph_empty(&g1, 5, IGRAPH_UNDIRECTED);
        igraph_complementer(&g2, &g1, IGRAPH_NO_LOOPS);
        igraph_write_graph_edgelist(&g2, stdout);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        printf("---\n");

        /* complementer of the full graph */
        igraph_full(&g1, 5, IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
        igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
        if (igraph_ecount(&g2) != 0) {
            return 1;
        }
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        printf("---\n");

        /* complementer of the full graph, results loops only */
        igraph_full(&g1, 5, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
        igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
        igraph_write_graph_edgelist(&g2, stdout);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        return 0;
    }

### 2.3. `igraph_compose` — Calculates the composition of two graphs.

    igraph_error_t igraph_compose(igraph_t *res,
                                  const igraph_t *g1,
                                  const igraph_t *g2,
                                  igraph_vector_int_t *edge_map1,
                                  igraph_vector_int_t *edge_map2);

The composition of graphs contains the same number of vertices as the bigger graph of the two operands. It contains an (i,j) edge if and only if there is a k vertex, such that the first graph contains an (i,k) edge and the second graph a (k,j) edge.

This is of course exactly the composition of two binary relations.

The two graphs must have the same directedness, otherwise the function returns with an error. Note that for undirected graphs the two relations are by definition symmetric.

Arguments:

`res`: | Pointer to an uninitialized graph object, the result will be stored here.
`g1`: | The first operand, a graph object.
`g2`: | The second operand, another graph object.
`edge_map1`: | If not a null pointer, then it must be a pointer to an initialized vector, and a mapping from the edges of the result graph to the edges of the first graph is stored here.
`edge_map2`: | If not a null pointer, then it must be a pointer to an initialized vector, and a mapping from the edges of the result graph to the edges of the second graph is stored here.

Returns:

`` | Error code.

Time complexity: O(|V|*d1*d2), |V| is the number of vertices in the first graph, d1 and d2 the average degree in the first and second graphs.

Example 15.6. File `examples/simple/igraph_compose.c`

    #include <igraph.h>

    int main(void) {

        igraph_t g1, g2, res;
        igraph_vector_int_t v;
        igraph_vector_int_t map1, map2;

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

        igraph_vector_int_init(&map1, 0);
        igraph_vector_int_init(&map2, 0);

        /* composition with the empty graph */
        igraph_empty(&g1, 5, IGRAPH_DIRECTED);
        igraph_full(&g2, 5, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
        igraph_compose(&res, &g1, &g2, &map1, &map2);
        if (igraph_ecount(&res) != 0) {
            return 1;
        }
        if (igraph_vector_int_size(&map1) != 0 || igraph_vector_int_size(&map2) != 0) {
            return 11;
        }
        igraph_destroy(&res);
        igraph_compose(&res, &g2, &g1, &map1, &map2);
        if (igraph_ecount(&res) != 0) {
            return 2;
        }
        if (igraph_vector_int_size(&map1) != 0 || igraph_vector_int_size(&map2) != 0) {
            return 12;
        }
        igraph_destroy(&res);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        /* same but undirected */
        igraph_empty(&g1, 5, IGRAPH_UNDIRECTED);
        igraph_full(&g2, 5, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
        igraph_compose(&res, &g1, &g2, &map1, &map2);
        if (igraph_ecount(&res) != 0) {
            return 1;
        }
        if (igraph_vector_int_size(&map1) != 0 || igraph_vector_int_size(&map2) != 0) {
            return 11;
        }
        igraph_destroy(&res);
        igraph_compose(&res, &g2, &g1, &map1, &map2);
        if (igraph_ecount(&res) != 0) {
            return 2;
        }
        if (igraph_vector_int_size(&map1) != 0 || igraph_vector_int_size(&map2) != 0) {
            return 12;
        }
        igraph_destroy(&res);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        /* proper directed graph */
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 5, 6, -1);
        igraph_create(&g1, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_vector_int_init_int_end(&v, -1, 0, 1, 2, 4, 5, 6, -1);
        igraph_create(&g2, &v, 0, IGRAPH_DIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_compose(&res, &g1, &g2, &map1, &map2);
        igraph_write_graph_edgelist(&res, stdout);
        igraph_vector_int_print(&map1);
        igraph_vector_int_print(&map2);
        igraph_destroy(&res);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        /* undirected graph */
        igraph_vector_int_init_int_end(&v, -1, 0, 1, 1, 2, 5, 6, -1);
        igraph_create(&g1, &v, 0, IGRAPH_UNDIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_vector_int_init_int_end(&v, -1, 0, 1, 0, 4, 5, 6, -1);
        igraph_create(&g2, &v, 0, IGRAPH_UNDIRECTED);
        igraph_vector_int_destroy(&v);

        igraph_compose(&res, &g1, &g2, &map1, &map2);
        igraph_write_graph_edgelist(&res, stdout);
        igraph_vector_int_print(&map1);
        igraph_vector_int_print(&map2);
        igraph_destroy(&res);
        igraph_destroy(&g1);
        igraph_destroy(&g2);

        igraph_vector_int_destroy(&map2);
        igraph_vector_int_destroy(&map1);

        return 0;
    }

## 3. Miscellaneous operators

### 3.1. `igraph_connect_neighborhood` — Connects each vertex to its neighborhood.

    igraph_error_t igraph_connect_neighborhood(igraph_t *graph, igraph_int_t order,
                                    igraph_neimode_t mode);

This function adds new edges to the input graph. Each vertex is connected to all vertices reachable by at most `order` steps from it (unless a connection already existed).

Note that the input graph is modified in place, no new graph is created. Call `igraph_copy()` if you want to keep the original graph as well.

For undirected graphs reachability is always symmetric: if vertex A can be reached from vertex B in at most `order` steps, then the opposite is also true. Only one undirected (A,B) edge will be added in this case.

Arguments:

`graph`: | The input graph. It will be modified in-place.
`order`: | Integer constant, it gives the distance within which the vertices will be connected to the source vertex.
`mode`: | Constant, it specifies how the neighborhood search is performed for directed graphs. If `IGRAPH_OUT` then vertices reachable from the source vertex will be connected, `IGRAPH_IN` is the opposite. If `IGRAPH_ALL` then the directed graph is considered as an undirected one.

Returns:

`` | Error code.

See also:

`` | `igraph_graph_power()` to compute the kth power of a graph; `igraph_square_lattice()` uses this function to connect the neighborhood of the vertices.

Time complexity: O(|V|*d^k), |V| is the number of vertices in the graph, d is the average degree and k is the `order` argument.

### 3.2. `igraph_contract_vertices` — Replace multiple vertices with a single one.

    igraph_error_t igraph_contract_vertices(igraph_t *graph,
                                 const igraph_vector_int_t *mapping,
                                 const igraph_attribute_combination_t *vertex_comb);

This function modifies the graph by merging several vertices into one. The vertices in the modified graph correspond to groups of vertices in the input graph. No edges are removed, thus the modified graph will typically have self-loops (corresponding to in-group edges) and multi-edges (corresponding to multiple connections between two groups). Use `igraph_simplify()` to eliminate self-loops and merge multi-edges.

Arguments:

`graph`: | The input graph. It will be modified in-place.
`mapping`: | A vector giving the mapping. For each vertex in the original graph, it should contain its desired ID in the result graph. In order not to create "orphan vertices" that have no corresponding vertices in the original graph, ensure that the IDs are consecutive integers starting from zero.
`vertex_comb`: | What to do with the vertex attributes. `NULL` means that vertex attributes are not kept after the contraction (not even for unaffected vertices). See the igraph manual section about attributes for details.

Returns:

`` | Error code.

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

Example 15.7. File `examples/simple/igraph_contract_vertices.c`

    #include <igraph.h>

    /* Create the condensation of a directed graph.
     * See https://en.wikipedia.org/wiki/Strongly_connected_component#Definitions
     * This example demonstrates how to write a basic igraph function, complete
     * with error handling. */
    igraph_error_t condensation(const igraph_t *graph, igraph_t *cond) {
        igraph_vector_int_t membership;

        /* Data structures such as vector must be initialized in igraph before use. */
        IGRAPH_CHECK(igraph_vector_int_init(&membership, 0));

        /* Adding the initialized vector to the "finally" stack ensures that it will
         * be automatically destroyed if an error occurs. */
        IGRAPH_FINALLY(igraph_vector_int_destroy, &membership);

        /* Functions that return an error code can be wrapped in IGRAPH_CHECK to pass that error
         * up to the caller. */
        IGRAPH_CHECK(igraph_connected_components(graph, &membership, /* csize */ NULL, /* no */ NULL, IGRAPH_STRONG));

        /* To compute the condensation, we simply contract strongly connected components.
         * Since igraph_contract_vertices() modifies graphs in-place, we make a copy first. */
        IGRAPH_CHECK(igraph_copy(cond, graph));

        /* Since we are not done creating the condensation yet, we add 'cond' to the
         * "finally" stack, so that it will be destroyed if an error occurs. */
        IGRAPH_FINALLY(igraph_destroy, cond);

        /* Contract strongly connected components. */
        IGRAPH_CHECK(igraph_contract_vertices(cond, &membership, NULL));

        /* igraph_contract_vertices() preserves all edges, some of which become
         * parallel edges or self-loops after the contraction. We simplify these. */
        IGRAPH_CHECK(igraph_simplify(cond, /* remove_multiple */ true, /* remove_loops */ true, NULL));

        /* Data structures that are no longer needed must be explicitly destroyed.
         * If they were added to the "finally" stack, they must be removed explicitly,
         * in the opposite order to how they were added. IGRAPH_FINALLY_CLEAN removes
         * the indicated number of entries from the "finally" stack. We remove
         * 'membership' because it was destroyed, and 'cond' because the responsibility
         * to destroy it is now with the caller. */
        igraph_vector_int_destroy(&membership);
        IGRAPH_FINALLY_CLEAN(2);

        return IGRAPH_SUCCESS; /* return with no error */
    }

    int main(void) {
        igraph_t graph, cond;

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

        /* Create a random directed graph with mean degree 2 and compute its condensation. */
        igraph_erdos_renyi_game_gnm(&graph, 100, 200, IGRAPH_DIRECTED, IGRAPH_SIMPLE_SW, IGRAPH_EDGE_UNLABELED);
        condensation(&graph, &cond);

        printf("Number of vertices in the condensation: %" IGRAPH_PRId "\n", igraph_vcount(&cond));
        igraph_write_graph_edgelist(&cond, stdout);

        /* Destroy data structures that are no longer needed. */
        igraph_destroy(&graph);
        igraph_destroy(&cond);

        return 0;
    }

### 3.3. `igraph_graph_power` — The k-th power of a graph.

    igraph_error_t igraph_graph_power(const igraph_t *graph, igraph_t *res,
                                      igraph_int_t order, igraph_bool_t directed);

The k-th power of a graph G is a simple graph where vertex `u` is connected to `v` by a single edge if `v` is reachable from `u` in G within at most k steps. By convention, the zeroth power of a graph has no edges. The first power is identical to the original graph, except that multiple edges and self-loops are removed.

Graph power is usually defined only for undirected graphs. igraph extends the concept to directed graphs. To ignore edge directions in the input, set the `directed` parameter to `false`. In this case, the result will be an undirected graph.

Graph and vertex attributes are preserved, but edge attributes are discarded.

Arguments:

`graph`: | The input graph.
`res`: | The graph power of the given `order`.
`order`: | Non-negative integer, the power to raise the graph to. In other words, vertices within a distance `order` will be connected.
`directed`: | Whether to take edge directions into account.

Returns:

`` | Error code.

See also:

`` | `igraph_connect_neighborhood()` to connect each vertex to its neighborhood, modifying a graph in-place.

Time complexity: O(|V|*d^k), |V| is the number of vertices in the graph, d is the average degree and k is the `order` argument.

### 3.4. `igraph_product` — The graph product of two graphs, according to the chosen product type.

    igraph_error_t igraph_product(igraph_t *res,
                                  const igraph_t *g1,
                                  const igraph_t *g2,
                                  igraph_product_t type);

### 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 function computes the product of two graphs using the graph product concept selected by the `type` parameter. The two graphs must be of the same type, either directed or undirected. If a product of an undirected and a directed graph is required, convert one of them to the appropriate type using `igraph_to_directed()` or `igraph_to_undirected()`.

Each vertex of the product graph corresponds to a pair `(u, v)`, where `u` is a vertex from the first graph and `v` is a vertex from the second graph. Thus the number of vertices in the product graph is `|V1| |V2|`, where `|V1|` and `|V2|` are the sizes of the vertex set of the operands. The pair `(u, v)` is mapped to a unique vertex index in the product graph using `index = u |V2| + v`.

All implemented graph products are associative, but not all are commutative.

The supported graph product types are detailed below. The notation `u ~ v` is used to indicate that vertices `u` and `v` are adjacent, i.e. there is a connection from `u` to `v`.

`IGRAPH_PRODUCT_CARTESIAN`

Computes the cartesian product of two graphs. In the product graph, there is a connection from `(u1, v1)` to `(u2, v2)` if and only if `u1 = u2` and `v1 ~ v2` or `u1 ~ u2` and `v1 = v2`. Thus, the number of edges in the product graph is `|V1| |E2| + |V2| |E1|`.

Time complexity: O(|V1| |V2| + |V1| |E2| + |V2| |E1|) where |V1| and |V2| are the number of vertices, and |E1| and |E2| are the number of edges of the operands.

`IGRAPH_PRODUCT_LEXICOGRAPHIC`

Computes the lexicographic product of two graphs. In the product graph, there is a connection from `(u1, v1)` to `(u2, v2)` if and only if `u1 = u2` and `v1 ~ v2` or `u1 ~ u2`. Thus, the number of edges in the product graph is `|V1| |E2| + |V2|^2 |E1|`. Unlike most other graph products, the lexicographic product is not commutative.

Time complexity: O(|V1| |V2| + |V1| |E2| + |V2|^2 |E1|) where |V1| and |V2| are the number of vertices, and |E1| and |E2| are the number of edges of the operands.

`IGRAPH_PRODUCT_STRONG`

Computes the strong product (also known as normal product) of two graphs. In the product graph, there is a connection from `(u1, v1)` to `(u2, v2)` if and only if `u1 = u2` and `v1 ~ v2` or `u1 ~ u2` and `v1 = v2` or `u1 ~ u2` and `v1 ~ v2`. Thus, the number of edges in the product graph is `|V1| |E2| + |V2| |E1| + |E1| |E2|` in the directed case and `|V1| |E2| + |V2| |E1| + 2 |E1| |E2|` in the undirected case.

Time complexity: O(|V1| |V2| + |V1| |E2| + |V2| |E1| + |E1| |E2|) where |V1| and |V2| are the number of vertices, and |E1| and |E2| are the number of edges of the operands.

`IGRAPH_PRODUCT_TENSOR`

Computes the tensor product (also known as categorial product) of two graphs. In the product graph, there is a connection from `(u1, v1)` to `(u2, v2)` if and only if `u1 ~ u2` and `v1 ~ v2`. Thus, the number of edges in the product is `|E1| |E2|` in the directed case and `2 |E1| |E2|` in the undirected case.

Time complexity: O(|V1| |V2| + |E1| |E2|) where |V1| and |V2| are the number of vertices, and |E1| and |E2| are the number of edges of the operands.

`IGRAPH_PRODUCT_MODULAR`

Computes the modular product of two graphs. In the product graph, there is a connection from `(u1, v1)` to `(u2, v2)` if and only if `u1 ~ u2` and `v1 ~ v2` or `NOT (u1 ~ u2)` and `NOT (v1 ~ v2)`. The modular product requires both graphs to be simple. Thus, the number of edges in the product is `|E1| |E2| + |E1'| |E2'|` in the directed case and `2 |E1| |E2| + 2 |E1'| |E2'|` in the undirected case.

Time complexity: O(|V1| |V2| + |E1| |E2| + |E1'| |E2'|) where |V1| and |V2| are the number of vertices, |E1| and |E2| are the number of edges of the operands, and |E1'| and |E2'| are the number of edges of their complement.

Reference:

Richard Hammack, Wilfried Imrich, and Sandi Klavžar (2011). Handbook of Product Graphs (2nd ed.). CRC Press. https://doi.org/10.1201/b10959

Arguments:

`res`: | Pointer to an uninitialized graph object. The product graph will be stored here.
`g1`: | The first operand graph.
`g2`: | The second operand graph. It must have the same directedness as `g1`.
`type`: | The type of graph product to compute.

Returns:

`` | Error code: `IGRAPH_EINVAL` if the specified `type` is unsupported or the input graphs `g1` and `g2` are incompatible for the requested product.

See also:

`` | `igraph_rooted_product()` for the rooted product.

### 3.5. `igraph_rooted_product` — The rooted graph product of two graphs.

    igraph_error_t igraph_rooted_product(igraph_t *res,
                                         const igraph_t *g1,
                                         const igraph_t *g2,
                                         igraph_int_t root);

### 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 function computes the rooted product of two graphs. The two graphs must be of the same type, either directed or undirected. If a product of an undirected and a directed graph is required, convert one of them to the appropriate type using `igraph_to_directed()` or `igraph_to_undirected()`.

The vertex IDs in the product graph related to the IDs in the operands in the same convention as in `igraph_product()`.

In the rooted product graph of G and H, with root vertex ID `root` in H, there is a connection from `(u1, v1)` to `(u2, v2)` if and only if `u1 = u2` and `v1 ~ v2` or `u1 ~ u2` and `v1 = v2 = root`. Thus, the number of edges in the product graph is `|V1| |E2| + |E1|`.

Arguments:

`res`: | Pointer to an uninitialized graph object. The product graph will be stored here.
`g1`: | The first operand graph.
`g2`: | The second operand graph. It must have the same directedness as `g1`.
`root`: | The root vertex id of the second graph.

Returns:

`` | Error code: `IGRAPH_EINVAL` if the specified `type` is unsupported or the input graphs `g1` and `g2` are incompatible for the requested product. `IGRAPH_EINVVID` if invalid vertex ID passed as `root`.

See also:

`` | `igraph_product()` for other types of graph products.

Time complexity: O(|V1| |V2| + |V1| |E2| + |E1|) where |V1| and |V2| are the number of vertices, and |E1| and |E2| are the number of edges of the operands.

### 3.6. `igraph_induced_subgraph` — Creates a subgraph induced by the specified vertices.

    igraph_error_t igraph_induced_subgraph(const igraph_t *graph, igraph_t *res,
                                           const igraph_vs_t vids,
                                           igraph_subgraph_implementation_t impl);

This function collects the specified vertices and all edges between them to a new graph. As vertex IDs are always contiguos integers starting at zero, the IDs in the created subgraph will be different from the IDs in the original graph. To get the mappings between them, use `igraph_induced_subgraph_map()`

Arguments:

`graph`: | The graph object.
`res`: | The subgraph, another graph object will be stored here, do not initialize this object before calling this function, and call `igraph_destroy()` on it if you don't need it any more.

`vids`:

A vertex selector describing which vertices to keep. A vertex may appear more than once in the selector, but it will be considered only once (i.e. it is not possible to duplicate a vertex by adding its ID more than once to the selector). The order in which the vertices appear in the vertex selector is ignored; the returned subgraph will always contain the vertices of the original graph in increasing order of vertex IDs.

`impl`:

This parameter selects which implementation should we use when constructing the new graph. Basically there are two possibilities: `IGRAPH_SUBGRAPH_COPY_AND_DELETE` copies the existing graph and deletes the vertices that are not needed in the new graph, while `IGRAPH_SUBGRAPH_CREATE_FROM_SCRATCH` constructs the new graph from scratch without copying the old one. The latter is more efficient if you are extracting a relatively small subpart of a very large graph, while the former is better if you want to extract a subgraph whose size is comparable to the size of the whole graph. There is a third possibility: `IGRAPH_SUBGRAPH_AUTO` will select one of the two methods automatically based on the ratio of the number of vertices in the new and the old graph.

Returns:

`` | Error code: `IGRAPH_ENOMEM`, not enough memory for temporary data. `IGRAPH_EINVVID`, invalid vertex ID in `vids`.

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

See also:

`` | `igraph_induced_subgraph_map()` to also retrieve the vertex ID mapping between the graph and the extracted subgraph; `igraph_delete_vertices()` to delete the specified set of vertices from a graph, the opposite of this function.

### 3.7. `igraph_induced_subgraph_map` — Creates an induced subraph and returns the mapping from the original.

    igraph_error_t igraph_induced_subgraph_map(const igraph_t *graph, igraph_t *res,
                                               const igraph_vs_t vids,
                                               igraph_subgraph_implementation_t impl,
                                               igraph_vector_int_t *map,
                                               igraph_vector_int_t *invmap);

This function collects the specified vertices and all edges between them to a new graph. As vertex IDs are always contiguos integers starting at zero, the IDs in the created subgraph will be different from the IDs in the original graph. The mapping between the vertex IDs in the graph and the extracted subgraphs are returned in `map` and `invmap`.

Arguments:

`graph`: | The graph object.
`res`: | The subgraph, another graph object will be stored here, do not initialize this object before calling this function, and call `igraph_destroy()` on it if you don't need it any more.
`vids`: | A vertex selector describing which vertices to keep.

`impl`:

This parameter selects which implementation should be used when constructing the new graph. Basically there are two possibilities: `IGRAPH_SUBGRAPH_COPY_AND_DELETE` copies the existing graph and deletes the vertices that are not needed in the new graph, while `IGRAPH_SUBGRAPH_CREATE_FROM_SCRATCH` constructs the new graph from scratch without copying the old one. The latter is more efficient if you are extracting a relatively small subpart of a very large graph, while the former is better if you want to extract a subgraph whose size is comparable to the size of the whole graph. There is a third possibility: `IGRAPH_SUBGRAPH_AUTO` will select one of the two methods automatically based on the ratio of the number of vertices in the new and the old graph.

`map`: | Returns a map of the vertices in `graph` to the vertices in `res`. -1 indicates a vertex is not mapped. A value of `i` at position `j` indicates the vertex `j` in `graph` is mapped to vertex i in `res`.
`invmap`: | Returns a map of the vertices in `res` to the vertices in `graph`. A value of `i` at position `j` indicates that vertex `i` in `graph` is mapped to vertex `j` in `res`.

Returns:

`` | Error code: `IGRAPH_ENOMEM`, not enough memory for temporary data. `IGRAPH_EINVVID`, invalid vertex ID in `vids`.

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

See also:

`` | `igraph_delete_vertices()` to delete the specified set of vertices from a graph, the opposite of this function.

### 3.8. `igraph_induced_subgraph_edges` — The edges contained within an induced sugraph.

    igraph_error_t igraph_induced_subgraph_edges(const igraph_t *graph, igraph_vs_t vids, igraph_vector_int_t *edges);

This function finds the IDs of those edges which connect vertices from a given list, passed in the `vids` parameter.

Arguments:

`graph`: | The graph.
`vids`: | A vertex selector specifying the vertices that make up the subgraph.
`edges`: | Integer vector. The IDs of edges within the subgraph induces by `vids` will be stored here.

Returns:

`` | Error code.

Time complexity: O(mv log(nv)) where nv is the number of vertices in `vids` and mv is the sum of degrees of vertices in `vids`.

### 3.9. `igraph_linegraph` — Create the line graph of a graph.

    igraph_error_t igraph_linegraph(const igraph_t *graph, igraph_t *linegraph);

The line graph L(G) of a G undirected graph is defined as follows. L(G) has one vertex for each edge in G and two different vertices in L(G) are connected by an edge if their corresponding edges share an end point. In a multigraph, if two end points are shared, two edges are created. The single vertex of an undirected self-loop is counted as two end points.

The line graph L(G) of a G directed graph is slightly different: L(G) has one vertex for each edge in G and two vertices in L(G) are connected by a directed edge if the target of the first vertex's corresponding edge is the same as the source of the second vertex's corresponding edge.

Self-loops are considered self-adjacent, thus their corresponding vertex in the line graph will also a have a single self-loop, in both undirected and directed graphs.

Edge i in the original graph will correspond to vertex i in the line graph.

The first version of this function was contributed by Vincent Matossian, thanks.

Arguments:

`graph`: | The input graph, may be directed or undirected.
`linegraph`: | Pointer to an uninitialized graph object, the result is stored here.

Returns:

`` | Error code.

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

### 3.10. `igraph_mycielskian` — Generate the Mycielskian of a graph with `k` iterations.

    igraph_error_t igraph_mycielskian(const igraph_t *graph, igraph_t *res, igraph_int_t k);

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

The Mycielskian of a graph is a larger graph formed using a construction due to Jan Mycielski that increases the chromatic number by one while preserving the triangle-free property. The Mycielski construction can be used to create triangle-free graphs with an arbitrarily large chromatic number.

Let the `n` vertices of the given graph `G` be `v_1`, ..., `v_n`. The Mycielskian of `G`, denoted `M(G)`, contains `G` itself as a subgraph, together with `n`+1 additional vertices:

- A vertex `u_i` corresponding to each vertex `v_i` of `G`.

- An extra vertex `w`.

The edges are added as follows:

- Each vertex `u_i` is connected to `w`, forming a star.

- For each edge `(v_i, v_j)` in `G`, two new edges are added: `(u_i, v_j)` and `(v_i, u_j)`.

Thus, if `G` has `n` vertices and `m` edges, the Mycielskian `M(G)` has `2n + 1` vertices, and `3m + n` edges.

igraph uses an alternative construction in two special cases:

- The Mycielskian of the null graph is the singleton graph.

- The Mycielskian of the singleton graph is the two-path.

This ensures that iterative applications of the construction, starting from the null or singleton graph, always yields connected graphs. In fact these are the Mycielski graphs that `igraph_mycielski_graph()` produces.

igraph extends the construction to directed graphs, as well as to non-simple graphs, by following the above constructions rules literally.

This function can apply the Mycielski transformation an arbitrary number of times, controlled by the parameter `k`. The k-th iterated Mycielskian has `n_k = (n + 1) * 2^k - 1` vertices and `m_k = ((2m + 2n + 1) * 3^k - n_{k+1}) / 2` edges, where `n` and `m` are the vertex and edge count of the original graph, respectively.

Arguments:

`graph`: | Pointer to the input graph.
`res`: | Pointer to an uninitialized graph object where the Mycielskian of the input graph will be stored.
`k`: | Integer, the number of Mycielskian iterations (must be non-negative).

Returns:

`` | Error code.

See also:

`` | `igraph_mycielski_graph()`.

Time complexity: O(|V| 2^k + |E| 3^k) where |V| and |E| are the vertex and edge counts, respectively.

### 3.11. `igraph_simplify` — Removes loop and/or multiple edges from the graph.

    igraph_error_t igraph_simplify(igraph_t *graph,
                                   igraph_bool_t remove_multiple, igraph_bool_t remove_loops,
                                   const igraph_attribute_combination_t *edge_comb);

This function merges parallel edges and removes self-loops, according to the `multiple` and `loops` parameters. Note that this function may change the edge order, even if the input was already a simple graph.

Arguments:

`graph`: | The graph object.
`remove_multiple`: | If true, multiple edges will be removed.
`remove_loops`: | If true, loops (self edges) will be removed.
`edge_comb`: | What to do with the edge attributes. `NULL` means to discard the edge attributes after the operation, even for edges that were unaffected. See the igraph manual section about attributes for details.

Returns:

`` | Error code: `IGRAPH_ENOMEM` if we are out of memory.

Time complexity: O(|V|+|E|).

Example 15.8. File `examples/simple/igraph_simplify.c`

    #include <igraph.h>

    int main(void) {

        igraph_t g;

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

        /* Multiple edges */

        igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, -1);
        igraph_simplify(&g, true, true, /*edge_comb=*/ NULL);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_destroy(&g);

        igraph_small(&g, 0, IGRAPH_UNDIRECTED, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, -1);
        igraph_simplify(&g, true, true, /*edge_comb=*/ NULL);
        if (igraph_ecount(&g) != 1) {
            return 1;
        }
        igraph_destroy(&g);

        /* Loop edges*/

        igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 0, 1, 1, 2, 2, 1, 2, -1);
        igraph_simplify(&g, true, true, /*edge_comb=*/ NULL);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_destroy(&g);

        igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 0, 1, 1, 2, 2, 1, 2, -1);
        igraph_simplify(&g, true, true, /*edge_comb=*/ NULL);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_destroy(&g);

        /* Loop & multiple edges */

        igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, -1);
        igraph_simplify(&g, /* remove_multiple */ true, /* remove_loops */ false, /*edge_comb=*/ NULL);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_destroy(&g);

        igraph_small(&g, 0, IGRAPH_UNDIRECTED, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, -1);
        igraph_simplify(&g, /* remove_multiple */ true, /* remove_loops */ false, /*edge_comb=*/ NULL);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_destroy(&g);

        igraph_small(&g, 0, IGRAPH_DIRECTED, 2, 2, 2, 2, 2, 2, 3, 2, -1);
        igraph_simplify(&g, /* remove_multiple */ false, /* remove_loops */ true, /*edge_comb=*/ NULL);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_destroy(&g);

        igraph_small(&g, 0, IGRAPH_UNDIRECTED, 3, 3, 3, 3, 3, 4, -1);
        igraph_simplify(&g, /* remove_multiple */ false, /* remove_loops */ true, /*edge_comb=*/ NULL);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_destroy(&g);

        igraph_small(&g, 0, IGRAPH_DIRECTED, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, -1);
        igraph_simplify(&g, true, true, /*edge_comb=*/ NULL);
        igraph_write_graph_edgelist(&g, stdout);
        igraph_destroy(&g);

        igraph_small(&g, 0, IGRAPH_UNDIRECTED,
                     2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 2, 3, 2, -1);
        igraph_simplify(&g, true, true, /*edge_comb=*/ NULL);
        if (igraph_ecount(&g) != 1) {
            return 2;
        }
        igraph_destroy(&g);

        return 0;
    }

### 3.12. `igraph_subgraph_from_edges` — Creates a subgraph with the specified edges and their endpoints.

    igraph_error_t igraph_subgraph_from_edges(
        const igraph_t *graph, igraph_t *res, const igraph_es_t eids,
        igraph_bool_t delete_vertices
    );

This function collects the specified edges and their endpoints to a new graph. As the edge IDs in a graph are always contiguous integers starting at zero, the edge IDs in the extracted subgraph will be different from those in the original graph. Vertex IDs will also be reassigned if `delete_vertices` is set to `true`. Attributes are preserved.

Arguments:

`graph`: | The graph object.
`res`: | The subgraph, another graph object will be stored here, do not initialize this object before calling this function, and call `igraph_destroy()` on it if you don't need it any more.
`eids`: | An edge selector describing which edges to keep.
`delete_vertices`: | Whether to delete the vertices not incident on any of the specified edges as well. If `false`, the number of vertices in the result graph will always be equal to the number of vertices in the input graph.

Returns:

`` | Error code: `IGRAPH_ENOMEM`, not enough memory for temporary data. `IGRAPH_EINVEID`, invalid edge ID in `eids`.

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

See also:

`` | `igraph_delete_edges()` to delete the specified set of edges from a graph, the opposite of this function.

### 3.13. `igraph_reverse_edges` — Reverses some edges of a directed graph.

    igraph_error_t igraph_reverse_edges(igraph_t *graph, const igraph_es_t eids);

This function reverses some edges of a directed graph. The modification is done in place. All attributes, as well as the ordering of edges and vertices are preserved.

Note that is rarely necessary to reverse all edges, as almost all functions that handle directed graphs take a `mode` argument that can be set to `IGRAPH_IN` to effectively treat edges as reversed.

Arguments:

`graph`: | The graph whose edges will be reversed.
`eids`: | The edges to be reversed. Pass `igraph_ess_all(IGRAPH_EDGEORDER_ID)` to reverse all edges.

Returns:

`` | Error code.

Time complexity: O(1) if all edges are reversed, otherwise O(|E|) where |E| is the number of edges in the graph.