igraph_error_t igraph_create(igraph_t *graph, const igraph_vector_int_t *edges,
                  igraph_integer_t n, igraph_bool_t directed);

Arguments: 

Returns: 

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

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_t v1, v2;

    /* simple use */
    igraph_vector_int_init(&v1, 8);
    VECTOR(v1)[0] = 0;
    VECTOR(v1)[1] = 1;
    VECTOR(v1)[2] = 1;
    VECTOR(v1)[3] = 2;
    VECTOR(v1)[4] = 2;
    VECTOR(v1)[5] = 3;
    VECTOR(v1)[6] = 2;
    VECTOR(v1)[7] = 2;
    igraph_create(&g, &v1, 0, 0);
    if (igraph_vcount(&g) != 4) {
        return 1;
    }
    igraph_vector_int_init(&v2, 0);
    igraph_get_edgelist(&g, &v2, 0);
    igraph_vector_int_sort(&v1);
    igraph_vector_int_sort(&v2);
    if (!igraph_vector_int_all_e(&v1, &v2)) {
        return 2;
    }
    igraph_destroy(&g);

    /* higher number of vertices */
    igraph_create(&g, &v1, 10, 0);
    if (igraph_vcount(&g) != 10) {
        return 1;
    }
    igraph_get_edgelist(&g, &v2, 0);
    igraph_vector_int_sort(&v1);
    igraph_vector_int_sort(&v2);
    if (!igraph_vector_int_all_e(&v1, &v2)) {
        return 3;
    }
    igraph_destroy(&g);
    igraph_vector_int_destroy(&v1);
    igraph_vector_int_destroy(&v2);

    return 0;
}

igraph_error_t igraph_small(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,
                            int first, ...);

This function is handy when a relatively small graph needs to be created. Instead of giving the edges as a vector, they are given simply as arguments and a -1 needs to be given after the last meaningful edge argument.

This function is intended to be used with vertex IDs that are entered as literal integers. If you use a variable instead of a literal, make sure that it is of type int, as this is the type that this function assumes for all variadic arguments. Using a different integer type is undefined behaviour and likely to cause platform-specific issues.

Arguments: 

Returns: 

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

#include <igraph.h>

int main(void) {

    igraph_t g;

    igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 3, 4, 6, 1, -1);
    igraph_write_graph_edgelist(&g, stdout);
    igraph_destroy(&g);

    return 0;
}

igraph_error_t igraph_adjacency(
    igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode,
    igraph_loops_t loops
);

The order of the vertices in the matrix is preserved, i.e. the vertex corresponding to the first row/column will be vertex with id 0, the next row is for vertex 1, etc. No guarantees are given about the ordering of edges.

Arguments: 

Returns: 

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

#include <igraph.h>

int main(void) {

    return 0;
}

igraph_error_t igraph_weighted_adjacency(
    igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode,
    igraph_vector_t *weights, igraph_loops_t loops
);

The order of the vertices in the matrix is preserved, i.e. the vertex corresponding to the first row/column will be vertex with id 0, the next row is for vertex 1, etc. No guarantees are given for the ordering of edges.

Arguments: 

Returns: 

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

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_real_t data[4][4] = { {   0, 1.2, 2.3,   0 },
                                 { 2.0,   0,   0, 1.0 },
                                 {   0,   0, 1.5,   0 },
                                 {   0, 1.0,   0,   0 } };
    igraph_matrix_t mat;
    igraph_vector_t weights;
    igraph_vector_int_t edges;
    igraph_integer_t n;

    /* C arryas use row-major storage, while igraph's matrix uses column-major.
     * The matrix 'mat' will be the transpose of 'data'. */
    igraph_matrix_view(&mat, *data, sizeof(data[0]) / sizeof(data[0][0]), sizeof(data) / sizeof(data[0]));

    /* Initialize vector into which weights will be written. */
    igraph_vector_init(&weights, 0);

    igraph_weighted_adjacency(&graph, &mat, IGRAPH_ADJ_DIRECTED, &weights, IGRAPH_LOOPS_ONCE);

    /* When igraph_weighted_adjacency() returns, 'weights' will typically have
     * more capacity allocated than what it uses. We may optionally free any
     * unused capacity to save memory, although in most applications this
     * is not necessary. */
    igraph_vector_resize_min(&weights);

    /* Get the edge list of the graph and output it, along with the weights. */

    igraph_vector_int_init(&edges, 0);
    igraph_get_edgelist(&graph, &edges, 0);
    n = igraph_ecount(&graph);

    for (igraph_integer_t i = 0; i < n; i++) {
        printf("%" IGRAPH_PRId " --> %" IGRAPH_PRId ": %g\n",
               VECTOR(edges)[2*i], VECTOR(edges)[2*i + 1], VECTOR(weights)[i]);
    }

    /* Free all allocated storage. */
    igraph_vector_int_destroy(&edges);
    igraph_destroy(&graph);
    igraph_vector_destroy(&weights);

    return 0;
}

igraph_error_t igraph_sparse_adjacency(igraph_t *graph, igraph_sparsemat_t *adjmatrix,
        igraph_adjacency_t mode, igraph_loops_t loops);

This has the same functionality as igraph_adjacency(), but uses a column-compressed adjacency matrix. Time complexity: O(|E|), where |E| is the number of edges in the graph.

igraph_error_t igraph_sparse_weighted_adjacency(
    igraph_t *graph, igraph_sparsemat_t *adjmatrix, igraph_adjacency_t mode,
    igraph_vector_t *weights, igraph_loops_t loops
);

This has the same functionality as igraph_weighted_adjacency(), but uses a column-compressed adjacency matrix. Time complexity: O(|E|), where |E| is the number of edges in the graph.

igraph_error_t igraph_adjlist(igraph_t *graph, const igraph_adjlist_t *adjlist,
                   igraph_neimode_t mode, igraph_bool_t duplicate);

An adjacency list is a list of vectors, containing the neighbors of all vertices. For operations that involve many changes to the graph structure, it is recommended that you convert the graph into an adjacency list via igraph_adjlist_init(), perform the modifications (these are cheap for an adjacency list) and then recreate the igraph graph via this function.

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_star(igraph_t *graph, igraph_integer_t n, igraph_star_mode_t mode,
                igraph_integer_t center);

Arguments: 

Returns: 

Time complexity: O(|V|), the number of vertices in the graph.

See also: 

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

int main(void) {
    igraph_t graph;

    /* Create an undirected 6-star, with the 0th node as the centre. */
    igraph_star(&graph, 7, IGRAPH_STAR_UNDIRECTED, 0);

    /* Output the edge list of the graph. */
    igraph_write_graph_edgelist(&graph, stdout);

    /* Destroy the graph when we are done using it. */
    igraph_destroy(&graph);

    return 0;
}

igraph_error_t igraph_wheel(igraph_t *graph, igraph_integer_t n, igraph_wheel_mode_t mode,
                igraph_integer_t center);

A wheel graph on n vertices can be thought of as a wheel with n - 1 spokes. The cycle graph part makes up the rim, while the star graph part adds the spokes.

Note that the two and three-vertex wheel graphs are non-simple: The two-vertex wheel graph contains a self-loop, while the three-vertex wheel graph contains parallel edges (a 1-cycle and a 2-cycle, respectively).

Arguments: 

Returns: 

Time complexity: O(|V|), the number of vertices in the graph.

See also: 

igraph_error_t igraph_hypercube(igraph_t *graph,
                                igraph_integer_t n, igraph_bool_t directed);

The hypercube graph Q_n has 2^n vertices and 2^(n-1) n edges. Two vertices are connected when the binary representations of their zero-based vertex IDs differs in precisely one bit.

Arguments: 

Returns: 

See also: 

Time complexity: O(2^n)

igraph_error_t igraph_square_lattice(
    igraph_t *graph, const igraph_vector_int_t *dimvector, igraph_integer_t nei,
    igraph_bool_t directed, igraph_bool_t mutual, const igraph_vector_bool_t *periodic
);

Creates d-dimensional square lattices of the given size. Optionally, the lattice can be made periodic, and the neighbors within a given graph distance can be connected.

In the zero-dimensional case, the singleton graph is returned.

The vertices of the resulting graph are ordered such that the index of the vertex at position (i_1, i_2, i_3, ..., i_d) in a lattice of size (n_1, n_2, ..., n_d) will be i_1 + n_1 * i_2 + n_1 * n_2 * i_3 + ....

Arguments: 

Returns: 

See also: 

Time complexity: If nei is less than two then it is O(|V|+|E|) (as far as I remember), |V| and |E| are the number of vertices and edges in the generated graph. Otherwise it is O(|V|*d^k+|E|), d is the average degree of the graph, k is the nei argument.

igraph_error_t igraph_triangular_lattice(
        igraph_t *graph, const igraph_vector_int_t *dims,
        igraph_bool_t directed, igraph_bool_t mutual);

Creates a triangular lattice whose vertices have the form (i, j) for non-negative integers i and j and (i, j) is generally connected with (i + 1, j), (i, j + 1), and (i - 1, j + 1). The function constructs a planar dual of the graph constructed by igraph_hexagonal_lattice(). In particular, there a one-to-one correspondence between the vertices in the constructed graph and the cycles of length 6 in the graph constructed by igraph_hexagonal_lattice() with the same dims parameter.

The vertices of the resulting graph are ordered lexicographically with the 2nd coordinate being more significant, e.g., (i, j) < (i + 1, j) and (i + 1, j) < (i, j + 1)

Arguments: 

Returns: 

See also: 

Time complexity: O(|V|), where |V| is the number of vertices in the generated graph.

igraph_error_t igraph_hexagonal_lattice(
        igraph_t *graph, const igraph_vector_int_t *dims,
        igraph_bool_t directed, igraph_bool_t mutual);

Creates a hexagonal lattice whose vertices have the form (i, j) for non-negative integers i and j and (i, j) is generally connected with (i + 1, j), and if i is odd also with (i - 1, j + 1). The function constructs a planar dual of the graph constructed by igraph_triangular_lattice(). In particular, there a one-to-one correspondence between the cycles of length 6 in the constructed graph and the vertices of the graph constructed by igraph_triangular_lattice() function with the same dims parameter.

The vertices of the resulting graph are ordered lexicographically with the 2nd coordinate being more significant, e.g., (i, j) < (i + 1, j) and (i + 1, j) < (i, j + 1)

Arguments: 

Returns: 

See also: 

Time complexity: O(|V|), where |V| is the number of vertices in the generated graph.

igraph_error_t igraph_ring(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,
                igraph_bool_t mutual, igraph_bool_t circular);

A circular ring on n vertices is commonly known in graph theory as the cycle graph, and often denoted by C_n. Removing a single edge from the cycle graph C_n results in the path graph P_n. This function can generate both.

When n is 1 or 2, the result may not be a simple graph: the one-cycle contains a self-loop and the undirected or reciprocally connected directed two-cycle contains parallel edges.

Arguments: 

Returns: 

Time complexity: O(|V|), the number of vertices in the graph.

See also: 

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

int main(void) {
    igraph_t graph;

    /* Create a directed path graph on 10 vertices. */
    igraph_ring(&graph, 10, IGRAPH_DIRECTED, /* mutual= */ 0, /* circular= */ 0);

    /* Output the edge list of the graph. */
    printf("10-path graph:\n");
    igraph_write_graph_edgelist(&graph, stdout);

    /* Destroy the graph. */
    igraph_destroy(&graph);

    /* Create a 4-cycle graph. */
    igraph_ring(&graph, 4, IGRAPH_UNDIRECTED, /* mutual= */ 0, /* circular= */ 1);

    /* Output the edge list of the graph. */
    printf("\n4-cycle graph:\n");
    igraph_write_graph_edgelist(&graph, stdout);

    /* Destroy the graph. */
    igraph_destroy(&graph);

    return 0;
}

igraph_error_t igraph_kary_tree(igraph_t *graph, igraph_integer_t n, igraph_integer_t children,
                igraph_tree_mode_t type);

To obtain a completely symmetric tree with l layers, where each vertex has precisely children descendants, use n = (children^(l+1) - 1) / (children - 1). Such trees are often called k-ary trees, where k refers to the number of children.

Note that for n=0, the null graph is returned, which is not considered to be a tree by igraph_is_tree().

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_bool_t res;

    /* Create a directed binary tree on 15 nodes,
       with edges pointing towards the root. */
    igraph_kary_tree(&graph, 15, 2, IGRAPH_TREE_IN);

    igraph_is_tree(&graph, &res, NULL, IGRAPH_IN);
    printf("Is it an in-tree? %s\n", res ? "Yes" : "No");

    igraph_is_tree(&graph, &res, NULL, IGRAPH_OUT);
    printf("Is it an out-tree? %s\n", res ? "Yes" : "No");

    igraph_destroy(&graph);

    return 0;
}

igraph_error_t igraph_symmetric_tree(igraph_t *graph, const igraph_vector_int_t *branches,
                igraph_tree_mode_t type);

This function creates a tree in which all vertices at distance d from the root have branching_counts[d] children.

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>

int main(void) {

    igraph_t graph;
    igraph_bool_t res;
    igraph_vector_int_t v;
    igraph_vector_int_init_int(&v, 3, 3, 4, 5);

    /* Create a directed symmetric tree with 2 levels -
       3 children in first and 4 children in second level,
       5 children in third level
       with edges pointing towards the root. */
    igraph_symmetric_tree(&graph, &v, IGRAPH_TREE_IN);

    igraph_is_tree(&graph, &res, NULL, IGRAPH_IN);
    printf("Is it an in-tree? %s\n", res ? "Yes" : "No");

    igraph_is_tree(&graph, &res, NULL, IGRAPH_OUT);
    printf("Is it an out-tree? %s\n", res ? "Yes" : "No");

    igraph_destroy(&graph);
    igraph_vector_int_destroy(&v);

    return 0;
}

igraph_error_t igraph_regular_tree(igraph_t *graph, igraph_integer_t h, igraph_integer_t k, igraph_tree_mode_t type);

All vertices of a regular tree, except its leaves, have the same total degree k. This is different from a k-ary tree (igraph_kary_tree()), where all vertices have the same number of children, thus the degre of the root is one less than the degree of the other internal vertices. Regular trees are also referred to as Bethe lattices.

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>

int main(void) {
    igraph_t tree;
    igraph_vector_t eccentricity;
    igraph_bool_t is_tree;

    /* Create a Bethe lattice with 5 levels, i.e. height 4. */
    igraph_regular_tree(&tree, 4, 3, IGRAPH_TREE_UNDIRECTED);

    /* Bethe lattices are trees. */
    igraph_is_tree(&tree, &is_tree, NULL, IGRAPH_ALL);
    printf("Is it a tree? %s\n", is_tree ? "Yes." : "No.");

    /* Compute and print eccentricities. The root is the most central. */
    igraph_vector_init(&eccentricity, 0);
    igraph_eccentricity(&tree, &eccentricity, igraph_vss_all(), IGRAPH_ALL);
    printf("Vertex eccentricities:\n");
    igraph_vector_print(&eccentricity);
    igraph_vector_destroy(&eccentricity);

    /* Clean up. */
    igraph_destroy(&tree);

    return 0;
}

igraph_error_t igraph_tree_from_parent_vector(
        igraph_t *graph,
        const igraph_vector_int_t *parents,
        igraph_tree_mode_t type);

Rooted trees and forests are conveniently represented using a parents vector where the ID of the parent of vertex v is stored in parents[v]. This function serves to construct an igraph graph from a parent vector representation. The result is guaranteed to be a forest or a tree. If the parents vector is found to encode a cycle or a self-loop, an error is raised.

Several igraph functions produce such vectors, such as graph traversal functions (igraph_bfs() and igraph_dfs()), shortest path functions that construct a shortest path tree, as well as some other specialized functions like igraph_dominator_tree() or igraph_cohesive_blocks(). Vertices which do not have parents (i.e. roots) get a negative entry in the parents vector.

Use igraph_bfs() or igraph_dfs() to convert a forest into a parent vector representation. For trees, i.e. forests with a single root, it is more convenient to use igraph_bfs_simple().

Arguments: 

Returns: 

See also: 

Time complexity: O(n) where n is the length of parents.

igraph_error_t igraph_full(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,
                igraph_bool_t loops);

In a full graph every possible edge is present: every vertex is connected to every other vertex. igraph generalizes the usual concept of complete graphs in graph theory to graphs with self-loops as well as to directed graphs.

Arguments: 

Returns: 

Time complexity: O(|V|^2) = O(|E|), where |V| is the number of vertices and |E| is the number of edges.

See also: 

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

int main(void) {
    igraph_t graph;
    igraph_integer_t n_vertices = 10;

    /* Create an undirected complete graph. */
    /* Use IGRAPH_UNDIRECTED and IGRAPH_NO_LOOPS instead of true and false for better readability. */
    igraph_full(&graph, n_vertices, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
    printf("The undirected complete graph on %" IGRAPH_PRId " vertices has %" IGRAPH_PRId " edges.\n",
          igraph_vcount(&graph), igraph_ecount(&graph));

    /* Remember to destroy the object at the end. */
    igraph_destroy(&graph);

    /* Create a directed complete graph. */
    igraph_full(&graph, n_vertices, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
    printf("The directed complete graph on %" IGRAPH_PRId " vertices has %" IGRAPH_PRId " edges.\n",
          igraph_vcount(&graph), igraph_ecount(&graph));

    igraph_destroy(&graph);

    /* Create an undirected complete graph with self-loops. */
    igraph_full(&graph, n_vertices, IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
    printf("The undirected complete graph on %" IGRAPH_PRId " vertices with self-loops has %" IGRAPH_PRId " edges.\n",
          igraph_vcount(&graph), igraph_ecount(&graph));

    igraph_destroy(&graph);

    /* Create a directed graph with self-loops. */
    igraph_full(&graph, n_vertices, IGRAPH_DIRECTED, IGRAPH_LOOPS);
    printf("The directed complete graph on %" IGRAPH_PRId " vertices with self-loops has %" IGRAPH_PRId " edges.\n",
          igraph_vcount(&graph), igraph_ecount(&graph));

    igraph_destroy(&graph);

    return 0;

}

igraph_error_t igraph_full_citation(igraph_t *graph, igraph_integer_t n,
                         igraph_bool_t directed);

This is a directed graph, where every i->j edge is present if and only if j<i. If the directed argument is false then an undirected graph is created, and it is just a complete graph.

Arguments: 

Returns: 

See also: 

Time complexity: O(|V|^2) = O(|E|), where |V| is the number of vertices and |E| is the number of edges.

igraph_error_t igraph_full_multipartite(igraph_t *graph,
                          igraph_vector_int_t *types,
                          const igraph_vector_int_t *n,
                          igraph_bool_t directed,
                          igraph_neimode_t mode);

A multipartite graph contains two or more types of vertices and connections are only possible between two vertices of different types. This function creates a complete multipartite graph.

Arguments: 

Returns: 

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

See also: 

igraph_error_t igraph_turan(igraph_t *graph,
                            igraph_vector_int_t *types,
                            igraph_integer_t n,
                            igraph_integer_t r);

Turán graphs are complete multipartite graphs with the property that the sizes of the partitions are as close to equal as possible.

The Turán graph with n vertices and r partitions is the densest graph on n vertices that does not contain a clique of size r+1.

This function generates undirected graphs. The null graph is returned when the number of vertices is zero. A complete graph is returned if the number of partitions is greater than the number of vertices.

Arguments: 

Returns: 

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

See also: 

igraph_error_t igraph_realize_degree_sequence(
        igraph_t *graph,
        const igraph_vector_int_t *outdeg, const igraph_vector_int_t *indeg,
        igraph_edge_type_sw_t allowed_edge_types,
        igraph_realize_degseq_t method);

This function generates an undirected graph that realizes a given degree sequence, or a directed graph that realizes a given pair of out- and in-degree sequences.

Simple undirected graphs are constructed using the Havel-Hakimi algorithm (undirected case), or the analogous Kleitman-Wang algorithm (directed case). These algorithms work by choosing an arbitrary vertex and connecting all its stubs to other vertices of highest degree. In the directed case, the "highest" (in, out) degree pairs are determined based on lexicographic ordering. This step is repeated until all degrees have been connected up.

Loopless multigraphs are generated using an analogous algorithm: an arbitrary vertex is chosen, and it is connected with a single connection to a highest remaining degee vertex. If self-loops are also allowed, the same algorithm is used, but if a non-zero vertex remains at the end of the procedure, the graph is completed by adding self-loops to it. Thus, the result will contain at most one vertex with self-loops.

The method parameter controls the order in which the vertices to be connected are chosen. In the undirected case, IGRAPH_REALIZE_DEGSEQ_SMALLEST produces a connected graph when one exists. This makes this method suitable for constructing trees with a given degree sequence.

References:

V. Havel: Poznámka o existenci konečných grafů (A remark on the existence of finite graphs), Časopis pro pěstování matematiky 80, 477-480 (1955). http://eudml.org/doc/19050

S. L. Hakimi: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph, Journal of the SIAM 10, 3 (1962). https://www.jstor.org/stable/2098770

D. J. Kleitman and D. L. Wang: Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors, Discrete Mathematics 6, 1 (1973). https://doi.org/10.1016/0012-365X%2873%2990037-X P. L. Erdős, I. Miklós, Z. Toroczkai: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs, The Electronic Journal of Combinatorics 17.1 (2010). http://eudml.org/doc/227072

Sz. Horvát and C. D. Modes: Connectedness matters: construction and exact random sampling of connected networks (2021). https://doi.org/10.1088/2632-072X/abced5

Arguments: 

Returns: 

See also: 

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

int main(void){
    igraph_t g1, g2, g3;
    igraph_integer_t nodes = 500, A = 0, power = 1, m = 1;
    igraph_real_t assortativity;

    igraph_rng_seed(igraph_rng_default(), 42);
    printf("Demonstration of difference in assortativities of graphs with the same degree sequence but different linkages:\n\nInitial graph based on the Barabasi-Albert model with %" IGRAPH_PRId " nodes.\n", nodes);

    /* Graph 1 generated by a randomized graph generator */
    igraph_barabasi_game(&g1, nodes, power, m, NULL, /* outpref */ 0, A, IGRAPH_UNDIRECTED, IGRAPH_BARABASI_PSUMTREE, /* start from */ NULL);

    igraph_vector_int_t degree;
    igraph_vector_int_init(&degree, nodes);
    igraph_degree(&g1, &degree, igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS);

    /* Measuring assortativity of the first graph */
    igraph_assortativity_degree(&g1, &assortativity, IGRAPH_UNDIRECTED);
    printf("Assortativity of initial graph = %g\n\n", assortativity);
    igraph_destroy(&g1);

    /* Graph 2 (with the same degree sequence) generated by selecting vertices with the smallest degree first */
    igraph_realize_degree_sequence(&g2, &degree, NULL, IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_SMALLEST);
    igraph_assortativity_degree(&g2, &assortativity, IGRAPH_UNDIRECTED);
    printf("Assortativity after choosing vertices with the smallest degrees first = %g\n\n", assortativity);
    igraph_destroy(&g2);

    /* Graph 3 (with the same degree sequence) generated by selecting vertices with the largest degree first */
    igraph_realize_degree_sequence(&g3, &degree, NULL, IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_LARGEST);
    igraph_assortativity_degree(&g3, &assortativity, IGRAPH_UNDIRECTED);
    printf("Assortativity after choosing vertices with the largest degrees first = %g\n", assortativity);
    igraph_destroy(&g3);
    igraph_vector_int_destroy(&degree);

    return 0;
}

igraph_error_t igraph_realize_bipartite_degree_sequence(
    igraph_t *graph,
    const igraph_vector_int_t *degrees1, const igraph_vector_int_t *degrees2,
    const igraph_edge_type_sw_t allowed_edge_types, const igraph_realize_degseq_t method
);

This function generates a bipartite graph with the given bidegree sequence, using a Havel-Hakimi-like construction algorithm. The order in which vertices are connected up is controlled by the method parameter. When using the IGRAPH_REALIZE_DEGSEQ_SMALLEST method, it is ensured that the graph will be connected if and only if the given bidegree sequence is potentially connected.

The vertices of the graph will be ordered so that those having degrees1 come first, followed by degrees2.

Arguments: 

Returns: 

See also: 

igraph_error_t igraph_famous(igraph_t *graph, const char *name);

The name of the graph can be simply supplied as a string. Note that this function creates graphs which don't take any parameters, there are separate functions for graphs with parameters, e.g. igraph_full() for creating a full graph.

The following graphs are supported:

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_lcf(igraph_t *graph, igraph_integer_t n, ...);

LCF is short for Lederberg-Coxeter-Frucht, it is a concise notation for 3-regular Hamiltonian graphs. It consists of three parameters: the number of vertices in the graph, a list of shifts giving additional edges to a cycle backbone, and another integer giving how many times the shifts should be performed. See https://mathworld.wolfram.com/LCFNotation.html for details.

Arguments: 

Returns: 

See also: 

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

#include <igraph.h>

int main(void) {

    igraph_t g, g2;
    igraph_bool_t iso;

    // Franklin graph
    igraph_lcf(&g, 12, 5, -5, 6, 0);
    igraph_famous(&g2, "franklin");

    igraph_isomorphic_vf2(&g, &g2,
                          /*vertex.color1=*/ 0, /*vertex.color2=*/ 0,
                          /*edge.color1=*/ 0, /*edge.color2=*/ 0,
                          &iso, 0, 0, 0, 0, 0);
    if (!iso) {
        printf("Failure: Franklin\n");
        return 1;
    }

    igraph_destroy(&g);
    igraph_destroy(&g2);

    // [3, -2]^4, n=8
    igraph_lcf(&g, 8, 3, -2, 4, 0);

    if (igraph_ecount(&g) != 16) {
        printf("Failure: [3, -2]^4, n=8\n");
        return 1;
    }

    igraph_destroy(&g);

    // [2, -2]^2, n=2
    igraph_lcf(&g, 2, 2, -2, 2, 0);

    if (igraph_ecount(&g) != 1) {
        printf("Failure: [2, -2]^2, n=2\n");
        return 1;
    }

    igraph_destroy(&g);

    // [2]^2, n=2
    igraph_lcf(&g, 2, 2, 2, 0);

    if (igraph_ecount(&g) != 1) {
        printf("Failure: [2]^2, n=2\n");
        return 1;
    }

    igraph_destroy(&g);

    // Regression test for bug #996
    igraph_lcf(&g, 0, 0);
    if (igraph_vcount(&g) != 0 || igraph_ecount(&g) != 0) {
        printf("Failure: regression test for #996\n");
        return 1;
    }

    igraph_destroy(&g);

    return 0;
}

igraph_error_t igraph_lcf_vector(igraph_t *graph, igraph_integer_t n,
                      const igraph_vector_int_t *shifts,
                      igraph_integer_t repeats);

This function is essentially the same as igraph_lcf(), only the way for giving the arguments is different. See igraph_lcf() for details.

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_from_prufer(igraph_t *graph, const igraph_vector_int_t *prufer);

A Prüfer sequence is a unique sequence of integers associated with a labelled tree. A tree on n vertices can be represented by a sequence of n-2 integers, each between 0 and n-1 (inclusive). The algorithm used by this function is based on Paulius Micikevičius, Saverio Caminiti, Narsingh Deo: Linear-time Algorithms for Encoding Trees as Sequences of Node Labels

Arguments: 

Returns: 

See also: 

Time complexity: O(|V|), where |V| is the number of vertices in the tree.

igraph_error_t igraph_atlas(igraph_t *graph, igraph_integer_t number);

The graph atlas contains all simple undirected unlabeled graphs on between 0 and 7 vertices. The number of the graph is given as a parameter. The graphs are listed:

The data was converted from the NetworkX software package, see https://networkx.org/.

See An Atlas of Graphs by Ronald C. Read and Robin J. Wilson, Oxford University Press, 1998.

Arguments: 

Added in version 0.2.

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

#include <igraph.h>

int main(void) {

    igraph_t g;

    igraph_atlas(&g, 45);
    igraph_write_graph_edgelist(&g, stdout);
    printf("\n");
    igraph_destroy(&g);

    igraph_atlas(&g, 0);
    igraph_write_graph_edgelist(&g, stdout);
    printf("\n");
    igraph_destroy(&g);

    igraph_atlas(&g, 1252);
    igraph_write_graph_edgelist(&g, stdout);
    printf("\n");
    igraph_destroy(&g);

    return 0;
}

igraph_error_t igraph_de_bruijn(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);

A de Bruijn graph represents relationships between strings. An alphabet of m letters are used and strings of length n are considered. A vertex corresponds to every possible string and there is a directed edge from vertex v to vertex w if the string of v can be transformed into the string of w by removing its first letter and appending a letter to it.

Please note that the graph will have m to the power n vertices and even more edges, so probably you don't want to supply too big numbers for m and n.

De Bruijn graphs have some interesting properties, please see another source, e.g. Wikipedia for details.

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_kautz(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);

A Kautz graph is a labeled graph, vertices are labeled by strings of length n+1 above an alphabet with m+1 letters, with the restriction that every two consecutive letters in the string must be different. There is a directed edge from a vertex v to another vertex w if it is possible to transform the string of v into the string of w by removing the first letter and appending a letter to it. For string length 1 the new letter cannot equal the old letter, so there are no loops.

Kautz graphs have some interesting properties, see e.g. Wikipedia for details.

Vincent Matossian wrote the first version of this function in R, thanks.

Arguments: 

Returns: 

See also: 

Time complexity: O(|V|* [(m+1)/m]^n +|E|), in practice it is more like O(|V|+|E|). |V| is the number of vertices, |E| is the number of edges and m and n are the corresponding arguments.

igraph_error_t igraph_circulant(igraph_t *graph, igraph_integer_t n, const igraph_vector_int_t *shifts, igraph_bool_t directed);

A circulant graph G(n, shifts) consists of n vertices v_0, ..., v_(n-1) such that for each s_i in the list of offsets shifts, v_j is connected to v_((j + s_i) mod n) for all j.

The function can generate either directed or undirected graphs. It does not generate multi-edges or self-loops.

Arguments: 

Returns: 

See also: 

Time complexity: O(|V| |shifts|), the number of vertices in the graph times the number of shifts.

igraph_error_t igraph_generalized_petersen(igraph_t *graph, igraph_integer_t n, igraph_integer_t k);

The generalized Petersen graph G(n, k) consists of n vertices v_0, ..., v_n forming an "outer" cycle graph, and n additional vertices u_0, ..., u_n forming an "inner" circulant graph where u_i is connected to u_(i + k mod n). Additionally, all v_i are connected to u_i.

G(n, k) has 2n vertices and 3n edges. The Petersen graph itself is G(5, 2).

Reference:

M. E. Watkins, A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs, Journal of Combinatorial Theory 6, 152-164 (1969). https://doi.org/10.1016%2FS0021-9800%2869%2980116-X

Arguments: 

Returns: 

See also: 

Time complexity: O(|V|), the number of vertices in the graph.

igraph_error_t igraph_extended_chordal_ring(
    igraph_t *graph, igraph_integer_t nodes, const igraph_matrix_int_t *W,
    igraph_bool_t directed);

An extended chordal ring is a cycle graph with additional chords connecting its vertices. Each row L of the matrix W specifies a set of chords to be inserted, in the following way: vertex i will connect to a vertex L[(i mod p)] steps ahead of it along the cycle, where p is the length of L. In other words, vertex i will be connected to vertex (i + L[(i mod p)]) mod nodes. If multiple edges are defined in this way, this will output a non-simple graph. The result can be simplified using igraph_simplify().

See also Kotsis, G: Interconnection Topologies for Parallel Processing Systems, PARS Mitteilungen 11, 1-6, 1993. The igraph extended chordal rings are not identical to the ones in the paper. In igraph the matrix specifies which edges to add. In the paper, a condition is specified which should simultaneously hold between two endpoints and the reverse endpoints.

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_grg_game(igraph_t *graph, igraph_integer_t nodes,
                    igraph_real_t radius, igraph_bool_t torus,
                    igraph_vector_t *x, igraph_vector_t *y);

A geometric random graph is created by dropping points (i.e. vertices) randomly on the unit square and then connecting all those pairs which are strictly less than radius apart in Euclidean distance.

Original code contributed by Keith Briggs, thanks Keith.

Arguments: 

Returns: 

Time complexity: TODO, less than O(|V|^2+|E|).

#include <igraph.h>
#include <math.h>

int main(void) {
    igraph_t graph;
    igraph_vector_t x, y;
    igraph_vector_t weights;
    igraph_eit_t eit;
    igraph_real_t avg_dist;

    /* Set random seed for reproducible results */

    igraph_rng_seed(igraph_rng_default(), 42);

    /* Create a random geometric graph and retrieve vertex coordinates */

    igraph_vector_init(&x, 0);
    igraph_vector_init(&y, 0);

    igraph_grg_game(&graph, 200, 0.1, /* torus */ 0, &x, &y);

    /* Compute edge weights as geometric distance */

    igraph_vector_init(&weights, igraph_ecount(&graph));
    igraph_eit_create(&graph, igraph_ess_all(IGRAPH_EDGEORDER_ID), &eit);
    for (; ! IGRAPH_EIT_END(eit); IGRAPH_EIT_NEXT(eit)) {
        igraph_integer_t e = IGRAPH_EIT_GET(eit);
        igraph_integer_t u = IGRAPH_FROM(&graph, e);
        igraph_integer_t v = IGRAPH_TO(&graph, e);

        VECTOR(weights)[e] = hypot(VECTOR(x)[u] - VECTOR(x)[v], VECTOR(y)[u] - VECTOR(y)[v]);
    }
    igraph_eit_destroy(&eit);

    /* Compute average path length */

    igraph_average_path_length_dijkstra(&graph, &avg_dist, NULL, &weights, IGRAPH_UNDIRECTED, /* unconn */ 1);

    printf("Average distance in the geometric graph: %g.\n", avg_dist);

    /* Destroy data structures when no longer needed */

    igraph_vector_destroy(&weights);
    igraph_destroy(&graph);
    igraph_vector_destroy(&x);
    igraph_vector_destroy(&y);

    return 0;
}

igraph_error_t igraph_barabasi_game(igraph_t *graph, igraph_integer_t n,
                         igraph_real_t power,
                         igraph_integer_t m,
                         const igraph_vector_int_t *outseq,
                         igraph_bool_t outpref,
                         igraph_real_t A,
                         igraph_bool_t directed,
                         igraph_barabasi_algorithm_t algo,
                         const igraph_t *start_from);

This function implements several variants of the preferential attachment process, including linear and non-linear varieties of the Barabási-Albert and Price models. The graph construction starts with a single vertex, or an existing graph given by the start_from parameter. Then new vertices are added one at a time. Each new vertex connects to m existing vertices, choosing them with probabilities proportional to

d^power + A,

where d is the in- or total degree of the existing vertex (controlled by the outpref argument), while power and A are given by parameters. The constant attractiveness A is used to ensure that vertices with zero in-degree can also be connected to with non-zero probability.

Barabási, A.-L. and Albert R. 1999. Emergence of scaling in random networks, Science, 286 509--512. https://doi.org/10.1126/science.286.5439.509

de Solla Price, D. J. 1965. Networks of Scientific Papers, Science, 149 510--515. https://doi.org/10.1126/science.149.3683.510

Arguments: 

Returns: 

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

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_t v;
    igraph_vector_int_t v2, v3;

    igraph_barabasi_game(&g, 10, /*power=*/ 1, 2, 0, 0, /*A=*/ 1, 1,
                         IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
    if (igraph_ecount(&g) != 18) {
        return 1;
    }
    if (igraph_vcount(&g) != 10) {
        return 2;
    }
    if (!igraph_is_directed(&g)) {
        return 3;
    }

    igraph_vector_int_init(&v, 0);
    igraph_get_edgelist(&g, &v, 0);
    for (igraph_integer_t i = 0; i < igraph_ecount(&g); i++) {
        if (VECTOR(v)[2 * i] <= VECTOR(v)[2 * i + 1]) {
            return 4;
        }
    }
    igraph_vector_int_destroy(&v);
    igraph_destroy(&g);

    /* out-degree sequence */
    igraph_vector_int_init_int(&v3, 10, 0, 1, 3, 3, 4, 5, 6, 7, 8, 9);

    igraph_barabasi_game(&g, 10, /*power=*/ 1, 0, &v3, 0, /*A=*/ 1, 1,
                         IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
    if (igraph_ecount(&g) != igraph_vector_int_sum(&v3)) {
        return 5;
    }
    igraph_vector_int_init(&v2, 0);
    igraph_degree(&g, &v2, igraph_vss_all(), IGRAPH_OUT, 1);
    for (igraph_integer_t i = 0; i < igraph_vcount(&g); i++) {
        if (VECTOR(v3)[i] != VECTOR(v2)[i]) {
            igraph_vector_int_print(&v3);
            printf("\n");
            igraph_vector_int_print(&v2);
            return 6;
        }
    }
    igraph_vector_int_destroy(&v3);
    igraph_vector_int_destroy(&v2);
    igraph_destroy(&g);

    /* outpref, we cannot really test this quantitatively,
       would need to set random seed */
    igraph_barabasi_game(&g, 10, /*power=*/ 1, 2, 0, 1, /*A=*/ 1, 1,
                         IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
    igraph_vector_int_init(&v, 0);
    igraph_get_edgelist(&g, &v, 0);
    for (igraph_integer_t i = 0; i < igraph_ecount(&g); i++) {
        if (VECTOR(v)[2 * i] <= VECTOR(v)[2 * i + 1]) {
            return 7;
        }
    }
    if (!igraph_is_directed(&g)) {
        return 8;
    }
    igraph_vector_int_destroy(&v);
    igraph_destroy(&g);

    return 0;
}

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

int main(void) {

    igraph_t g;
    igraph_bool_t simple;

    igraph_barabasi_game(/* graph=    */ &g,
                                         /* n=        */ 100,
                                         /* power=    */ 1.0,
                                         /* m=        */ 2,
                                         /* outseq=   */ 0,
                                         /* outpref=  */ 0,
                                         /* A=        */ 1.0,
                                         /* directed= */ IGRAPH_DIRECTED,
                                         /* algo=     */ IGRAPH_BARABASI_PSUMTREE,
                                         /* start_from= */ 0);

    if (igraph_ecount(&g) != 197) {
        return 1;
    }
    if (igraph_vcount(&g) != 100) {
        return 2;
    }
    igraph_is_simple(&g, &simple);
    if (!simple) {
        return 3;
    }

    igraph_destroy(&g);

    /* ============================== */

    igraph_barabasi_game(/* graph=    */ &g,
                                         /* n=        */ 100,
                                         /* power=    */ 1.0,
                                         /* m=        */ 2,
                                         /* outseq=   */ 0,
                                         /* outpref=  */ 0,
                                         /* A=        */ 1.0,
                                         /* directed= */ IGRAPH_DIRECTED,
                                         /* algo=     */ IGRAPH_BARABASI_PSUMTREE_MULTIPLE,
                                         /* start_from= */ 0);

    if (igraph_ecount(&g) != 198) {
        return 4;
    }
    if (igraph_vcount(&g) != 100) {
        return 5;
    }
    igraph_is_simple(&g, &simple);
    if (simple) {
        return 6;
    }

    igraph_destroy(&g);

    /* ============================== */

    igraph_barabasi_game(/* graph=    */ &g,
                                         /* n=        */ 100,
                                         /* power=    */ 1.0,
                                         /* m=        */ 2,
                                         /* outseq=   */ 0,
                                         /* outpref=  */ 0,
                                         /* A=        */ 1.0,
                                         /* directed= */ IGRAPH_DIRECTED,
                                         /* algo=     */ IGRAPH_BARABASI_BAG,
                                         /* start_from= */ 0);

    if (igraph_ecount(&g) != 198) {
        return 7;
    }
    if (igraph_vcount(&g) != 100) {
        return 8;
    }
    igraph_is_simple(&g, &simple);
    if (simple) {
        return 9;
    }

    igraph_destroy(&g);

    return 0;
}

igraph_error_t igraph_erdos_renyi_game_gnm(
    igraph_t *graph, igraph_integer_t n, igraph_integer_t m,
    igraph_bool_t directed, igraph_bool_t loops, igraph_bool_t multiple
);

In the G(n, m) Erdős-Rényi model, a graph with n vertices and m edges is generated uniformly at random.

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_vector_int_t component_sizes;

    igraph_rng_seed(igraph_rng_default(), 42); /* make program deterministic */

    /* Sample a graph from the Erdős-Rényi G(n,m) model */

    igraph_erdos_renyi_game_gnm(
        &graph, /* n= */ 100, /* m= */ 100,
        IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE
    );

    /* Compute the fraction of vertices contained within the largest connected component */

    igraph_vector_int_init(&component_sizes, 0);
    igraph_connected_components(&graph, NULL, &component_sizes, NULL, IGRAPH_STRONG);

    printf(
        "Fraction of vertices in giant component: %g\n",
        ((double) igraph_vector_int_max(&component_sizes)) / igraph_vcount(&graph)
    );

    /* Clean up data structures when no longer needed */

    igraph_vector_int_destroy(&component_sizes);
    igraph_destroy(&graph);

    return 0;
}

igraph_error_t igraph_erdos_renyi_game_gnp(
    igraph_t *graph, igraph_integer_t n, igraph_real_t p,
    igraph_bool_t directed, igraph_bool_t loops
);

In the G(n, p) Erdős-Rényi model, also known as the Gilbert model, or Bernoulli random graph, a graph with n vertices is generated such that every possible edge is included in the graph independently with probability p. This is equivalent to a maximum entropy random graph model model with a constraint on the expected edge count. Setting p = 1/2 generates all graphs on n vertices with the same probability.

The expected mean degree of the graph is approximately p n; set p = k/n when a mean degree of approximately k is desired. More precisely, the expected mean degree is p(n-1) in (undirected or directed) graphs without self-loops, p(n+1) in undirected graphs with self-loops, and p n in directed graphs with self-loops.

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_vector_int_t component_sizes;

    igraph_rng_seed(igraph_rng_default(), 42); /* make program deterministic */

    /* Sample a graph from the Erdős-Rényi G(n,p) model */

    igraph_erdos_renyi_game_gnp(
        &graph, /* n= */ 100, /* p= */ 0.01,
        IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS
    );

    /* Compute the fraction of vertices contained within the largest connected component */

    igraph_vector_int_init(&component_sizes, 0);
    igraph_connected_components(&graph, NULL, &component_sizes, NULL, IGRAPH_STRONG);

    printf(
        "Fraction of vertices in giant component: %g\n",
        ((double) igraph_vector_int_max(&component_sizes)) / igraph_vcount(&graph)
    );

    /* Clean up data structures when no longer needed */

    igraph_vector_int_destroy(&component_sizes);
    igraph_destroy(&graph);

    return 0;
}

igraph_error_t igraph_watts_strogatz_game(igraph_t *graph, igraph_integer_t dim,
                               igraph_integer_t size, igraph_integer_t nei,
                               igraph_real_t p, igraph_bool_t loops,
                               igraph_bool_t multiple);

This function generates networks with the small-world property based on a variant of the Watts-Strogatz model. The network is obtained by first creating a periodic undirected lattice, then rewiring both endpoints of each edge with probability p, while avoiding the creation of multi-edges.

This process differs from the original model of Watts and Strogatz (see reference) in that it rewires both endpoints of edges. Thus in the limit of p=1, we obtain a G(n,m) random graph with the same number of vertices and edges as the original lattice. In comparison, the original Watts-Strogatz model only rewires a single endpoint of each edge, thus the network does not become fully random even for p=1. For appropriate choices of p, both models exhibit the property of simultaneously having short path lengths and high clustering.

Reference:

Duncan J Watts and Steven H Strogatz: Collective dynamics of “small world” networks, Nature 393, 440-442, 1998. https://doi.org/10.1038/30918

Arguments: 

Returns: 

See also: 

Time complexity: O(|V|*d^o+|E|), |V| and |E| are the number of vertices and edges, d is the average degree, o is the nei argument.

igraph_error_t igraph_rewire_edges(igraph_t *graph, igraph_real_t prob,
                        igraph_bool_t loops, igraph_bool_t multiple);

This function rewires the edges of a graph with a constant probability. More precisely each end point of each edge is rewired to a uniformly randomly chosen vertex with constant probability prob.

Note that this function modifies the input graph, call igraph_copy() if you want to keep it.

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_rewire_directed_edges(igraph_t *graph, igraph_real_t prob,
                                 igraph_bool_t loops, igraph_neimode_t mode);

This function rewires either the start or end of directed edges in a graph with a constant probability. Correspondingly, either the in-degree sequence or the out-degree sequence of the graph will be preserved.

Note that this function modifies the input graph, call igraph_copy() if you want to keep it.

This function can produce multiple edges between two vertices.

Arguments: 

Returns: 

See also: 

Time complexity: O(|E|).

igraph_error_t igraph_degree_sequence_game(
        igraph_t *graph,
        const igraph_vector_int_t *out_degrees,
        const igraph_vector_int_t *in_degrees,
        igraph_degseq_t method);

This function generates random graphs with a prescribed degree sequence. Several sampling methods are available, which respect different constraints (simple graph or multigraphs, connected graphs, etc.), and provide different tradeoffs between performance and unbiased sampling. See Section 2.1 of Horvát and Modes (2021) for an overview of sampling techniques for graphs with fixed degrees.

References:

Fabien Viger, and Matthieu Latapy: Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence, Journal of Complex Networks 4, no. 1, pp. 15–37 (2015). https://doi.org/10.1093/comnet/cnv013.

Szabolcs Horvát, and Carl D Modes: Connectedness Matters: Construction and Exact Random Sampling of Connected Networks, Journal of Physics: Complexity 2, no. 1, pp. 015008 (2021). https://doi.org/10.1088/2632-072x/abced5.

Arguments: 

Returns: 

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges for IGRAPH_DEGSEQ_CONFIGURATION and IGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE. The time complexity of the other modes is not known.

See also: 

#include <igraph.h>

int main(void) {
    igraph_t g;
    igraph_vector_int_t outdeg, indeg;
    igraph_vector_int_t vec;
    igraph_bool_t is_simple;

    /* Set random seed for reproducibility */
    igraph_rng_seed(igraph_rng_default(), 42);

    igraph_vector_int_init_int(&outdeg, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3);
    igraph_vector_int_init_int(&indeg, 10, 4, 4, 2, 2, 4, 4, 2, 2, 3, 3);
    igraph_vector_int_init(&vec, 0);

    /* checking the configuration model, undirected graphs */
    igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_CONFIGURATION);
    if (igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 1;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) {
        return 2;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    /* checking the Viger-Latapy method, undirected graphs */
    igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_VL);
    if (igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 3;
    }
    if (igraph_is_simple(&g, &is_simple) || !is_simple) {
        return 4;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 0)) {
        return 5;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    /* checking the configuration model, directed graphs */
    igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_CONFIGURATION);
    if (!igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 6;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) {
        return 7;
    }
    igraph_vector_int_print(&vec);
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_IN, 1)) {
        return 8;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    /* checking the fast heuristic method, undirected graphs */
    igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE);
    if (igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 9;
    }
    if (igraph_is_simple(&g, &is_simple) || !is_simple) {
        return 10;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) {
        return 11;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    /* checking the fast heuristic method, directed graphs */
    igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE);
    if (!igraph_is_directed(&g) || igraph_vcount(&g) != 10) {
        return 12;
    }
    if (igraph_is_simple(&g, &is_simple) || !is_simple) {
        return 13;
    }
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) {
        return 14;
    }
    igraph_vector_int_print(&vec);
    if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_IN, 1)) {
        return 15;
    }
    igraph_vector_int_print(&vec);
    igraph_destroy(&g);

    igraph_vector_int_destroy(&vec);
    igraph_vector_int_destroy(&outdeg);
    igraph_vector_int_destroy(&indeg);

    return 0;
}

igraph_error_t igraph_k_regular_game(igraph_t *graph,
                          igraph_integer_t no_of_nodes, igraph_integer_t k,
                          igraph_bool_t directed, igraph_bool_t multiple);

This game generates a directed or undirected random graph where the degrees of vertices are equal to a predefined constant k. For undirected graphs, at least one of k and the number of vertices must be even.

Currently, this game simply uses igraph_degree_sequence_game with the IGRAPH_DEGSEQ_CONFIGURATION or the IGRAPH_DEGSEQ_FAST_SIMPLE method and appropriately constructed degree sequences. Thefore, it does not sample uniformly: while it can generate all k-regular graphs with the given number of vertices, it does not generate each one with the same probability.

Arguments: 

Returns: 

Time complexity: O(|V|+|E|) if multiple is true, otherwise not known.

igraph_error_t igraph_static_fitness_game(igraph_t *graph, igraph_integer_t no_of_edges,
                               const igraph_vector_t *fitness_out, const igraph_vector_t *fitness_in,
                               igraph_bool_t loops, igraph_bool_t multiple);

This game generates a directed or undirected random graph where the probability of an edge between vertices i and j depends on the fitness scores of the two vertices involved. For undirected graphs, each vertex has a single fitness score. For directed graphs, each vertex has an out- and an in-fitness, and the probability of an edge from i to j depends on the out-fitness of vertex i and the in-fitness of vertex j.

The generation process goes as follows. We start from N disconnected nodes (where N is given by the length of the fitness vector). Then we randomly select two vertices i and j, with probabilities proportional to their fitnesses. (When the generated graph is directed, i is selected according to the out-fitnesses and j is selected according to the in-fitnesses). If the vertices are not connected yet (or if multiple edges are allowed), we connect them; otherwise we select a new pair. This is repeated until the desired number of links are created.

The expected degree (though not the actual degree) of each vertex will be proportional to its fitness. This is exactly true when self-loops and multi-edges are allowed, and approximately true otherwise. If you need to generate a graph with an exact degree sequence, consider igraph_degree_sequence_game() and igraph_realize_degree_sequence() instead.

To generate random undirected graphs with a given expected degree sequence, set fitness_out (and in the directed case fitness_out) to the desired expected degrees, and no_of_edges to the corresponding edge count, i.e. half the sum of expected degrees in the undirected case, and the sum of out- or in-degrees in the directed case.

This model is similar to the better-known Chung-Lu model, implemented in igraph as igraph_chung_lu_game(), but with a sharply fixed edge count.

This model is commonly used to generate static scale-free networks. To achieve this, you have to draw the fitness scores from the desired power-law distribution. Alternatively, you may use igraph_static_power_law_game() which generates the fitnesses for you with a given exponent.

Reference:

Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001 https://doi.org/10.1103/PhysRevLett.87.278701.

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_static_power_law_game(igraph_t *graph,
                                 igraph_integer_t no_of_nodes, igraph_integer_t no_of_edges,
                                 igraph_real_t exponent_out, igraph_real_t exponent_in,
                                 igraph_bool_t loops, igraph_bool_t multiple,
                                 igraph_bool_t finite_size_correction);

This game generates a directed or undirected random graph where the degrees of vertices follow power-law distributions with prescribed exponents. For directed graphs, the exponents of the in- and out-degree distributions may be specified separately.

The game simply uses igraph_static_fitness_game() with appropriately constructed fitness vectors. In particular, the fitness of vertex i is i^(-alpha), where alpha = 1/(gamma-1) and gamma is the exponent given in the arguments.

To remove correlations between in- and out-degrees in case of directed graphs, the in-fitness vector will be shuffled after it has been set up and before igraph_static_fitness_game() is called.

Note that significant finite size effects may be observed for exponents smaller than 3 in the original formulation of the game. This function provides an argument that lets you remove the finite size effects by assuming that the fitness of vertex i is (i+i0-1)^(-alpha), where i0 is a constant chosen appropriately to ensure that the maximum degree is less than the square root of the number of edges times the average degree; see the paper of Chung and Lu, and Cho et al for more details.

References:

Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001. https://doi.org/10.1103/PhysRevLett.87.278701

Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002. https://doi.org/10.1007/PL00012580

Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009. https://doi.org/10.1103/PhysRevLett.103.135702

Arguments: 

Returns: 

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

igraph_error_t igraph_chung_lu_game(igraph_t *graph,
                                    const igraph_vector_t *out_weights,
                                    const igraph_vector_t *in_weights,
                                    igraph_bool_t loops,
                                    igraph_chung_lu_t variant);

The Chung-Lu model is useful for generating random graphs with fixed expected degrees. This function implements both the original model of Chung and Lu, as well as some additional variants with useful properties.

In the original Chung-Lu model, each pair of vertices i and j is connected with independent probability p_ij = w_i w_j / S, where w_i is a weight associated with vertex i and S = sum_k w_k is the sum of weights. In the directed variant, vertices have both out-weights, w^out, and in-weights, w^in, with equal sums, S = sum_k w^out_k = sum_k w^in_k. The connection probability between i and j is p_ij = w^out_i w^in_j / S.

This model is commonly used to create random graphs with a fixed expected degree sequence. The expected degree of vertex i is approximately equal to the weight w_i. Specifically, if the graph is directed and self-loops are allowed, then the expected out- and in-degrees are precisely w^out and w^in. If self-loops are disallowed, then the expected out- and in-degrees are w^out (S - w^in) / S and w^in (S - w^out) / S, respectively. If the graph is undirected, then the expected degrees with and without self-loops are w (S + w) / S and w (S - w) / S, respectively.

A limitation of the original Chung-Lu model is that when some of the weights are large, the formula for p_ij yields values larger than 1. Chung and Lu's original paper excludes the use of such weights. When p_ij > 1, this function simply issues a warning and creates a connection between i and j. However, in this case the expected degrees will no longer relate to the weights in the manner stated above. Thus the original Chung-Lu model cannot produce certain (large) expected degrees.

The overcome this limitation, this function implements additional variants of the model, with modified expressions for the connection probability p_ij between vertices i and j. Let q_ij = w_i w_j / S, or q_ij = w^out_i w^in_j / S in the directed case. All model variants become equivalent in the limit of sparse graphs where q_ij approaches zero. In the original Chung-Lu model, selectable by setting variant to IGRAPH_CHUNG_LU_ORIGINAL, p_ij = min(q_ij, 1). The IGRAPH_CHUNG_LU_MAXENT variant, sometiems referred to a the generalized random graph, uses p_ij = q_ij / (1 + q_ij), and is equivalent to a maximum entropy model (i.e. exponential random graph model) with a constraint on expected degrees; see Park and Newman (2004), Section B, setting exp(-Theta_ij) = w_i w_j / S. This model is also discussed by Britton, Deijfen and Martin-Löf (2006). By virtue of being a degree-constrained maximum entropy model, it produces graphs with the same degree sequence with the same probability. A third variant can be requested with IGRAPH_CHUNG_LU_NR, and uses p_ij = 1 - exp(-q_ij). This is the underlying simple graph of a multigraph model introduced by Norros and Reittu (2006). For a discussion of these three model variants, see Section 16.4 of Bollobás, Janson, Riordan (2007), as well as Van Der Hofstad (2013).

References:

Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145 (2002). https://doi.org/10.1007/PL00012580

Miller JC and Hagberg A: Efficient Generation of Networks with Given Expected Degrees (2011). https://doi.org/10.1007/978-3-642-21286-4_10

Park J and Newman MEJ: Statistical mechanics of networks. Physical Review E 70, 066117 (2004). https://doi.org/10.1103/PhysRevE.70.066117

Britton T, Deijfen M, Martin-Löf A: Generating Simple Random Graphs with Prescribed Degree Distribution. J Stat Phys 124, 1377–1397 (2006). https://doi.org/10.1007/s10955-006-9168-x

Norros I and Reittu H: On a conditionally Poissonian graph process. Advances in Applied Probability 38, 59–75 (2006). https://doi.org/10.1239/aap/1143936140

Bollobás B, Janson S, Riordan O: The phase transition in inhomogeneous random graphs. Random Struct Algorithms 31, 3–122 (2007). https://doi.org/10.1002/rsa.20168

Van Der Hofstad R: Critical behavior in inhomogeneous random graphs. Random Struct Algorithms 42, 480–508 (2013). https://doi.org/10.1002/rsa.20450

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_forest_fire_game(igraph_t *graph, igraph_integer_t nodes,
                            igraph_real_t fw_prob, igraph_real_t bw_factor,
                            igraph_integer_t pambs, igraph_bool_t directed);

The forest fire model intends to reproduce the following network characteristics, observed in real networks:

The network is generated in the following way. One vertex is added at a time. This vertex connects to (cites) ambs vertices already present in the network, chosen uniformly random. Now, for each cited vertex v we do the following procedure:

See also: Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. KDD '05: Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining , 177--187, 2005.

Note however, that the version of the model in the published paper is incorrect in the sense that it cannot generate the kind of graphs the authors claim. A corrected version is available from http://cs.stanford.edu/people/jure/pubs/powergrowth-tkdd.pdf , our implementation is based on this.

Arguments: 

Returns: 

Time complexity: TODO.

igraph_error_t igraph_rewire(igraph_t *graph, igraph_integer_t n, igraph_rewiring_t mode);

This function generates a new graph based on the original one by randomly "rewriting" edges while preserving the original graph's degree sequence. The rewiring is done "in place", so no new graph will be allocated. If you would like to keep the original graph intact, use igraph_copy() beforehand. All graph attributes will be lost.

The rewiring is performed with degree-preserving edge switches: Two arbitrary edges are picked uniformly at random, namely (a, b) and (c, d), then they are replaced by (a, d) and (b, c) if this preserves the constraints specified by mode.

Arguments: 

Returns: 

Time complexity: TODO.

igraph_error_t igraph_growing_random_game(igraph_t *graph, igraph_integer_t n,
                               igraph_integer_t m, igraph_bool_t directed,
                               igraph_bool_t citation);

This function simulates a growing random graph. We start out with one vertex. In each step a new vertex is added and a number of new edges are also added. These graphs are known to be different from standard (not growing) random graphs.

Arguments: 

Returns: 

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

igraph_error_t igraph_callaway_traits_game(igraph_t *graph, igraph_integer_t nodes,
                                igraph_integer_t types, igraph_integer_t edges_per_step,
                                const igraph_vector_t *type_dist,
                                const igraph_matrix_t *pref_matrix,
                                igraph_bool_t directed,
                                igraph_vector_int_t *node_type_vec);

The different types of vertices prefer to connect other types of vertices with a given probability.

The simulation goes like this: in each discrete time step a new vertex is added to the graph. The type of this vertex is generated based on type_dist. Then two vertices are selected uniformly randomly from the graph. The probability that they will be connected depends on the types of these vertices and is taken from pref_matrix. Then another two vertices are selected and this is repeated edges_per_step times in each time step.

References:

D. S. Callaway, J. E. Hopcroft, J. M. Kleinberg, M. E. J. Newman, and S. H. Strogatz, Are randomly grown graphs really random? Phys. Rev. E 64, 041902 (2001). https://doi.org/10.1103/PhysRevE.64.041902

Arguments: