Deterministic generators

Builds a graph from a flat vector of edge endpoints.

og_error_t og_create(
    og_t *graph,
    const og_vector_int_t *edges,
    og_int_t n,
    og_bool_t directed
);

The vector holds the edges as consecutive pairs: entries 2i and 2i+1 are the two endpoints of edge i, and the edges keep that order as their ids. The graph gets n vertices, or one more than the largest id in the vector when that is larger, so n = 0 lets the edges decide.

Self-loops and repeated pairs are kept as given. In an undirected graph each edge is stored with its smaller endpoint first.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• edges The endpoints, two per edge. Ids must not be negative.
• n The least number of vertices; raised to cover the largest id.
• directed OG_DIRECTED or OG_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL edges has an odd number of entries
• OG_EINVAL n is negative
• OG_EINVVID an id is negative or beyond the vertex limit
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 (python-igraph 1.0 on 200 seeded random graphs plus the edge cases: null graph, one vertex, isolated vertices, loops, multi-edges, both directions). 100k random edges build in about a third of python-igraph's time (which includes its list conversion).

C name

og_create

In notebooks

Og.Create

igraph 1.0

igraph_create

See also

small, empty, add_edges, adjacency, get_edgelist

og_t g;
og_vector_int_t edges;
og_vector_int_init_int(&edges, 6, 0, 1, 1, 2, 2, 0);  /* a triangle */
og_create(&g, &edges, 0, OG_UNDIRECTED);               /* n = 0: the ids decide */
printf("%" OG_PRId " vertices, %" OG_PRId " edges\n", og_vcount(&g), og_ecount(&g));
og_vector_int_destroy(&edges);
og_destroy(&g);

Builds a small graph from endpoints passed directly as int arguments.

og_error_t og_small(
    og_t *graph,
    og_int_t n,
    og_bool_t directed,
    int first,
    ...
);

A shorthand for create(): after the vertex count and the directedness come the endpoints as plain int arguments, two per edge, and -1 ends the list. The vertex count grows to cover the largest id, as in create().

The arguments are read as int, so pass literals or int variables, never og_int_t values: a 64-bit value in a variable argument list is read wrongly.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The least number of vertices.
• directed OG_DIRECTED or OG_UNDIRECTED.
• first The first endpoint (or -1 for a graph without edges).
• ... The remaining endpoints as int values, two per edge, then -1.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EINVAL an odd number of endpoints is given
• OG_EINVVID an id is negative (other than the closing -1)
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|).

Checked

No oracle exposes it; checked equal to create() on the same edges, errors included.

C name

og_small

igraph 1.0

igraph_small

See also

create

og_t g;
/* a bow tie: two triangles meeting at vertex 2 */
og_small(&g, 5, OG_UNDIRECTED, 0,2, 1,2, 0,1, 2,3, 2,4, 3,4, -1);
og_destroy(&g);

Builds a graph from a square matrix of edge counts.

og_error_t og_adjacency(
    og_t *graph,
    const og_matrix_t *adjmatrix,
    og_adjacency_t mode,
    og_loops_t loops
);

Entry (i, j) of the n x n matrix is the number of edges between vertex i and vertex j. Entries are truncated to whole numbers, NaN and infinite entries count as no edge, and negative entries are refused. OG_ADJ_DIRECTED gives a directed graph with A[i][j] edges i -> j. The other modes give undirected graphs: OG_ADJ_UNDIRECTED needs a symmetric matrix; OG_ADJ_UPPER and OG_ADJ_LOWER read only one triangle (diagonal included); OG_ADJ_MAX and OG_ADJ_MIN put max or min(A[i][j], A[j][i]) edges between i and j; OG_ADJ_PLUS puts A[i][j] + A[j][i].

On the diagonal, OG_NO_LOOPS ignores it, OG_LOOPS_ONCE makes A[i][i] self-loops, and OG_LOOPS_TWICE reads it as a degree contribution: A[i][i] / 2 loops in the modes that fold both triangles (UNDIRECTED, MAX, MIN, PLUS), A[i][i] loops in DIRECTED, UPPER and LOWER.

Edges come column by column for DIRECTED, PLUS, UPPER and LOWER, and row by row over the pairs i <= j for UNDIRECTED, MAX and MIN; this is python-igraph 1.0's order.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• adjmatrix The n x n matrix of edge counts.
• mode How the matrix is read: OG_ADJ_DIRECTED, OG_ADJ_UNDIRECTED, OG_ADJ_UPPER, OG_ADJ_LOWER, OG_ADJ_MAX, OG_ADJ_MIN or OG_ADJ_PLUS (see the description).
• loops What the diagonal means: OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE (= OG_LOOPS).

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL mode or loops is not a known value
• OG_EINVAL the matrix is not square
• OG_EINVAL an entry is negative
• OG_EINVAL OG_ADJ_UNDIRECTED is given a matrix that is not symmetric
• OG_EINVAL OG_LOOPS_TWICE in a folding mode meets an odd diagonal entry
• OG_EOVERFLOW the matrix asks for more edges than the library can hold
• OG_ENOMEM there is not enough memory

Complexity

O(n^2 + |E|).

Checked

Identical to igraph 1.0, edge order included: 896 cases over all 7 modes and 3 loop modes, random matrices up to 45 x 45 with fractional, NaN, infinite and odd diagonal entries, and the error cases.

C name

og_adjacency

In notebooks

Og.Adjacency

igraph 1.0

igraph_adjacency

See also

weighted_adjacency, sparse_adjacency, adjlist, get_adjacency, create

og_t g;
og_matrix_t A;
og_matrix_init(&A, 3, 3);                      /* all zeros */
OG_MATRIX(A, 0, 1) = OG_MATRIX(A, 1, 0) = 1;
OG_MATRIX(A, 1, 2) = OG_MATRIX(A, 2, 1) = 2;   /* two parallel edges 1-2 */
og_adjacency(&g, &A, OG_ADJ_UNDIRECTED, OG_NO_LOOPS);  /* 3 edges */
og_matrix_destroy(&A);
og_destroy(&g);

Builds a weighted graph from a square matrix, one edge per non-zero entry.

og_error_t og_weighted_adjacency(
    og_t *graph,
    const og_matrix_t *adjmatrix,
    og_adjacency_t mode,
    og_vector_t *weights,
    og_loops_t loops
);

Each non-zero entry gives one edge whose weight is the entry; zero means no edge. Negative weights are allowed, and NaN counts as an edge of weight NaN. The modes read the matrix as adjacency() does, with weights in place of counts and at most one edge per vertex pair: OG_ADJ_UNDIRECTED needs a symmetric matrix (NaN opposite NaN is accepted), OG_ADJ_MAX and OG_ADJ_MIN keep the larger or smaller of the two entries (NaN if either is NaN), and OG_ADJ_PLUS their sum.

On the diagonal, OG_NO_LOOPS ignores the entries, OG_LOOPS_ONCE makes a loop of weight A[i][i], and OG_LOOPS_TWICE halves that weight in the folding modes (UNDIRECTED, MAX, MIN, PLUS). Edges come column by column for DIRECTED, UNDIRECTED, UPPER and LOWER and row by row for MAX, MIN and PLUS, as in python-igraph 1.0.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• adjmatrix The n x n matrix of weights.
• mode How the matrix is read: OG_ADJ_DIRECTED, OG_ADJ_UNDIRECTED, OG_ADJ_UPPER, OG_ADJ_LOWER, OG_ADJ_MAX, OG_ADJ_MIN or OG_ADJ_PLUS (see the description).
• weights Output, may be NULL: resized to the edge count and filled with the weights in edge-id order.
• loops What the diagonal means: OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE (= OG_LOOPS).

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL mode or loops is not a known value
• OG_EINVAL the matrix is not square
• OG_EINVAL OG_ADJ_UNDIRECTED is given a matrix that is not symmetric
• OG_EOVERFLOW the edge count exceeds the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n^2).

Checked

Identical to igraph 1.0: edges, order and weights, on fixtures with negative, zero, NaN and infinite entries in every mode.

C name

og_weighted_adjacency

In notebooks

Og.WeightedAdjacency

igraph 1.0

igraph_weighted_adjacency

See also

adjacency, sparse_weighted_adjacency, get_adjacency

Turns a sparse matrix of edge counts into a graph.

og_error_t og_sparse_adjacency(
    og_t *graph,
    og_sparsemat_t *adjmatrix,
    og_adjacency_t mode,
    og_loops_t loops
);

Reads an sparsemat_t, in triplet or column-compressed form, exactly as adjacency() reads a dense matrix. Entries that are not stored are zero, and repeated positions of a triplet matrix are added together. The edges come in the order the dense function gives for the same matrix.

The work is linear in the stored entries, so a large sparse matrix never costs n^2.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• adjmatrix The n x n sparse matrix of edge counts (triplet or compressed).
• mode How the matrix is read: OG_ADJ_DIRECTED, OG_ADJ_UNDIRECTED, OG_ADJ_UPPER, OG_ADJ_LOWER, OG_ADJ_MAX, OG_ADJ_MIN or OG_ADJ_PLUS (see the description).
• loops What the diagonal means: OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE (= OG_LOOPS).

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL mode or loops is not a known value
• OG_EINVAL the matrix is not square, or an entry lies outside it
• OG_EINVAL an entry is negative
• OG_EINVAL OG_ADJ_UNDIRECTED is given a matrix that is not symmetric
• OG_EINVAL OG_LOOPS_TWICE in a folding mode meets an odd diagonal entry
• OG_EOVERFLOW the matrix asks for more edges than the library can hold
• OG_ENOMEM there is not enough memory

Complexity

O(n + nnz + |E|), nnz the stored entries.

Checked

Equal to adjacency() on every dense fixture case, in both storage forms (and on 60 random matrices x 7 modes x 3 loop modes). igraph's own order for sparse input could not be observed (python-igraph converts sparse matrices in Python), so the dense order is used.

C name

og_sparse_adjacency

In notebooks

Og.SparseAdjacency

igraph 1.0

igraph_sparse_adjacency

See also

adjacency, sparse_weighted_adjacency, sparsemat_init, get_adjacency_sparse

Builds a weighted graph from a sparse matrix, one edge per non-zero entry.

og_error_t og_sparse_weighted_adjacency(
    og_t *graph,
    og_sparsemat_t *adjmatrix,
    og_adjacency_t mode,
    og_vector_t *weights,
    og_loops_t loops
);

Reads an sparsemat_t, in triplet or column-compressed form, exactly as weighted_adjacency() reads a dense matrix. Entries that are not stored are zero and repeated positions of a triplet matrix are added together; an entry that adds up to zero makes no edge. The edges and weights come in the dense function's order.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• adjmatrix The n x n sparse matrix of weights (triplet or compressed).
• mode How the matrix is read: OG_ADJ_DIRECTED, OG_ADJ_UNDIRECTED, OG_ADJ_UPPER, OG_ADJ_LOWER, OG_ADJ_MAX, OG_ADJ_MIN or OG_ADJ_PLUS (see the description).
• weights Output, may be NULL: resized to the edge count and filled with the weights in edge-id order.
• loops What the diagonal means: OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE (= OG_LOOPS).

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL mode or loops is not a known value
• OG_EINVAL the matrix is not square, or an entry lies outside it
• OG_EINVAL OG_ADJ_UNDIRECTED is given a matrix that is not symmetric
• OG_EOVERFLOW the edge count exceeds the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n + nnz + |E|), nnz the stored entries.

Checked

Equal to weighted_adjacency() (edges and weights) on every dense fixture case, in both storage forms.

C name

og_sparse_weighted_adjacency

In notebooks

Og.SparseWeightedAdjacency

igraph 1.0

igraph_sparse_weighted_adjacency

See also

weighted_adjacency, sparse_adjacency, sparsemat_init

Turns an adjacency list, one neighbour list per vertex, into a graph.

og_error_t og_adjlist(
    og_t *graph,
    const og_adjlist_t *adjlist,
    og_neimode_t mode,
    og_bool_t duplicate
);

List i holds the neighbours of vertex i, and the number of lists is the vertex count. With OG_OUT each entry j in list i is an edge i -> j, with OG_IN an edge j -> i; both give directed graphs. OG_ALL gives an undirected graph.

With OG_ALL, duplicate says whether each edge is listed at both of its ends. When true an edge is taken once, from the list of its smaller end, and a self-loop (which its vertex lists twice) once per two sightings; when false every entry becomes an edge. duplicate has no effect with OG_OUT and OG_IN. Edges come vertex by vertex in list order.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• adjlist The adjacency list (containers area); it is not changed.
• mode OG_OUT, OG_IN or OG_ALL (see the description).
• duplicate OG_ALL only: true when every undirected edge appears in both lists.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL
• OG_EINVVID a list holds an id that is not a vertex
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|).

Checked

No oracle exposes it: tested on 240 random graphs (out, in and duplicated undirected lists, loops, multi-edges) and on its errors.

C name

og_adjlist

In notebooks

Og.Adjlist

igraph 1.0

igraph_adjlist

See also

adjlist_init, create, adjacency

Turns a vector of parent ids into a tree or forest.

og_error_t og_tree_from_parent_vector(
    og_t *graph,
    const og_vector_int_t *parents,
    og_tree_mode_t type
);

parents[v] is the parent of vertex v, or a negative value when v is a root, so forests with several roots are allowed. Each vertex that has a parent gives one edge, oriented by type. A parent vector that leads back to a vertex already on the way is refused.

Edge order: vertices are visited in id order and each climbs towards its root, adding the edge to each parent on the way until it reaches a root or a vertex an earlier climb passed. This is igraph 1.0's order.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• parents parents[v] is v's parent id, negative for a root; its length is the vertex count.
• type OG_TREE_OUT (edges from parent to child), OG_TREE_IN (child to parent) or OG_TREE_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVMODE type is not a known value
• OG_EINVVID a parent id is not a vertex
• OG_EINVAL a vertex is its own parent
• OG_EINVAL the parent vector contains a cycle
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Identical to igraph 1.0.1's C library on 15 recorded cases (forests with several roots, all types, chains climbing through higher ids, cycle and self-loop errors) plus 240 random forests and cycles checked against the definition.

C name

og_tree_from_parent_vector

In notebooks

Og.TreeFromParentVector

igraph 1.0

igraph_tree_from_parent_vector

See also

kary_tree, from_prufer, is_tree

Builds the labelled tree that a Prüfer sequence encodes.

og_error_t og_from_prufer(og_t *graph, const og_vector_int_t *prufer);

A sequence of length L with entries in 0..L+1 encodes exactly one tree on L + 2 labelled vertices. Decoding repeatedly joins the smallest current leaf to the next entry and removes the leaf; the last edge joins the remaining leaf to vertex L + 1. The tree is undirected and its edges come in decoding order.

The decoding is linear: a pointer moves up through the ids to find the smallest leaf, and a vertex that becomes a leaf below the pointer is used at once (Micikevicius, Caminiti and Deo).

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• prufer The sequence; entries must lie in 0..L+1 for a sequence of length L.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL an entry is out of range
• OG_EOVERFLOW the sequence is too long
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Identical to igraph 1.0 on 220 random sequences (lengths 0..18, some out of range) and 30 sequences of 1,000-20,000 entries.

C name

og_from_prufer

In notebooks

Og.FromPrufer

igraph 1.0

igraph_from_prufer

See also

to_prufer, tree_game, tree_from_parent_vector

Builds a star: one center vertex joined to every other vertex.

og_error_t og_star(
    og_t *graph,
    og_int_t n,
    og_star_mode_t mode,
    og_int_t center
);

Vertex center is joined to each of the other n - 1 vertices. OG_STAR_OUT points the edges away from the center, OG_STAR_IN towards it, OG_STAR_MUTUAL gives both directions (center -> i, then i -> center), and OG_STAR_UNDIRECTED an undirected star. Edges are listed by the other vertex, in increasing order.

n = 1 gives a single vertex (igraph 1.0 gives the null graph there). The center must be a vertex, so n = 0 is an error.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• mode OG_STAR_OUT (edges from the center), OG_STAR_IN (towards it), OG_STAR_MUTUAL (both) or OG_STAR_UNDIRECTED.
• center The id of the center, 0 <= center < n.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVVID n is negative (the code the reference gives)
• OG_EINVAL center is not a vertex (always so for n = 0)
• OG_EINVMODE mode is not a known value
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Identical to igraph 1.0 for every mode and center on n = 0 and 2..8, error codes included. Divergence: n = 1 gives one vertex, igraph 1.0 the null graph.

C name

og_star

In notebooks

Og.Star

igraph 1.0

igraph_star

See also

wheel, ring, full

Builds a wheel: a star whose outer vertices also form a cycle.

og_error_t og_wheel(
    og_t *graph,
    og_int_t n,
    og_wheel_mode_t mode,
    og_int_t center
);

The spokes are those of star() with the same mode (OG_WHEEL_OUT, OG_WHEEL_IN, OG_WHEEL_MUTUAL, OG_WHEEL_UNDIRECTED). The rim is the cycle through the other vertices in increasing id order, pointing forwards in the directed modes; OG_WHEEL_MUTUAL adds the reverse cycle after it. Spokes are listed first, then the rim.

For n = 2 the rim is a self-loop and for n = 3 a doubled edge, so the result is not simple, as in igraph. n = 1 gives a single vertex (igraph 1.0: the null graph).

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• mode OG_WHEEL_OUT, OG_WHEEL_IN, OG_WHEEL_MUTUAL or OG_WHEEL_UNDIRECTED; the spokes as in star().
• center The id of the hub, 0 <= center < n.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVVID n is negative
• OG_EINVAL center is not a vertex (always so for n = 0)
• OG_EINVMODE mode is not a known value
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Identical to igraph 1.0.1's C library on 18 recorded cases (all modes, several centers, the non-simple n = 2 and 3) plus 240 random parameter sets checked against the definition. Divergence: n = 1, as for star().

C name

og_wheel

In notebooks

Og.Wheel

igraph 1.0

igraph_wheel

See also

star, ring

Builds the hypercube of dimension n: 2^n vertices, one per n-bit number.

og_error_t og_hypercube(og_t *graph, og_int_t n, og_bool_t directed);

The 2^n vertices are the n-bit numbers, and two vertices are adjacent when their ids differ in exactly one bit, so every vertex has degree n. In a directed graph each edge points from the smaller id to the larger. Edges are listed by the smaller endpoint, then by bit position.

n may be at most 57, the largest dimension whose edge count fits the library's limits.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The dimension, 0..57.
• directed OG_DIRECTED (edges from smaller to larger id) or OG_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative or above 57
• OG_ENOMEM there is not enough memory

Complexity

O(n 2^n) = O(|E|).

Checked

Identical to igraph 1.0 for n = 0..8 in both directions; n = 58 is EINVAL as in the reference.

C name

og_hypercube

In notebooks

Og.Hypercube

igraph 1.0

igraph_hypercube

See also

square_lattice, full

Builds a square grid lattice in any number of dimensions, optionally periodic.

og_error_t og_square_lattice(
    og_t *graph,
    const og_vector_int_t *dimvector,
    og_int_t nei,
    og_bool_t directed,
    og_bool_t mutual,
    const og_vector_bool_t *periodic
);

dimvector gives the size along each dimension, and the vertex count is their product. Ids run with the first dimension fastest: coordinates (c0, c1, c2, ...) have id c0 + s0 c1 + s0 s1 c2 + ... Each vertex is joined to its successor along every dimension; periodic (one flag per dimension, NULL for none) closes a dimension into a ring. A periodic dimension of size 2 adds no second edge unless the graph is directed and not mutual, and one of size 1 adds nothing.

In a directed lattice edges point towards the larger coordinate, and mutual adds each reverse edge. With nei >= 2 every vertex is also joined to all vertices within nei steps, from the smaller id to the larger; these edges follow the lattice edges, vertex by vertex in breadth-first order.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• dimvector The size along each dimension; a zero size gives the null graph.
• nei 1 (or less) for the plain lattice; k >= 2 also joins vertices up to k steps apart.
• directed OG_DIRECTED or OG_UNDIRECTED.
• mutual Directed lattices only: add every edge in both directions.
• periodic NULL, or one flag per dimension: true closes that dimension into a ring.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL periodic does not have one entry per dimension
• OG_EINVAL a size is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(|V| d + |E|) for nei <= 1 (d dimensions); with nei >= 2 a bounded breadth-first search from every vertex is added.

Checked

Identical to igraph 1.0, edge order included: 260 random shapes (0-3 dimensions, zero sizes, nei 1-3, directed and mutual, periodicity with sizes 1 and 2) and 40 larger ones of up to 2,500 vertices. A 300 x 300 lattice builds in 0.9x python-igraph's time.

C name

og_square_lattice

In notebooks

Og.SquareLattice

igraph 1.0

igraph_square_lattice

See also

triangular_lattice, hexagonal_lattice, ring, hypercube, watts_strogatz_game, connect_neighborhood

og_t g;
og_vector_int_t dims;
og_vector_bool_t periodic;
og_vector_int_init_int(&dims, 2, 10, 20);  /* 10 x 20 grid, 200 vertices */
og_vector_bool_init(&periodic, 2);
og_vector_bool_fill(&periodic, true);      /* wrap both ways: a torus */
og_square_lattice(&g, &dims, 1, OG_UNDIRECTED, false, &periodic);  /* 400 edges */
og_vector_bool_destroy(&periodic);
og_vector_int_destroy(&dims);
og_destroy(&g);

Builds a lattice of triangles in one of three outlines.

og_error_t og_triangular_lattice(
    og_t *graph,
    const og_vector_int_t *dims,
    og_bool_t directed,
    og_bool_t mutual
);

Each grid point gets three edges of its own: one step forward in the first coordinate, one step forward in the second, and the diagonal that steps back in the first while stepping forward in the second. Counting the edges other points send to it, an inner point ends up with six neighbours. dims chooses the outline: one size s gives a triangle with s points per side; two sizes (r, c) give r rows of c points, alternately shifted so that the outline stays roughly rectangular; three sizes (a, b, c) give a hexagonal outline with sides of a, b and c points. A zero size gives the null graph.

Vertices are numbered row by row. In a directed lattice every edge points from the smaller id to the larger, and mutual adds each reverse edge right after it.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• dims 1, 2 or 3 sizes choosing the outline: a triangle, a roughly rectangular patch, or a hexagon (see the description).
• directed OG_DIRECTED or OG_UNDIRECTED.
• mutual Directed lattices only: add every edge in both directions.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL dims has fewer than 1 or more than 3 entries
• OG_EINVAL a size is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory (also for outlines too large to lay out)

Complexity

O(|V| + |E| + rows).

Checked

Identical to igraph 1.0, edge order included, for every outline with 1-3 sizes up to 5 and 26 larger ones (sides up to 120) in all three orientations; oversize shapes give the reference's ENOMEM or EOVERFLOW.

C name

og_triangular_lattice

In notebooks

Og.TriangularLattice

igraph 1.0

igraph_triangular_lattice

See also

hexagonal_lattice, square_lattice

Builds a honeycomb lattice of hexagons in one of three outlines.

og_error_t og_hexagonal_lattice(
    og_t *graph,
    const og_vector_int_t *dims,
    og_bool_t directed,
    og_bool_t mutual
);

dims counts hexagons and takes the same three forms as in triangular_lattice(): one size for a triangle of hexagons, two for a roughly rectangular patch, three for a hexagonal outline. The hexagons sit where the triangular lattice with the same dims has its points (the two lattices are planar duals), and every vertex has degree 2 or 3.

Vertices are numbered row by row. In a directed lattice every edge points from the smaller id to the larger, and mutual adds each reverse edge right after it.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• dims 1, 2 or 3 sizes, in hexagons, as for triangular_lattice().
• directed OG_DIRECTED or OG_UNDIRECTED.
• mutual Directed lattices only: add every edge in both directions.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL dims has fewer than 1 or more than 3 entries
• OG_EINVAL a size is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory (also for outlines too large to lay out)

Complexity

O(|V| + |E| + rows).

Checked

Identical to igraph 1.0, edge order included, on the same outlines as triangular_lattice() (26 larger ones with sides up to 120, all three orientations).

C name

og_hexagonal_lattice

In notebooks

Og.HexagonalLattice

igraph 1.0

igraph_hexagonal_lattice

See also

triangular_lattice, square_lattice

Builds a path or a cycle on n vertices.

og_error_t og_ring(
    og_t *graph,
    og_int_t n,
    og_bool_t directed,
    og_bool_t mutual,
    og_bool_t circular
);

Vertex i is joined to i+1 for i = 0..n-2, and with circular also n-1 to 0. Directed edges point forwards; mutual adds each reverse edge right after its forward edge.

With circular, n = 1 gives a self-loop and n = 2 two edges between the vertices, as in igraph.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• directed OG_DIRECTED or OG_UNDIRECTED.
• mutual Directed graphs only: add every edge in both directions.
• circular true for a cycle, false for a path.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Identical to igraph 1.0 for n = 0..8 and every combination of directed, mutual and circular. 100,000 vertices build in 0.6x python-igraph's time.

C name

og_ring

In notebooks

Og.Ring

igraph 1.0

igraph_ring

See also

path_graph, cycle_graph, star, square_lattice, circulant

og_t g;
og_ring(&g, 10, OG_UNDIRECTED, false, true);  /* the cycle C10 */
og_destroy(&g);

Builds the path on n vertices.

og_error_t og_path_graph(
    og_t *graph,
    og_int_t n,
    og_bool_t directed,
    og_bool_t mutual
);

Vertices 0..n-1 joined in order: ring() with circular false. Directed edges point from i to i+1; mutual adds each reverse edge.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• directed OG_DIRECTED or OG_UNDIRECTED.
• mutual Directed graphs only: add every edge in both directions.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Calls ring(); identical to igraph 1.0 on every ring case.

C name

og_path_graph

In notebooks

Og.PathGraph

igraph 1.0

igraph_path_graph

See also

ring, cycle_graph

Builds the cycle on n vertices.

og_error_t og_cycle_graph(
    og_t *graph,
    og_int_t n,
    og_bool_t directed,
    og_bool_t mutual
);

Vertices 0..n-1 joined in order and n-1 joined back to 0: ring() with circular true. n = 1 gives a self-loop and n = 2 a doubled edge.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• directed OG_DIRECTED or OG_UNDIRECTED.
• mutual Directed graphs only: add every edge in both directions.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Calls ring(); identical to igraph 1.0 on every ring case.

C name

og_cycle_graph

In notebooks

Og.CycleGraph

igraph 1.0

igraph_cycle_graph

See also

ring, path_graph

Builds a graph from its LCF notation: a Hamiltonian cycle plus chords.

og_error_t og_lcf(
    og_t *graph,
    og_int_t n,
    const og_vector_int_t *shifts,
    og_int_t repeats
);

LCF notation (after Lederberg, Coxeter and Frucht) describes a graph as the cycle 0, 1, ..., n-1 plus chords. The shifts are applied to vertices 0, 1, 2, ... in turn, the whole list repeats times, and shift s at vertex p adds the chord from p to (p + s) mod n; vertex positions wrap around modulo n.

The result is simple and undirected: self-loops and chords that repeat an edge are dropped, and the edges come sorted by smaller endpoint, then larger. A shift below -n can reach a negative id, which is reported as an invalid vertex, as in igraph.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• shifts The chord offsets, applied to consecutive vertices.
• repeats How many times the shift list is applied.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n or repeats is negative
• OG_EINVVID a shift below -n leads to a negative id
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n + k r), k shifts applied r times.

Checked

Identical to igraph 1.0 on 252 random cases (shifts -12..12, repeats 0..6, n 0..24), the Heawood graph, and 40 larger cases with n up to 5,000, invalid-vertex errors included.

C name

og_lcf

In notebooks

Og.Lcf

igraph 1.0

igraph_lcf

See also

lcf_small, circulant, extended_chordal_ring, famous

LCF notation with the shifts and the repeat count passed as int arguments.

og_error_t og_lcf_small(og_t *graph, og_int_t n, ...);

Same as lcf(): after n come the shifts as int values, then the repeat count, then 0 to end the list. lcf_small(&g, 14, 5, -5, 7, 0) gives the Heawood graph. A shift of 0 cannot be written this way, since 0 ends the list (it would only add a self-loop, which is dropped anyway).

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• ... int values: the shifts, then the repeat count, then 0.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n or the repeat count is negative
• OG_EINVVID a shift below -n leads to a negative id
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n + k r), k shifts applied r times.

Checked

Equal to lcf() (which is exact) on the same input.

C name

og_lcf_small

igraph 1.0

igraph_lcf_small

See also

lcf

Builds a circulant graph: every vertex joined to the vertices a fixed set of offsets away.

og_error_t og_circulant(
    og_t *graph,
    og_int_t n,
    const og_vector_int_t *shifts,
    og_bool_t directed
);

For each shift s, every vertex j is joined to (j + s) mod n. Shifts are taken modulo n, and zero shifts and shifts that repeat an edge set already added are skipped, so the graph has no self-loops and no multi-edges. In an undirected graph s and n - s give the same edges, and when 2s = n each such edge appears once.

Edges come shift by shift in the order of the shifts vector, and within a shift by j.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• shifts The offsets; any integers (negative and beyond n allowed).
• directed OG_DIRECTED (j -> j + s) or OG_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n k + |shifts|), k the number of distinct shifts.

Checked

Identical to igraph 1.0.1's C library on 13 recorded cases (duplicate, zero, negative, larger than n and n/2 shifts, both directions) plus 240 random parameter sets checked against the definition.

C name

og_circulant

In notebooks

Og.Circulant

igraph 1.0

igraph_circulant

See also

ring, lcf, extended_chordal_ring

Builds an extended chordal ring: a cycle plus chords from a periodic offset table.

og_error_t og_extended_chordal_ring(
    og_t *graph,
    og_int_t nodes,
    const og_matrix_int_t *W,
    og_bool_t directed
);

The vertices 0..nodes-1 form a cycle. W has p columns, and p must divide nodes; for each vertex i and each row r of W a chord joins i to (i + W[r][i mod p]) mod nodes (Kotsis 1993). Offsets may be negative or larger than nodes. Chords are kept as they come: an offset of 0 gives a self-loop, and an offset of +-1 or a repeated one a multi-edge.

The cycle edges are listed first, then the chords vertex by vertex, row by row. A W without rows gives the plain cycle.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• nodes The number of vertices, at least 3.
• W The offset table; its column count must divide nodes.
• directed OG_DIRECTED (edges i -> target) or OG_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL nodes is below 3
• OG_EINVAL W has rows and its column count does not divide nodes
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(nodes (rows + 1)).

Checked

Identical to igraph 1.0.1's C library on 10 recorded cases (negative and beyond-n offsets, several rows, directed) plus 240 random tables checked against the definition.

C name

og_extended_chordal_ring

In notebooks

Og.ExtendedChordalRing

igraph 1.0

igraph_extended_chordal_ring

See also

ring, circulant, lcf

Builds the complete graph on n vertices.

og_error_t og_full(
    og_t *graph,
    og_int_t n,
    og_bool_t directed,
    og_bool_t loops
);

Every pair of distinct vertices is joined, in a directed graph in both directions. With loops every vertex also gets one self-loop. Edges are listed by first endpoint, then second (undirected: the pairs i <= j).

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• directed OG_DIRECTED or OG_UNDIRECTED.
• loops true to add one self-loop at every vertex.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n^2).

Checked

Identical to igraph 1.0 for n = 0..8, both directions, with and without loops. About 100k edges build in 0.9-0.95x python-igraph's time.

C name

og_full

In notebooks

Og.Full

igraph 1.0

igraph_full

See also

full_citation, full_multipartite, turan, star

og_t g;
og_full(&g, 5, OG_UNDIRECTED, false);  /* K5: 10 edges */
og_destroy(&g);

Builds the complete citation graph: every vertex points to all earlier vertices.

og_error_t og_full_citation(og_t *graph, og_int_t n, og_bool_t directed);

Vertex i has an edge to every j < i, listed by i, then j. Undirected, this is the complete graph with another edge order.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• directed OG_DIRECTED (i -> j for j < i) or OG_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n^2).

Checked

Identical to igraph 1.0 for n = 0..8, both directions.

C name

og_full_citation

In notebooks

Og.FullCitation

igraph 1.0

igraph_full_citation

See also

full, barabasi_game

Builds the complete multipartite graph for given part sizes.

og_error_t og_full_multipartite(
    og_t *graph,
    og_vector_int_t *types,
    const og_vector_int_t *n,
    og_bool_t directed,
    og_neimode_t mode
);

n[p] is the size of part p, and the parts get consecutive ids in order. Every two vertices in different parts are joined, none inside a part. In a directed graph mode sets the direction: OG_OUT from the earlier part to the later, OG_IN the reverse, OG_ALL both. Edges are listed vertex by vertex, to every vertex of the later parts.

types (may be NULL) receives each vertex's part index. With empty parts igraph 1.0.1 numbers types differently (the graphs are the same); Open Graph always stores the part index.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• types Output, may be NULL: resized to the vertex count, the part of each vertex.
• n The part sizes; zeros allowed.
• directed OG_DIRECTED or OG_UNDIRECTED.
• mode Directed graphs only: OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVMODE the graph is directed and mode is not OG_OUT, OG_IN or OG_ALL
• OG_EINVAL a part size is negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|).

Checked

Graphs identical to igraph 1.0.1's C library on 4 recorded cases (all modes) plus 240 random partitions, empty parts included, checked against the definition. Divergence: the types vector when a part is empty (see above).

C name

og_full_multipartite

In notebooks

Og.FullMultipartite

igraph 1.0

igraph_full_multipartite

See also

turan, full, full_bipartite

Builds the Turán graph T(n, r): the complete r-partite graph with parts as equal as possible.

og_error_t og_turan(
    og_t *graph,
    og_vector_int_t *types,
    og_int_t n,
    og_int_t r
);

The n vertices are split into r parts whose sizes differ by at most one, the larger parts first, and every pair in different parts is joined (full_multipartite(), undirected). When r exceeds n every vertex is its own part, giving the complete graph. By Turán's theorem T(n, r) has the most edges among graphs on n vertices without r + 1 mutually adjacent vertices.

types (may be NULL) receives each vertex's part.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• types Output, may be NULL: resized to n, the part of each vertex.
• n The number of vertices.
• r The number of parts, at least 1.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EINVAL r is 0 or negative
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0.1's C library on 9 recorded cases plus 240 random (n, r) checked for balanced parts and completeness between them.

C name

og_turan

In notebooks

Og.Turan

igraph 1.0

igraph_turan

See also

full_multipartite, full

Builds the de Bruijn graph of strings of length n over m letters.

og_error_t og_de_bruijn(og_t *graph, og_int_t m, og_int_t n);

Each vertex is a string of n letters from an alphabet of m, read as a base-m number, so there are m^n vertices. The string s1 s2 ... sn has an edge to every s2 ... sn a, one per letter a: m out-edges and m in-edges per vertex, and a self-loop at each string of one repeated letter. The graph is directed; edges are listed by source, then letter.

n = 0 gives one vertex (the empty string), and m = 0 with n > 0 the null graph.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• m The alphabet size.
• n The string length.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL m or n is negative
• OG_EINVAL m^n exceeds the vertex limit
• OG_EOVERFLOW the edge count exceeds the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|) = O(m^(n+1)).

Checked

Identical to igraph 1.0 for every (m, n) with m^n <= 300, three too-large cases, and 11 graphs of up to 90,000 edges.

C name

og_de_bruijn

In notebooks

Og.DeBruijn

igraph 1.0

igraph_de_bruijn

See also

kautz, linegraph

Builds the Kautz graph: strings of length n+1 over m+1 letters with no letter repeated in a row.

og_error_t og_kautz(og_t *graph, og_int_t m, og_int_t n);

Vertices are the strings s0 s1 ... sn over an alphabet of m + 1 letters in which neighbouring letters differ, numbered in lexicographic order; there are (m+1) m^n of them. s0 s1 ... sn has an edge to every s1 ... sn a with a != sn, so each vertex has m out-edges and m in-edges and there are no self-loops. The graph is directed. n = 0 gives the complete directed graph on m + 1 vertices.

m = 0 gives one vertex for n = 0 and the null graph otherwise. Parameters are refused when (m+1)^(n+1) does not fit in 64 bits, as in igraph.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• m One less than the alphabet size.
• n One less than the string length.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL m or n is negative
• OG_EINVAL m^n or (m+1)^(n+1) does not fit in 64 bits
• OG_EOVERFLOW the vertex or edge count exceeds the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 for every (m, n) with (m+1) m^n <= 400, three too-large cases, and 9 graphs of up to 93,000 edges. Kautz(1, 40) is left out of the comparison: the reference runs out of memory there, Open Graph returns the 2-vertex graph.

C name

og_kautz

In notebooks

Og.Kautz

igraph 1.0

igraph_kautz

See also

de_bruijn, linegraph

Builds the generalized Petersen graph GP(n, k).

og_error_t og_generalized_petersen(og_t *graph, og_int_t n, og_int_t k);

Vertices 0..n-1 form an outer cycle, vertices n..2n-1 an inner star polygon in which n+i is joined to n + (i+k) mod n, and spokes join i to n+i (Watkins 1969). The graph is undirected and cubic, with 3n edges; GP(5, 2) is the Petersen graph. Edges are listed per i: outer edge, spoke, inner edge.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The size of each cycle, at least 3.
• k The inner step, 0 < k < n/2.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is below 3
• OG_EINVAL k is not in 1..(n-1)/2
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Identical to igraph 1.0.1's C library on 7 recorded cases (n 3..9, k up to 4) and its errors, plus 240 random (n, k) checked against the definition.

C name

og_generalized_petersen

In notebooks

Og.GeneralizedPetersen

igraph 1.0

igraph_generalized_petersen

See also

famous, circulant

Builds Mycielski's triangle-free graph M_k, whose chromatic number is k.

og_error_t og_mycielski_graph(og_t *graph, og_int_t k);

Order 0 is the null graph, 1 a single vertex and 2 a single edge; each further order applies the Mycielski construction (mycielskian()) to the previous graph, so order 3 is the 5-cycle and order 4 the Grötzsch graph. From order 2 on there are 3 2^(k-2) - 1 vertices, and one order up turns n vertices and m edges into 2n + 1 and 3m + n. Each graph lists the previous order's edges first. Undirected.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• k The order, 0 or more.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL k is negative
• OG_EOVERFLOW the graph would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|) of the result.

Checked

Identical to igraph 1.0.1's C library for k = 0..6; vertex and edge counts checked for k up to 11 and the graphs triangle-free up to k = 7.

C name

og_mycielski_graph

In notebooks

Og.MycielskiGraph

igraph 1.0

igraph_mycielski_graph

See also

mycielskian, famous

Builds a tree in which every vertex has up to k children, numbered breadth first.

og_error_t og_kary_tree(
    og_t *graph,
    og_int_t n,
    og_int_t children,
    og_tree_mode_t type
);

Vertex 0 is the root and the children of vertex v are kv + 1, ..., kv + k, so the parent of c is (c - 1) / k; the last level may be incomplete. Edges are listed by child id and oriented by type.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• n The number of vertices.
• children k, the most children a vertex has (at least 1).
• type OG_TREE_OUT (edges from parent to child), OG_TREE_IN (child to parent) or OG_TREE_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL n is negative
• OG_EINVAL children is 0 or negative
• OG_EINVMODE type is not a known value
• OG_ENOMEM there is not enough memory

Complexity

O(n).

Checked

Identical to igraph 1.0 for n = 0..21, k = 1..4 and all three types, plus 20 trees of 1,000-60,000 vertices. 100,001 vertices build in 0.65x python-igraph's time.

C name

og_kary_tree

In notebooks

Og.KaryTree

igraph 1.0

igraph_kary_tree

See also

symmetric_tree, regular_tree, tree_from_parent_vector, tree_game

og_t g;
og_kary_tree(&g, 15, 2, OG_TREE_OUT);  /* full binary tree, 4 levels, parent -> child */
og_destroy(&g);

Builds a tree whose number of children is set level by level.

og_error_t og_symmetric_tree(
    og_t *graph,
    const og_vector_int_t *branches,
    og_tree_mode_t type
);

branches[d] is the number of children of every vertex on level d (the root is level 0), so branches (b0, b1, ..., bh-1) give 1 + b0 + b0 b1 + ... vertices. Vertices are numbered breadth first and edges listed by child, as in kary_tree(); the same number of children on every level gives kary_tree()'s graph. An empty vector gives a single vertex.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• branches Children per vertex on each level; every entry must be positive.
• type OG_TREE_OUT (edges from parent to child), OG_TREE_IN (child to parent) or OG_TREE_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL an entry of branches is 0 or negative
• OG_EINVMODE type is not a known value
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(|V|).

Checked

No oracle exposes it: the numbering was checked by hand and equals kary_tree() (exact) for constant branching (k 1..4, 0..4 levels, all types).

C name

og_symmetric_tree

In notebooks

Og.SymmetricTree

igraph 1.0

igraph_symmetric_tree

See also

kary_tree, regular_tree

Builds a tree of height h whose inner vertices all have degree k (a finite Bethe lattice).

og_error_t og_regular_tree(
    og_t *graph,
    og_int_t h,
    og_int_t k,
    og_tree_mode_t type
);

The root has k children and every other vertex above the last level k - 1, so all inner vertices have degree k and the leaves, at distance h from the root, degree 1. It is symmetric_tree() with branches (k, k-1, ..., k-1). h = 0 gives a single vertex.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• h The height: the distance from the root to the leaves.
• k The degree of the inner vertices.
• type OG_TREE_OUT (edges from parent to child), OG_TREE_IN (child to parent) or OG_TREE_UNDIRECTED.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL h is negative
• OG_EINVAL no such tree exists: k < 1 with h >= 1, or k = 1 with h >= 2
• OG_EINVMODE type is not a known value
• OG_EOVERFLOW the vertex or edge count would exceed the library's limits
• OG_ENOMEM there is not enough memory

Complexity

O(|V|).

Checked

No oracle exposes it: vertex and edge counts and degrees (k inside, 1 at the leaves) checked for h 0..4 and k 2..4; numbering as symmetric_tree().

C name

og_regular_tree

In notebooks

Og.RegularTree

igraph 1.0

igraph_regular_tree

See also

symmetric_tree, kary_tree

Builds one graph with exactly the given degrees, by a deterministic greedy construction.

og_error_t og_realize_degree_sequence(
    og_t *graph,
    const og_vector_int_t *outdeg,
    const og_vector_int_t *indeg,
    og_edge_type_sw_t allowed_edge_types,
    og_realize_degseq_t method
);

With indeg NULL, outdeg holds the degrees of an undirected graph; otherwise outdeg and indeg are the out- and in-degrees of a directed graph. Undirected sequences use the Havel-Hakimi construction: a vertex is picked and joined to the vertices with the largest remaining degrees. method picks the vertex: OG_REALIZE_DEGSEQ_SMALLEST the one with the smallest remaining degree (for simple graphs this gives a connected graph whenever the sequence has one: Horvát and Modes 2021), OG_REALIZE_DEGSEQ_LARGEST the largest, OG_REALIZE_DEGSEQ_INDEX the lowest id. Directed sequences use the Kleitman-Wang construction, ordering the vertices by remaining (in, out) degree.

allowed_edge_types: OG_SIMPLE_SW for a simple graph, OG_MULTI_SW for a loopless multigraph, OG_LOOPS_SW | OG_MULTI_SW for a multigraph with loops (undirected only; a vertex left alone with stubs takes them as loops). A sequence with no realization of that kind is refused. Ties among equal degrees and the edge order are python-igraph 1.0's.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• outdeg The degrees (undirected) or out-degrees (directed).
• indeg NULL for an undirected graph, else the in-degrees (same length).
• allowed_edge_types OG_SIMPLE_SW, OG_MULTI_SW, or OG_LOOPS_SW | OG_MULTI_SW (undirected only).
• method Which vertex is handled next: OG_REALIZE_DEGSEQ_SMALLEST, OG_REALIZE_DEGSEQ_LARGEST or OG_REALIZE_DEGSEQ_INDEX.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL method is not a known value
• OG_EINVAL outdeg and indeg differ in length, or a degree is negative
• OG_EINVAL the out- and in-degree sums differ, or an undirected sum is odd
• OG_EINVAL no graph of the requested kind has these degrees
• OG_EOVERFLOW the degree sum is too large
• OG_UNIMPLEMENTED a directed graph with loops or multi-edges is asked for
• OG_UNIMPLEMENTED self-loops are allowed without multi-edges
• OG_ENOMEM there is not enough memory

Complexity

Simple undirected O(|V| + |E| + max degree); undirected multigraph O(|V| |E|); directed O(|V|^2 + |E|).

Checked

Identical to igraph 1.0, edges and order, on 5,541 fixture cases (every method and edge type, sequences of random graphs up to 300 vertices and non-realizable ones) and 132 larger cases of 300-2,000 vertices. 10,000 vertices / 50,000 arcs: 0.21-0.25 s, python-igraph 1.1-1.8 s.

C name

og_realize_degree_sequence

In notebooks

Og.RealizeDegreeSequence

igraph 1.0

igraph_realize_degree_sequence

See also

realize_bipartite_degree_sequence, degree_sequence_game, is_graphical, k_regular_game

og_t g;
og_vector_int_t deg;
og_vector_int_init_int(&deg, 5, 3, 2, 2, 2, 1);
og_realize_degree_sequence(&g, &deg, NULL, OG_SIMPLE_SW, OG_REALIZE_DEGSEQ_SMALLEST);
/* a simple undirected graph with degrees 3, 2, 2, 2, 1 (5 edges) */
og_vector_int_destroy(&deg);
og_destroy(&g);

Builds one bipartite graph with exactly the given degrees on its two sides.

og_error_t og_realize_bipartite_degree_sequence(
    og_t *graph,
    const og_vector_int_t *degrees1,
    const og_vector_int_t *degrees2,
    const og_edge_type_sw_t allowed_edge_types,
    const og_realize_degseq_t method
);

Vertices 0..n1-1 take the degrees in degrees1 and vertices n1..n1+n2-1 those in degrees2; edges only join the two sides. Each step picks a vertex by method (smallest or largest remaining degree, from either side with the first side winning ties, or the lowest id) and joins it to the vertices of largest remaining degree on the other side: to all its remaining stubs at once for a simple graph, or with one edge per step when OG_MULTI_SW allows multi-edges. The self-loop switch has no effect.

The two degree sums must agree. Ties and the edge order are python-igraph 1.0's.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• degrees1 Degrees of the first side (ids 0..n1-1).
• degrees2 Degrees of the second side (ids n1..n1+n2-1).
• allowed_edge_types OG_SIMPLE_SW or OG_MULTI_SW.
• method Which vertex is handled next: OG_REALIZE_DEGSEQ_SMALLEST, OG_REALIZE_DEGSEQ_LARGEST or OG_REALIZE_DEGSEQ_INDEX.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL method is not a known value
• OG_EINVAL a degree is negative, or the two sums differ
• OG_EINVAL no bipartite graph of the requested kind has these degrees
• OG_EOVERFLOW too many vertices, or the degree sum is too large
• OG_ENOMEM there is not enough memory

Complexity

Each step re-sorts both sides, O(|V| log |V|): O(|V|^2 log |V| + |E|) for simple graphs, O(|E| |V| log |V|) for multigraphs.

Checked

Identical to igraph 1.0 on 1,278 fixture cases (simple and multi, every method) and 50 larger ones of 150-800 vertices per side. Inputs with exactly one empty side are unit-tested only: python-igraph 1.0 aborts on them.

C name

og_realize_bipartite_degree_sequence

In notebooks

Og.RealizeBipartiteDegreeSequence

igraph 1.0

igraph_realize_bipartite_degree_sequence

See also

realize_degree_sequence, create_bipartite, full_bipartite

Builds a named graph from a built-in collection of well-known graphs.

og_error_t og_famous(og_t *graph, const char *name);

The name is matched without regard to case. Names (aliases in brackets): Bull, Chvatal, Coxeter, Cubical, Diamond, Dodecahedral (Dodecahedron), Folkman, Franklin, Frucht, Grotzsch (Groetzsch), Heawood, Herschel, House, HouseX, Icosahedral (Icosahedron), Krackhardt_Kite, Levi, McGee, Meredith, Noperfectmatching, Nonline, Octahedral (Octahedron), Petersen, Robertson, Smallestcyclicgroup, Tetrahedral (Tetrahedron), Thomassen, Tutte, Uniquely3colorable, Walther, Zachary. All are undirected.

The vertex numbering and edge order are igraph 1.0's, recorded from python-igraph's output, so famous(g, "Petersen") is the same labelled graph in both libraries.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• name The graph's name, any case.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL name is NULL or not a known name
• OG_ENOMEM there is not enough memory

Complexity

O(|V| + |E|).

Checked

All 36 names and aliases, case variants and unknown names identical to igraph 1.0.

C name

og_famous

In notebooks

Og.Famous

igraph 1.0

igraph_famous

See also

atlas, lcf, generalized_petersen

og_t g;
og_famous(&g, "petersen");  /* 10 vertices, 15 edges; case does not matter */
og_destroy(&g);

Builds graph number k of An Atlas of Graphs: every graph with up to 7 vertices.

og_error_t og_atlas(og_t *graph, og_int_t number);

The 1,253 graphs of Read and Wilson's An Atlas of Graphs (Oxford, 1998) are numbered 0 to 1252 as in the book: by vertex count, then edge count, then finer rules on the degree sequence and the automorphisms. Graph 0 is the null graph and graph 1 the single vertex. The labelled graphs (vertex numbering and edge order) are igraph 1.0's, recorded from python-igraph's output. All are undirected.

Parameters

• graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
• number The graph's number, 0..1252.

Returns

OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.

Errors

• OG_EINVAL number is outside 0..1252
• OG_ENOMEM there is not enough memory

Complexity

O(1) (at most 7 vertices and 21 edges).

Checked

All 1,253 graphs identical to igraph 1.0; -1 and 1253 give EINVAL as in the reference.

C name

og_atlas

In notebooks

Og.Atlas

igraph 1.0

igraph_atlas

See also

famous, isoclass_create, graph_count