1.1.igraph_create — Creates a graph with the specified edges.

1.2.igraph_small — Shorthand to create a small graph, giving the edges as arguments.

1.3.igraph_adjacency — Creates a graph from an adjacency matrix.

1.4.igraph_weighted_adjacency — Creates a graph from a weighted adjacency matrix.

1.5.igraph_sparse_adjacency — Creates a graph from a sparse adjacency matrix.

1.6.igraph_sparse_weighted_adjacency — Creates a graph from a weighted sparse adjacency matrix.

1.7.igraph_adjlist — Creates a graph from an adjacency list.

1.8.igraph_star — Creates astar graph, every vertex connects only to the center.

1.9.igraph_wheel — Creates awheel graph, a union of a star and a cycle graph.

1.10.igraph_hypercube — The n-dimensional hypercube graph.

1.11.igraph_square_lattice — Arbitrary dimensional square lattices.

1.12.igraph_triangular_lattice — A triangular lattice with the given shape.

1.13.igraph_hexagonal_lattice — A hexagonal lattice with the given shape.

1.14.igraph_ring — Creates acycle graph or apath graph.

1.15.igraph_path_graph — A path graphP_n.

1.16.igraph_cycle_graph — A cycle graphC_n.

1.17.igraph_kary_tree — Creates a k-ary tree in which almost all vertices have k children.

1.18.igraph_symmetric_tree — Creates a symmetric tree with the specified number of branches at each level.

1.19.igraph_regular_tree — Creates a regular tree.

1.20.igraph_tree_from_parent_vector — Constructs a tree or forest from a vector encoding the parent of each vertex.

1.21.igraph_full — Creates a full graph (complete graph).

1.22.igraph_full_citation — Creates a full citation graph (a complete directed acyclic graph).

1.23.igraph_full_multipartite — Creates a full multipartite graph.

1.24.igraph_turan — Creates a Turán graph.

1.25.igraph_realize_degree_sequence — Generates a graph with the given degree sequence.

1.26.igraph_realize_bipartite_degree_sequence — Generates a bipartite graph with the given bidegree sequence.

1.27.igraph_famous — Create a famous graph by simply providing its name.

1.28.igraph_lcf — Creates a graph from LCF notation.

1.29.igraph_lcf_vector — Creates a graph from LCF notation.

1.30.igraph_mycielski_graph — The Mycielski graph of orderk.

1.31.igraph_from_prufer — Generates a tree from a Prüfer sequence.

1.32.igraph_atlas — Create a small graph from the“Graph Atlas”.

1.33.igraph_de_bruijn — Generate a de Bruijn graph.

1.34.igraph_kautz — Generate a Kautz graph.

1.35.igraph_circulant — Creates a circulant graph.

1.36.igraph_generalized_petersen — Creates a Generalized Petersen graph.

1.37.igraph_extended_chordal_ring — Create an extended chordal ring.

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

#include <igraph.h>intmain(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 asarguments and a-1 needs to be given after the last meaningfuledge argument.

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

Arguments: 

Returns: 

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

#include <igraph.h>intmain(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 vertexcorresponding to the first row/column will be vertex with id 0, thenext row is for vertex 1, etc.

Arguments: 

Returns: 

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

#include <igraph.h>intmain(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 vertexcorresponding to the first row/column will be vertex with id 0, thenext row is for vertex 1, etc.

Arguments: 

Returns: 

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

#include <igraph.h>#include <stdarg.h>intmain(void) {    igraph_matrix_t mat;    igraph_t g;    int m[4][4] = { { 0, 1, 2, 0 }, { 2, 0, 0, 1 }, { 0, 0, 1, 0 }, { 0, 1, 0, 0 } };igraph_vector_t weights;    igraph_vector_int_t el;    igraph_integer_t i, j, n;igraph_vector_int_init(&el, 0);igraph_vector_init(&weights, 0);igraph_matrix_init(&mat, 4, 4);for (i = 0; i < 4; i++)for (j = 0; j < 4; j++) {MATRIX(mat, i, j) = m[i][j];    }igraph_weighted_adjacency(&g, &mat, IGRAPH_ADJ_DIRECTED, &weights, IGRAPH_LOOPS_ONCE);igraph_get_edgelist(&g, &el, 0);    n =igraph_ecount(&g);for (i = 0, j = 0; i < n; i++, j += 2) {printf("%" IGRAPH_PRId " --> %" IGRAPH_PRId ": %g\n",VECTOR(el)[j],VECTOR(el)[j + 1],VECTOR(weights)[i]);    }igraph_matrix_destroy(&mat);igraph_vector_destroy(&weights);igraph_vector_int_destroy(&el);igraph_destroy(&g);}

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 asigraph_adjacency(), but usesa 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 asigraph_weighted_adjacency(), but usesa 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 neighborsof all vertices. For operations that involve many changes to thegraph structure, it is recommended that you convert the graph intoan adjacency list viaigraph_adjlist_init(), perform themodifications (these are cheap for an adjacency list) and thenrecreate 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|), thenumber of vertices in the graph.

See also: 

#include <igraph.h>#include <stdio.h>intmain(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 onn vertices can be thought of as a wheel withn - 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-vertexwheel graph contains parallel edges (a 1-cycle and a 2-cycle, respectively).

Arguments: 

Returns: 

Time complexity: O(|V|), thenumber 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 graphQ_n has2^n vertices and2^(n-1) n edges. Two vertices are connected when the binaryrepresentations 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 givengraph distance can be connected.

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

The vertices of the resulting graph are ordered such that theindex 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 bei_1 + n_1 * i_2 + n_1 * n_2 * i_3 + ....

Arguments: 

Returns: 

See also: 

Time complexity: Ifnei is less than two then it is O(|V|+|E|) (asfar as I remember), |V| and |E| are the number of verticesand edges in the generated graph. Otherwise it is O(|V|*d^k+|E|), dis the average degree of the graph, k is thenei 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-negativeintegers 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 graphconstructed byigraph_hexagonal_lattice(). In particular, there a one-to-onecorrespondence between the vertices in the constructed graph and the cycles oflength 6 in the graph constructed byigraph_hexagonal_lattice()with the samedims parameter.

The vertices of the resulting graph are ordered lexicographically with the 2ndcoordinate 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-negativeintegers i and j and (i, j) is generally connected with (i + 1, j), and if i isodd also with (i - 1, j + 1). The function constructs a planar dual of the graphconstructed byigraph_triangular_lattice(). In particular, there a one-to-onecorrespondence between the cycles of length 6 in the constructed graph and thevertices of the graph constructed byigraph_triangular_lattice() functionwith the samedims parameter.

The vertices of the resulting graph are ordered lexicographically with the 2ndcoordinate 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 onn vertices is commonly known in graphtheory as the cycle graph, and often denoted byC_n.Removing a single edge from the cycle graphC_n resultsin the path graphP_n. This function can generate both.

Whenn is 1 or 2, the result may not be a simple graph:the one-cycle contains a self-loop and the undirected or reciprocallyconnected 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>intmain(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_path_graph(        igraph_t *graph, igraph_integer_t n,        igraph_bool_t directed, igraph_bool_t mutual);

Creates the path graphP_n onn vertices.

This is a convenience wrapper toigraph_ring().

Arguments: 

Returns: 

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

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

Creates the cycle graphC_n onn vertices.

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

This is a convenience wrapper toigraph_ring().

Arguments: 

Returns: 

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

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 withl layers, where eachvertex has preciselychildren descendants, usen = (children^(l+1) - 1) / (children - 1).Such trees are often calledk-ary trees, wherek refersto the number of children.

Note that forn=0, the null graph is returned,which is not considered to be a tree byigraph_is_tree().

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>intmain(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 distanced from theroot havebranching_counts[d] children.

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>intmain(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 degreek.This is different from a k-ary tree (igraph_kary_tree()), where allvertices have the same number of children, thus the degre of the root isone less than the degree of the other internal vertices. Regular treesare also referred to as Bethe lattices.

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>intmain(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 aparentsvector where the ID of the parent of vertexv is stored inparents[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 theparents vectoris found to encode a cycle or a self-loop, an error is raised.

Several igraph functions produce such vectors, such as graph traversalfunctions (igraph_bfs() andigraph_dfs()), shortest path functionsthat construct a shortest path tree, as well as some other specializedfunctions likeigraph_dominator_tree() origraph_cohesive_blocks().Vertices which do not have parents (i.e. roots) get a negative entry in theparents vector.

Useigraph_bfs() origraph_dfs() to convert a forest into a parentvector representation. For trees, i.e. forests with a single root, it ismore convenient to useigraph_bfs_simple().

Arguments: 

Returns: 

See also: 

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

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 isconnected to every other vertex.igraph generalizes the usualconcept of complete graphs in graph theory to graphs with self-loopsas 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>intmain(void) {    igraph_t graph;    igraph_integer_t n_vertices = 10;/* Create an undirected complete graph. *//* Use IGRAPH_UNDIRECTED and IGRAPH_NO_LOOPS instead of 1/TRUE and 0/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 everyi->j edge ispresent if and only ifj<i.If thedirected argument is false then an undirected graph iscreated, 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 connectionsare only possible between two vertices of different types. This functioncreates a complete multipartite graph.

Arguments: 

Returns: 

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

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 propertythat the sizes of the partitions are as close to equal as possible.

The Turán graph withn vertices andr partitions is the densestgraph onn vertices that does not contain a clique of sizer+1.

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

Arguments: 

Returns: 

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

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 degreesequence, or a directed graph that realizes a given pair of out- andin-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 itsstubs to other vertices of highest degree. In the directed case, the"highest" (in, out) degree pairs are determined based on lexicographicordering. This step is repeated until all degrees have been connected up.

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

Themethod parameter controls the order in which the vertices to beconnected are chosen. In the undirected case,IGRAPH_REALIZE_DEGSEQ_SMALLESTproduces a connected graph when one exists. This makes this method suitablefor constructing trees with a given degree sequence.

For a undirected simple graph, the time complexity is O(V + alpha(V) * E).For an undirected multi graph, the time complexity is O(V * E + V log V).For a directed graph, the time complexity is O(E + V^2 log V).

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-XP. 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>intmain(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 verticesare connected up is controlled by themethod parameter. When using theIGRAPH_REALIZE_DEGSEQ_SMALLEST method, it is ensured that the graph will beconnected if and only if the given bidegree sequence is potentially connected.

The vertices of the graph will be ordered so that those havingdegrees1come first, followed bydegrees2.

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 numberof 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 for3-regular Hamiltonian graphs. It consists of three parameters: thenumber of vertices in the graph, a list of shifts giving additionaledges to a cycle backbone, and another integer giving how many timesthe shifts should be performed. Seehttps://mathworld.wolfram.com/LCFNotation.html for details.

Arguments: 

Returns: 

See also: 

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

#include <igraph.h>intmain(void) {    igraph_t g, g2;    igraph_bool_t iso;// Franklin graphigraph_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=8igraph_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=2igraph_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=2igraph_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 #996igraph_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 asigraph_lcf(), onlythe way for giving the arguments is different. Seeigraph_lcf() for details.

Arguments: 

Returns: 

See also: 

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

igraph_error_t igraph_mycielski_graph(igraph_t *graph, igraph_integer_t k);

The Mycielski graph of orderk, denotedM_k, is a triangle-free graph onk vertices with chromatic numberk. It is defined through the Mycielskiconstruction described in the documentation ofigraph_mycielskian().

Some authors define Mycielski graphs only fork > 1.igraph extends this to allk >= 0.The first few Mycielski graphs are:

The vertex count ofM_k isn_k = 3 * 2^(k-2) - 1 fork > 1 andk otherwise.The edge count ism_k = (7 * 3^(k-2) + 1) / 2 - 3 * 2^(k - 2) fork > 1and 0 otherwise.

Arguments: 

Returns: 

See also: 

Time complexity: O(3^k), i.e. exponential ink.

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 associatedwith a labelled tree. A tree onn vertices can be representedby a sequence ofn-2 integers, each between0 andn-1 (inclusive).The algorithm used by this function is based onPaulius 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 between0 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,seehttps://networkx.org/.

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

Arguments: 

Returns: 

Added in version 0.2.

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

#include <igraph.h>intmain(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 alphabetofm letters are used and strings of lengthn are considered.A vertex corresponds to every possible string and there is a directed edgefrom vertexv to vertexw if the string ofv can be transformed intothe string ofw by removing its first letter and appending a letter to it.

Please note that the graph will havem to the powern vertices andeven more edges, so probably you don't want to supply too big numbers form andn.

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 stringsof lengthn+1 above an alphabet withm+1 letters, withthe restriction that every two consecutive letters in the stringmust be different. There is a directed edge from a vertexv toanother vertexw if it is possible to transform the string ofv into the string ofw by removing the first letter andappending a letter to it. For string length 1 the new lettercannot equal the old letter, so there are no loops.

Kautz graphs have some interesting properties, see e.g. Wikipediafor 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 morelike O(|V|+|E|). |V| is the number of vertices, |E| is the numberof edges andm andn 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 graphG(n, shifts) consists ofn verticesv_0, ...,v_(n-1) such that for eachs_i in the list of offsetsshifts,v_j isconnected tov_((j + s_i) mod n) for all j.

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

Arguments: 

Returns: 

See also: 

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

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

The generalized Petersen graphG(n, k) consists ofn verticesv_0, ...,v_n forming an "outer" cycle graph, andn additional verticesu_0, ...,u_n forming an "inner" circulant graph whereu_iis connected tou_(i + k mod n). Additionally, allv_i areconnected tou_i.

G(n, k) has2n vertices and3n edges. The Petersen graphitself isG(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 chordsconnecting its vertices.Each rowL of the matrixW specifies a set of chords to beinserted, in the following way: vertexi will connect to a vertexL[(i mod p)] steps ahead of it along the cycle, wherep is the length ofL.In other words, vertexi will be connected to vertex(i + L[(i mod p)]) mod nodes. If multiple edges aredefined in this way, this will output a non-simple graph. The resultcan be simplified usingigraph_simplify().

See also Kotsis, G: Interconnection Topologies for Parallel ProcessingSystems, PARS Mitteilungen 11, 1-6, 1993. The igraph extended chordalrings are not identical to the ones in the paper. In igraphthe matrix specifies which edges to add. In the paper, a condition isspecified which should simultaneously hold between two endpoints andthe reverse endpoints.

Arguments: 

Returns: 

See also: 

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

2.1.igraph_grg_game — Generates a geometric random graph.

2.2.igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.

2.3.igraph_erdos_renyi_game_gnm — Generates a random (Erdős-Rényi) graph with a fixed number of edges.

2.4.igraph_erdos_renyi_game_gnp — Generates a random (Erdős-Rényi) graph with fixed edge probabilities.

2.5.igraph_watts_strogatz_game — The Watts-Strogatz small-world model.

2.6.igraph_rewire_edges — Rewires the edges of a graph with constant probability.

2.7.igraph_rewire_directed_edges — Rewires the chosen endpoint of directed edges.

2.8.igraph_degree_sequence_game — Generates a random graph with a given degree sequence.

2.9.igraph_k_regular_game — Generates a random graph where each vertex has the same degree.

2.10.igraph_static_fitness_game — Non-growing random graph with edge probabilities proportional to node fitness scores.

2.11.igraph_static_power_law_game — Generates a non-growing random graph with expected power-law degree distributions.

2.12.igraph_chung_lu_game — Samples graphs from the Chung-Lu model.

2.13.igraph_forest_fire_game — Generates a network according to the“forest fire game”.

2.14.igraph_rewire — Randomly rewires a graph while preserving its degree sequence.

2.15.igraph_growing_random_game — Generates a growing random graph.

2.16.igraph_callaway_traits_game — Simulates a growing network with vertex types.

2.17.igraph_establishment_game — Generates a graph with a simple growing model with vertex types.

2.18.igraph_preference_game — Generates a graph with vertex types and connection preferences.

2.19.igraph_asymmetric_preference_game — Generates a graph with asymmetric vertex types and connection preferences.

2.20.igraph_recent_degree_game — Stochastic graph generator based on the number of incident edges a node has gained recently.

2.21.igraph_barabasi_aging_game — Preferential attachment with aging of vertices.

2.22.igraph_recent_degree_aging_game — Preferential attachment based on the number of edges gained recently, with aging of vertices.

2.23.igraph_lastcit_game — Simulates a citation network, based on time passed since the last citation.

2.24.igraph_cited_type_game — Simulates a citation based on vertex types.

2.25.igraph_citing_cited_type_game — Simulates a citation network based on vertex types.

2.26.igraph_sbm_game — Sample from a stochastic block model.

2.27.igraph_hsbm_game — Hierarchical stochastic block model.

2.28.igraph_hsbm_list_game — Hierarchical stochastic block model, more general version.

2.29.igraph_dot_product_game — Generates a random dot product graph.

2.30.igraph_tree_game — Generates a random tree with the given number of nodes.

2.31.igraph_correlated_game — Generates a random graph correlated to an existing graph.

2.32.igraph_correlated_pair_game — Generates pairs of correlated random graphs.

2.33.igraph_simple_interconnected_islands_game — Generates a random graph made of several interconnected islands, each island being a random graph.

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 pairswhich are strictly less thanradius 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>intmain(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 attachmentprocess, including linear and non-linear varieties of the Barabási-Albertand Price models. The graph construction starts with a single vertex,or an existing graph given by thestart_from parameter. Then new verticesare added one at a time. Each new vertex connects tom existing vertices,choosing them with probabilities proportional to

d^power + A,

whered is the in- or total degree of the existing vertex (controlledby theoutpref argument), whilepower andA are given byparameters. Theconstant attractivenessAis used to ensure that vertices with zero in-degree can also beconnected to with non-zero probability.

Barabási, A.-L. and Albert R. 1999. Emergence of scaling inrandom 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|), thenumber of vertices plus the number of edges.

#include <igraph.h>intmain(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>intmain(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);

In theG(n, m) Erdős-Rényi model, a graph withn verticesandm edges is generated uniformly at random.

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>intmain(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    );/* 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 theG(n, p) Erdős-Rényi model, also known as the Gilbert model,or Bernoulli random graph, a graph withn vertices is generated such thatevery possible edge is included in the graph independently with probabilityp. This is equivalent to a maximum entropy random graph model model witha constraint on theexpected edge count. Settingp = 1/2generates all graphs onn vertices with the same probability.

The expected mean degree of the graph is approximatelyp n;setp = k/n when a mean degree of approximatelyk isdesired. More precisely, the expected mean degree isp(n-1)in (undirected or directed) graphs without self-loops,p(n+1) in undirected graphs with self-loops, andp n in directed graphs with self-loops.

Arguments: 

Returns: 

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

See also: 

#include <igraph.h>intmain(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 propertybased on a variant of the Watts-Strogatz model. The network is obtainedby first creating a periodic undirected lattice, then rewiring bothendpoints of each edge with probabilityp, while avoiding thecreation of multi-edges.

This process differs from the original model of Watts and Strogatz(see reference) in that it rewiresboth endpoints of edges. Thus inthe limit ofp=1, we obtain a G(n,m) random graph with thesame 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 forp=1.For appropriate choices ofp, both models exhibit the property ofsimultaneously 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 ofvertices and edges, d is the average degree, o is theneiargument.

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 constantprobability. More precisely each end point of each edge is rewiredto a uniformly randomly chosen vertex with constant probabilityprob.

Note that this function modifies the inputgraph,calligraph_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 graphwith a constant probability. Correspondingly, either the in-degree sequenceor the out-degree sequence of the graph will be preserved.

Note that this function modifies the inputgraph,calligraph_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_deg,        const igraph_vector_int_t *in_deg,        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 differenttradeoffs between performance and unbiased sampling. See Section 2.1 ofHorvát and Modes (2021) for an overview of sampling techniques for graphswith 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 edgesforIGRAPH_DEGSEQ_CONFIGURATION andIGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE.The time complexity of the other modes is not known.

See also: 

#include <igraph.h>intmain(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 thedegrees of vertices are equal to a predefined constant k. For undirectedgraphs, at least one of k and the number of vertices must be even.

Currently, this game simply usesigraph_degree_sequence_game withtheIGRAPH_DEGSEQ_CONFIGURATION or theIGRAPH_DEGSEQ_FAST_SIMPLEmethod and appropriately constructed degree sequences.Thefore, it does not sample uniformly: while it can generate all k-regulargraphs with the given number of vertices, it does not generate each one withthe same probability.

Arguments: 

Returns: 

Time complexity: O(|V|+|E|) ifmultiple 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 theprobability of an edge between verticesi andj depends on the fitnessscores of the two vertices involved. For undirected graphs, each vertexhas a single fitness score. For directed graphs, each vertex has an out-and an in-fitness, and the probability of an edge fromi toj depends onthe out-fitness of vertexi and the in-fitness of vertexj.

The generation process goes as follows. We start fromN disconnected nodes(whereN is given by the length of the fitness vector). Then we randomlyselect two verticesi andj, with probabilities proportional to theirfitnesses. (When the generated graph is directed,i is selected according tothe out-fitnesses andj is selected according to the in-fitnesses). If thevertices are not connected yet (or if multiple edges are allowed), weconnect them; otherwise we select a new pair. This is repeated until thedesired number of links are created.

Theexpected degree (though not the actual degree) of each vertex will beproportional to its fitness. This is exactly true when self-loops and multi-edgesare allowed, and approximately true otherwise. If you need to generate a graphwith an exact degree sequence, considerigraph_degree_sequence_game() andigraph_realize_degree_sequence() instead.

To generate random undirected graphs with a given expected degree sequence, setfitness_out (and in the directed casefitness_out) to the desired expecteddegrees, andno_of_edges to the corresponding edge count, i.e. half the sum ofexpected degrees in the undirected case, and the sum of out- or in-degrees in thedirected case.

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

This model is commonly used to generate static scale-free networks. Toachieve this, you have to draw the fitness scores from the desired power-lawdistribution. Alternatively, you may useigraph_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 distributionin scale-free networks. Phys Rev Lett 87(27):278701, 2001https://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 thedegrees of vertices follow power-law distributions with prescribedexponents. For directed graphs, the exponents of the in- and out-degreedistributions may be specified separately.

The game simply usesigraph_static_fitness_game() with appropriatelyconstructed fitness vectors. In particular, the fitness of vertexiisi^(-alpha), wherealpha = 1/(gamma-1)andgamma is the exponent given in the arguments.

To remove correlations between in- and out-degrees in case of directedgraphs, the in-fitness vector will be shuffled after it has been set upand beforeigraph_static_fitness_game() is called.

Note that significant finite size effects may be observed for exponentssmaller than 3 in the original formulation of the game. This functionprovides an argument that lets you remove the finite size effects byassuming that the fitness of vertexi is(i+i0-1)^(-alpha),wherei0 is a constant chosen appropriately to ensure that the maximumdegree is less than the square root of the number of edges times theaverage degree; see the paper of Chung and Lu, and Cho et al for moredetails.

References:

Goh K-I, Kahng B, Kim D: Universal behaviour of load distributionin 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 givendegree 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 inscale-free networks under the Achlioptas process. Phys Rev Lett103: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 fixedexpected degrees. This function implements both the original model of Chungand Lu, as well as some additional variants with useful properties.

In the original Chung-Lu model, each pair of verticesi andj isconnected with independent probabilityp_ij = w_i w_j / S,wherew_i is a weight associated with vertexi andS = 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 betweeni andj isp_ij = w^out_i w^in_j / S.

This model is commonly used to create random graphs with a fixedexpecteddegree sequence. The expected degree of vertexi is approximately equalto the weightw_i. Specifically, if the graph is directed and self-loopsare allowed, then the expected out- and in-degrees are preciselyw^out andw^in. If self-loops are disallowed,then the expected out- and in-degrees arew^out (S - w^in) / Sandw^in (S - w^out) / S, respectively. If the graph isundirected, then the expected degrees with and without self-loops arew (S + w) / S andw (S - w) / S, respectively.

A limitation of the original Chung-Lu model is that when some of theweights are large, the formula forp_ij yields values larger than 1.Chung and Lu's original paper excludes the use of such weights. Whenp_ij > 1, this function simply issues a warning and createsa connection betweeni andj. However, in this case the expected degreeswill no longer relate to the weights in the manner stated above. Thus theoriginal Chung-Lu model cannot produce certain (large) expected degrees.

The overcome this limitation, this function implements additional variants ofthe model, with modified expressions for the connection probabilityp_ijbetween verticesi andj. Letq_ij = w_i w_j / S, orq_ij = w^out_i w^in_j / S in the directed case. All modelvariants become equivalent in the limit of sparse graphs whereq_ijapproaches zero. In the original Chung-Lu model, selectable by settingvariant toIGRAPH_CHUNG_LU_ORIGINAL,p_ij = min(q_ij, 1).TheIGRAPH_CHUNG_LU_MAXENT variant, sometiems referred to a the generalizedrandom graph, usesp_ij = q_ij / (1 + q_ij), and is equivalentto a maximum entropy model (i.e. exponential random graph model) witha constraint on expected degrees; see Park and Newman (2004), Section B,settingexp(-Theta_ij) = w_i w_j / S. This model is alsodiscussed by Britton, Deijfen and Martin-Löf (2006). By virtue of beinga degree-constrained maximum entropy model, it produces graphs with thesame degree sequence with the same probability.A third variant can be requested withIGRAPH_CHUNG_LU_NR, and usesp_ij = 1 - exp(-q_ij). This is the underlying simple graphof a multigraph model introduced by Norros and Reittu (2006).For a discussion of these three model variants, see Section 16.4 ofBollobás, Janson, Riordan (2007), as well as Van Der Hofstad (2013).

References:

Chung F and Lu L: Connected components in a random graph with givendegree 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 networkcharacteristics, observed in real networks:

The network is generated in the following way. One vertex is added ata time. This vertex connects to (cites)ambs vertices alreadypresent in the network, chosen uniformly random. Now, for each citedvertexv 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 internationalconference on Knowledge discovery in data mining, 177--187, 2005.

Note however, that the version of the model in the published paper is incorrectin the sense that it cannot generate the kind of graphs the authorsclaim. A corrected version is available fromhttps://www.cs.cmu.edu/~jure/pubs/powergrowth-tkdd.pdf, ourimplementation is based on this.

Arguments: