Graph basics

Optional start-up call that reseeds the calling thread's default random number generator from the clock.

og_error_t og_setup(void);

Open Graph needs no initialisation: every function works without setup. The call exists so that code ported from igraph keeps compiling and behaves the same.

All it does is give the calling thread's default generator (PCG32) a new seed from the clock. Other threads keep their own generators. Call rng_seed afterwards when results must be reproducible.

Returns

OG_SUCCESS (it cannot fail).

Complexity

O(1).

Checked

Unit test only: it just seeds the default generator.

C name

og_setup

In notebooks

Og.Setup

igraph 1.0

igraph_setup

See also

rng_default, rng_seed

Makes a graph with n vertices, numbered 0 to n - 1, and no edges.

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

Initialises *graph as a directed or undirected graph with n isolated vertices. Release it with destroy. If an attribute handler is installed (the attributes area does that), it is told about the new graph with no attribute records; use empty_attrs to pass graph attributes.

Open Graph stores a graph as its edge list plus two compressed adjacency tables (out-edges grouped by source, in-edges grouped by target). Queries read these tables without allocating; every structural change rebuilds them, so add edges in batches.

Parameters

• graph Graph object to initialise; it must not hold a live graph.
• n Number of vertices, 0 or more.
• directed OG_DIRECTED or OG_UNDIRECTED.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL n is negative.
• OG_ERANGE n is larger than OG_VCOUNT_MAX.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(|V|).

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_empty

In notebooks

Og.Empty

igraph 1.0

igraph_empty

See also

empty_attrs, add_edges, destroy, copy

og_t g;
og_vector_int_t edges;
og_vector_int_init_int(&edges, 6, 0, 1, 1, 2, 2, 0);   /* a triangle */
og_empty(&g, 3, OG_UNDIRECTED);
og_add_edges(&g, &edges, NULL);
printf("%" OG_PRId " vertices, %" OG_PRId " edges\n", og_vcount(&g), og_ecount(&g));
og_vector_int_destroy(&edges);
og_destroy(&g);

Same as empty, and hands a list of graph-attribute records to the attribute handler.

og_error_t og_empty_attrs(
    og_t *graph,
    og_int_t n,
    og_bool_t directed,
    const og_attribute_record_list_t *attr
);

Without an attribute handler installed, attr is ignored and the call is empty. With one, the handler's init hook receives attr after the structure is built. If the hook fails, the half-made graph is freed and the hook's error is returned.

Parameters

• graph Graph object to initialise.
• n Number of vertices, 0 or more.
• directed OG_DIRECTED or OG_UNDIRECTED.
• attr Graph-attribute records for the handler, or NULL.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL n is negative.
• OG_ERANGE n is larger than OG_VCOUNT_MAX.
• OG_EINTERNAL The attribute handler reported success but set up no attribute storage.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(|V|) plus the attribute handler's work.

Checked

Unit tests; the records go to whatever handler the attributes area installs.

C name

og_empty_attrs

In notebooks

Og.EmptyAttrs

igraph 1.0

igraph_empty_attrs

See also

empty, destroy

Duplicates a graph into a new, independent graph object.

og_error_t og_copy(og_t *to, const og_t *from);

*to receives its own copy of from's vertices, edges (with the same ids), directedness and cached properties, and, through the attribute handler, its attributes. Changing one graph afterwards never affects the other.

*to must not hold a live graph; release the copy with destroy.

Parameters

• to Graph object to initialise as the copy.
• from Graph to copy.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_ENOMEM Memory could not be allocated.
• OG_EINTERNAL The attribute handler reported success but copied no attribute storage.

Complexity

O(|V| + |E|) plus the attribute handler's work.

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_copy

In notebooks

Og.Copy

igraph 1.0

igraph_copy

See also

empty, destroy, is_same_graph

Frees everything a graph owns.

void og_destroy(og_t *graph);

Releases the edge list, the adjacency tables and, through the attribute handler, the attributes. A NULL pointer is ignored, and destroying the same graph twice is harmless (the second call finds nothing to free), so a graph can be registered on the cleanup stack.

The object must be initialised again (empty, copy, ...) before it is used again.

Parameters

• graph The graph to release, or NULL.

Returns

Nothing.

Complexity

O(1) plus freeing the attributes.

Checked

Unit tests in tests/foundation/basic.c.

C name

og_destroy

In notebooks

Og.Destroy

igraph 1.0

igraph_destroy

See also

empty, copy

How many vertices the graph has.

og_int_t og_vcount(const og_t *graph);

Vertex ids run from 0 to vcount(graph) - 1.

Parameters

• graph The graph.

Returns

The vertex count.

Complexity

O(1).

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_vcount

In notebooks

Og.Vcount

igraph 1.0

igraph_vcount

See also

ecount

How many edges the graph has.

og_int_t og_ecount(const og_t *graph);

Edge ids run from 0 to ecount(graph) - 1, in the order the edges were added. Deleting edges or vertices renumbers the edges that remain, keeping their relative order.

Parameters

• graph The graph.

Returns

The edge count.

Complexity

O(1).

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_ecount

In notebooks

Og.Ecount

igraph 1.0

igraph_ecount

See also

vcount, edge

Tells whether a graph is directed.

og_bool_t og_is_directed(const og_t *graph);

Directedness is fixed when the graph is made (empty) and never changes.

Parameters

• graph The graph.

Returns

true for a directed graph, false for an undirected one.

Complexity

O(1).

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_is_directed

In notebooks

Og.IsDirected

igraph 1.0

igraph_is_directed

See also

empty

The two endpoints of one edge.

og_error_t og_edge(
    const og_t *graph,
    og_int_t eid,
    og_int_t *from,
    og_int_t *to
);

Writes the tail of edge eid to *from and its head to *to. In an undirected graph *from always receives the smaller vertex id, because undirected edges are stored as (smaller, larger), the way python-igraph reports them.

Parameters

• graph The graph.
• eid Edge id.
• from Receives the first endpoint (tail).
• to Receives the second endpoint (head).

Returns

OG_SUCCESS, or OG_EINVEID.

Errors

• OG_EINVEID eid is not an edge of the graph.

Complexity

O(1).

Checked

Unit tests in tests/foundation/basic.c.

C name

og_edge

In notebooks

Og.Edge

igraph 1.0

igraph_edge

See also

edges, get_eid

The endpoints of the edges an edge selector names, as one integer vector.

og_error_t og_edges(
    const og_t *graph,
    og_es_t eids,
    og_vector_int_t *edges,
    og_bool_t bycol
);

For k selected edges, edges is resized to 2k. With bycol false the layout is from0, to0, from1, to1, ... (vertex pairs, the form add_edges takes). With bycol true it is the k first endpoints followed by the k second endpoints (the two columns of an edge list).

Edges come in the selector's order. Undirected edges give (smaller, larger).

Parameters

• graph The graph.
• eids Edge selector, e.g. ess_all(OG_EDGEORDER_ID).
• edges Initialised integer vector; resized to 2k.
• bycol false for pairs, true for two columns.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVEID The selector names an edge outside 0 .. ecount(graph) - 1.
• OG_EINVAL A range selector ends before it starts, or a pairs/path selector names two vertices with no edge between them.
• OG_EINVVID A pairs, path, incident or all-between selector names a vertex that does not exist.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(k) for k edges, plus resolving the selector.

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_edges

In notebooks

Og.Edges

igraph 1.0

igraph_edges

See also

edge, es_all, add_edges

Finds the id of an edge between two vertices.

og_error_t og_get_eid(
    const og_t *graph,
    og_int_t *eid,
    og_int_t from,
    og_int_t to,
    og_bool_t directed,
    og_bool_t error
);

Looks for an edge joining from and to. In an undirected graph the order of the two vertices does not matter. In a directed graph with directed true only an edge from -> to qualifies; with directed false, from -> to is tried first and to -> from second.

When parallel edges qualify, the one with the largest id is reported (python-igraph 1.0 does the same; measured as a black box). If no edge qualifies, *eid becomes -1, and with error true the call also fails with OG_EINVAL.

Parameters

• graph The graph.
• eid Receives the edge id, or -1.
• from First vertex.
• to Second vertex.
• directed In a directed graph: whether only from -> to counts. Ignored for undirected graphs.
• error Whether a missing edge is an error (OG_EINVAL) rather than -1.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID from or to is not a vertex of the graph.
• OG_EINVAL There is no such edge and error is true.

Complexity

O(log d): binary search in the shorter of from's out-slice and to's in-slice (d its length).

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_get_eid

In notebooks

Og.GetEid

igraph 1.0

igraph_get_eid

See also

get_eids, get_all_eids_between, es_pairs

Looks up the edge ids for a list of vertex pairs.

og_error_t og_get_eids(
    const og_t *graph,
    og_vector_int_t *eids,
    const og_vector_int_t *pairs,
    og_bool_t directed,
    og_bool_t error
);

pairs holds from0, to0, from1, to1, ...; eids is resized to one id per pair, each found the way get_eid finds it (the largest id among parallel edges; both directions in a directed graph when directed is false). A pair with no edge gives -1, or fails with OG_EINVAL when error is true.

Every vertex id is checked before any lookup.

Parameters

• graph The graph.
• eids Initialised integer vector; resized to the number of pairs.
• pairs Vertex ids, two per wanted edge.
• directed In a directed graph: whether only the given direction counts.
• error Whether a missing edge is an error rather than -1.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL pairs has an odd length, or a pair has no edge and error is true.
• OG_EINVVID pairs names a vertex that does not exist.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(k log d) for k pairs.

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_get_eids

In notebooks

Og.GetEids

igraph 1.0

igraph_get_eids

See also

get_eid, expand_path_to_pairs, es_pairs

Lists the ids of all edges between two vertices, parallel edges included.

og_error_t og_get_all_eids_between(
    const og_t *graph,
    og_vector_int_t *eids,
    og_int_t source,
    og_int_t target,
    og_bool_t directed
);

eids is cleared and receives every edge joining source and target, in increasing id order. In a directed graph with directed true only source -> target edges count; with directed false the edges of both directions are merged into one increasing list. For an undirected graph directed is ignored. When source equals target the self-loops at that vertex are listed, once each.

Parameters

• graph The graph.
• eids Initialised integer vector for the result.
• source First vertex.
• target Second vertex.
• directed In a directed graph: whether only source -> target counts.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID source or target is not a vertex of the graph.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(log d + k) for k edges found.

Checked

Unit tests; python-igraph has no direct equivalent to compare with. Ids come in increasing order.

C name

og_get_all_eids_between

In notebooks

Og.GetAllEidsBetween

igraph 1.0

igraph_get_all_eids_between

See also

get_eid, es_all_between

Lists the neighbours of one vertex.

og_error_t og_neighbors(
    const og_t *graph,
    og_vector_int_t *neis,
    og_int_t pnode,
    og_neimode_t mode,
    og_loops_t loops,
    og_bool_t multiple
);

neis receives the vertices adjacent to pnode, sorted by vertex id, with one entry per edge when multiple is true. mode picks which edges count in a directed graph: OG_OUT (heads of out-edges), OG_IN (tails of in-edges) or OG_ALL (both). It is ignored for undirected graphs.

loops decides how a self-loop appears: OG_NO_LOOPS leaves it out, OG_LOOPS_ONCE lists pnode once per loop, and OG_LOOPS_TWICE (= OG_LOOPS) lists it twice where both ends of the loop are seen (undirected graphs and OG_ALL), once for OG_OUT or OG_IN. With multiple false each neighbour is listed once, except that a self-loop still appears twice where OG_LOOPS_TWICE counts it twice.

The order is python-igraph 1.0's, checked on 200 random graphs.

Parameters

• graph The graph.
• neis Initialised integer vector for the result.
• pnode The vertex.
• mode OG_OUT, OG_IN or OG_ALL (directed graphs only).
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.
• multiple true: one entry per edge; false: parallel edges give one entry.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID pnode is not a vertex of the graph.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL loops is not one of the three loop modes.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(d), d the degree of pnode.

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_neighbors

In notebooks

Og.Neighbors

igraph 1.0

igraph_neighbors

See also

incident, degree, vs_adj

og_t g;
og_vector_int_t edges, neis;
og_vector_int_init_int(&edges, 6, 0, 1, 0, 2, 2, 2);   /* 2 has a self-loop */
og_empty(&g, 3, OG_UNDIRECTED);
og_add_edges(&g, &edges, NULL);
og_vector_int_init(&neis, 0);
og_neighbors(&g, &neis, 2, OG_ALL, OG_LOOPS_TWICE, true);
og_vector_int_print(&neis);                             /* 0 2 2 */
og_vector_int_destroy(&neis);
og_vector_int_destroy(&edges);
og_destroy(&g);

Lists the ids of the edges incident on one vertex.

og_error_t og_incident(
    const og_t *graph,
    og_vector_int_t *eids,
    og_int_t pnode,
    og_neimode_t mode,
    og_loops_t loops
);

eids receives one entry per incident edge, ordered by the vertex at the other end; parallel edges to the same neighbour come with the larger id first. In a directed graph with OG_ALL, out-edges and in-edges to the same neighbour alternate, out-edge first.

mode and loops work as for neighbors: with OG_LOOPS_TWICE a self-loop's id is listed twice in undirected graphs and for OG_ALL, OG_LOOPS_ONCE lists it once and OG_NO_LOOPS leaves it out. The order is python-igraph 1.0's (200 random graphs).

Parameters

• graph The graph.
• eids Initialised integer vector for the result.
• pnode The vertex.
• mode OG_OUT, OG_IN or OG_ALL (directed graphs only).
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID pnode is not a vertex of the graph.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL loops is not one of the three loop modes.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(d), d the degree of pnode.

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_incident

In notebooks

Og.Incident

igraph 1.0

igraph_incident

See also

neighbors, es_incident, edge

The degrees of a set of vertices.

og_error_t og_degree(
    const og_t *graph,
    og_vector_int_t *res,
    const og_vs_t vids,
    og_neimode_t mode,
    og_loops_t loops
);

res is resized to the number of selected vertices and receives each one's degree, in the selector's order. In a directed graph mode picks the out-degree (OG_OUT), in-degree (OG_IN) or their sum (OG_ALL); for undirected graphs it is ignored.

loops: OG_LOOPS_TWICE counts a self-loop twice where both of its ends are seen (undirected graphs, OG_ALL) and once for OG_OUT or OG_IN; OG_LOOPS_ONCE counts it once; OG_NO_LOOPS not at all. Parallel edges always count with their multiplicity.

Parameters

• graph The graph.
• res Initialised integer vector for the result.
• vids Vertex selector, e.g. vss_all().
• mode OG_OUT, OG_IN or OG_ALL.
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL loops is not one of the three loop modes, or a range selector ends before it starts.
• OG_EINVVID The selector names a vertex that does not exist.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(k) for k vertices when loops count as stored (OG_LOOPS_TWICE, or OG_LOOPS_ONCE with OG_OUT/OG_IN); otherwise O(k log d) plus the number of loops, to count the self-loops.

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_degree

In notebooks

Og.Degree

igraph 1.0

igraph_degree

See also

degree_1, neighbors

og_vector_int_t deg;
og_vector_int_init(&deg, 0);
og_degree(&g, &deg, og_vss_all(), OG_ALL, OG_LOOPS);
og_vector_int_print(&deg);
og_vector_int_destroy(&deg);

Degree of one vertex, returned through a pointer.

og_error_t og_degree_1(
    const og_t *graph,
    og_int_t *deg,
    og_int_t vid,
    og_neimode_t mode,
    og_loops_t loops
);

The one-vertex form of degree: the same mode and loops rules, with the result in *deg and no vector or selector needed.

Parameters

• graph The graph.
• deg Receives the degree.
• vid The vertex.
• mode OG_OUT, OG_IN or OG_ALL.
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID vid is not a vertex of the graph.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL loops is not one of the three loop modes.

Complexity

O(1) when loops count as stored, otherwise O(log d) plus the number of loops.

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_degree_1

In notebooks

Og.Degree1

igraph 1.0

igraph_degree_1

See also

degree

Adds one edge.

og_error_t og_add_edge(og_t *graph, og_int_t from, og_int_t to);

Appends the edge from -> to (in an undirected graph, {from, to}); its id is the previous ecount. The adjacency tables are rebuilt for every call, so adding m edges one at a time costs O(m (|V| + |E|)): collect them in a vector and call add_edges once instead. No attribute records are passed to the attribute handler.

Parameters

• graph The graph to change.
• from First endpoint.
• to Second endpoint.

Returns

OG_SUCCESS, or the error code; on failure the graph is unchanged.

Errors

• OG_EINVVID from or to is not a vertex of the graph.
• OG_ERANGE The graph already holds OG_ECOUNT_MAX edges.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(|V| + |E|).

Checked

Unit tests in tests/foundation/basic.c.

C name

og_add_edge

In notebooks

Og.AddEdge

igraph 1.0

igraph_add_edge

See also

add_edges, add_vertices

Adds a batch of edges.

og_error_t og_add_edges(
    og_t *graph,
    const og_vector_int_t *edges,
    const og_attribute_record_list_t *attr
);

edges holds from0, to0, from1, to1, ...; the new edges get the next ids in that order. Undirected edges are stored as (smaller, larger). Self-loops and parallel edges are allowed.

Everything is checked before the graph changes, and on any failure (the attribute handler's included) the graph is left exactly as it was. attr carries edge-attribute records for the attribute handler; without a handler it is ignored, so pass NULL. The adjacency tables are rebuilt once per call by two counting-sort passes, which is why one large batch is much cheaper than many small ones.

Parameters

• graph The graph to change.
• edges Vertex ids, two per new edge.
• attr Edge-attribute records for the handler, or NULL.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL edges has an odd length.
• OG_EINVVID edges names a vertex that does not exist.
• OG_ERANGE The result would hold more than OG_ECOUNT_MAX edges.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(|V| + |E|) for the whole batch.

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_add_edges

In notebooks

Og.AddEdges

igraph 1.0

igraph_add_edges

See also

add_edge, empty, delete_edges

Adds isolated vertices.

og_error_t og_add_vertices(
    og_t *graph,
    og_int_t nv,
    const og_attribute_record_list_t *attr
);

Appends nv vertices with the ids vcount .. vcount + nv - 1; existing ids do not change. attr carries vertex-attribute records for the attribute handler (ignored without one). Adding 0 vertices changes nothing and reads no record. On failure the graph is unchanged.

Parameters

• graph The graph to change.
• nv Number of vertices to add, 0 or more.
• attr Vertex-attribute records for the handler, or NULL.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL nv is negative.
• OG_ERANGE The result would hold more than OG_VCOUNT_MAX vertices.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(nv) amortised, plus the attribute handler's work.

Checked

Unit tests in tests/foundation/basic.c.

C name

og_add_vertices

In notebooks

Og.AddVertices

igraph 1.0

igraph_add_vertices

See also

add_edges, delete_vertices

Removes the edges an edge selector names.

og_error_t og_delete_edges(og_t *graph, og_es_t edges);

The remaining edges keep their relative order and are renumbered 0 .. m' - 1 without gaps; vertex ids do not change. An edge named twice is removed once. Edge attributes move with their edges. On failure the graph is unchanged.

Parameters

• graph The graph to change.
• edges Edge selector naming the edges to remove.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVEID The selector names an edge outside 0 .. ecount(graph) - 1.
• OG_EINVAL A range selector ends before it starts, or a pairs/path selector names two vertices with no edge between them.
• OG_EINVVID A pairs, path, incident or all-between selector names a vertex that does not exist.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(|V| + |E|).

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_delete_edges

In notebooks

Og.DeleteEdges

igraph 1.0

igraph_delete_edges

See also

delete_vertices, add_edges

Removes vertices together with every edge that touches them.

og_error_t og_delete_vertices(og_t *graph, const og_vs_t vertices);

The remaining vertices keep their relative order and are renumbered 0 .. n' - 1, and so are the remaining edges. Vertex and edge attributes move with their objects. Use delete_vertices_map to learn the new ids. On failure the graph is unchanged.

Parameters

• graph The graph to change.
• vertices Vertex selector naming the vertices to remove.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID The selector names a vertex outside 0 .. vcount(graph) - 1.
• OG_EINVAL A range selector ends before it starts.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(|V| + |E|).

Checked

Same results as python-igraph 1.0 on 200 seeded random graphs (tests/foundation/fixtures/basic.json) plus hand-worked cases.

C name

og_delete_vertices

In notebooks

Og.DeleteVertices

igraph 1.0

igraph_delete_vertices

See also

delete_vertices_map, delete_edges

Removes vertices like delete_vertices and reports where every vertex went.

og_error_t og_delete_vertices_map(
    og_t *graph,
    const og_vs_t vertices,
    og_vector_int_t *map,
    og_vector_int_t *invmap
);

map, when not NULL, is resized to the old vertex count: map[old] is the new id, or -1 for a removed vertex. invmap, when not NULL, is resized to the new vertex count: invmap[new] is the old id. Both outputs are sized before the graph changes, so nothing can fail once it has changed; on failure the graph is unchanged.

Parameters

• graph The graph to change.
• vertices Vertex selector naming the vertices to remove.
• map Initialised integer vector for old -> new ids, or NULL.
• invmap Initialised integer vector for new -> old ids, or NULL.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID The selector names a vertex outside 0 .. vcount(graph) - 1.
• OG_EINVAL A range selector ends before it starts.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(|V| + |E|).

Checked

Unit tests; the removal itself is the one delete_vertices checks against python-igraph.

C name

og_delete_vertices_map

In notebooks

Og.DeleteVerticesMap

igraph 1.0

igraph_delete_vertices_map

See also

delete_vertices

Turns a vertex path into the list of its consecutive vertex pairs, in place.

og_error_t og_expand_path_to_pairs(og_vector_int_t *path);

A path v0, v1, ..., vk becomes v0, v1, v1, v2, ..., v(k-1), vk: the 2k-entry form that get_eids and add_edges take. A path of fewer than two vertices becomes empty.

Parameters

• path Vertex ids along the path; replaced by the pairs.

Returns

OG_SUCCESS, or OG_ENOMEM.

Errors

• OG_ENOMEM Memory could not be allocated.

Complexity

O(k).

Checked

Unit tests in tests/foundation/basic.c.

C name

og_expand_path_to_pairs

In notebooks

Og.ExpandPathToPairs

igraph 1.0

igraph_expand_path_to_pairs

See also

get_eids, es_path

Forgets every cached whole-graph property.

void og_invalidate_cache(const og_t *graph);

Once computed, some yes/no facts about a graph are cached in it: whether it has a self-loop, multi-edges or mutual edges, whether it is weakly or strongly connected, a DAG or a forest. Open Graph keeps or drops each entry by itself as the graph changes, so normal code never needs this call. It is useful for timing measurements and tests.

Parameters

• graph The graph.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests in tests/foundation/basic.c.

C name

og_invalidate_cache

In notebooks

Og.Native.og_invalidate_cache

igraph 1.0

igraph_invalidate_cache

See also

copy

Checks whether two graphs have the same directedness, vertex count and edge multiset.

og_error_t og_is_same_graph(
    const og_t *graph1,
    const og_t *graph2,
    og_bool_t *res
);

*res becomes true only if the two graphs are both directed or both undirected, hold equally many vertices, and list identical edges (counted with multiplicity) between identical vertex ids. Edge ids may differ: two graphs holding the same edges in another order are the same. Attributes are not compared. This is not an isomorphism test (see the isomorphism area).

Parameters

• graph1 First graph.
• graph2 Second graph.
• res Receives the answer.

Returns

OG_SUCCESS (it cannot fail).

Complexity

O(|V| + |E|).

Checked

Unit tests in tests/foundation/basic.c.

C name

og_is_same_graph

In notebooks

Og.IsSameGraph

igraph 1.0

igraph_is_same_graph

See also

copy

Vertex selector for every vertex of the graph.

og_error_t og_vs_all(og_vs_t *vs);

A selector describes a set of vertices without referring to a graph; it is checked and resolved when a function uses it (or by vit_create). vs_all resolves to 0 .. n - 1 in increasing order. It owns nothing, so vs_destroy is optional; vss_all() returns the same selector as a value for use as a function argument.

Parameters

• vs Selector to fill.

Returns

OG_SUCCESS.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_all

In notebooks

Og.Native.og_vs_all

igraph 1.0

igraph_vs_all

See also

vss_all, vit_create, vs_is_all

Vertex selector for the neighbours of one vertex.

og_error_t og_vs_adj(
    og_vs_t *vs,
    og_int_t vid,
    og_neimode_t mode,
    og_loops_t loops,
    og_bool_t multiple
);

Resolves to exactly the list neighbors(graph, ..., vid, mode, loops, multiple) returns, in the same order. vid, mode and loops are checked when the selector is used, not when it is made.

Parameters

• vs Selector to fill.
• vid The vertex whose neighbours are selected.
• mode OG_OUT, OG_IN or OG_ALL.
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.
• multiple Whether parallel edges give repeated entries.

Returns

OG_SUCCESS.

Errors

• OG_EINVVID When used: vid is not a vertex of the graph.
• OG_EINVMODE When used: mode is invalid.

Complexity

O(1) to make; O(d) to resolve.

Checked

Unit tests; same order as neighbors, which is checked against python-igraph.

C name

og_vs_adj

In notebooks

Og.Native.og_vs_adj

igraph 1.0

igraph_vs_adj

See also

neighbors, vs_nonadj

Vertex selector for the vertices not adjacent to one vertex.

og_error_t og_vs_nonadj(og_vs_t *vs, og_int_t vid, og_neimode_t mode);

Resolves to every vertex that is not a neighbour of vid under mode, in increasing id order. vid itself is included unless it has a self-loop.

Parameters

• vs Selector to fill.
• vid The vertex.
• mode OG_OUT, OG_IN or OG_ALL (directed graphs only).

Returns

OG_SUCCESS.

Errors

• OG_EINVVID When used: vid is not a vertex of the graph.
• OG_EINVMODE When used: mode is invalid.
• OG_ENOMEM When used: memory could not be allocated.

Complexity

O(1) to make; O(|V| + d) to resolve.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_nonadj

In notebooks

Og.Native.og_vs_nonadj

igraph 1.0

igraph_vs_nonadj

See also

vs_adj

Selector that resolves to no vertex at all.

og_error_t og_vs_none(og_vs_t *vs);

Resolves to no vertices in any graph.

Parameters

• vs Selector to fill.

Returns

OG_SUCCESS.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_none

In notebooks

Og.Native.og_vs_none

igraph 1.0

igraph_vs_none

See also

vss_none

Selector naming exactly one vertex id.

og_error_t og_vs_1(og_vs_t *vs, og_int_t vid);

The id is checked when the selector is used.

Parameters

• vs Selector to fill.
• vid The vertex id.

Returns

OG_SUCCESS.

Errors

• OG_EINVVID When used: vid is not a vertex of the graph.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_1

In notebooks

Og.Native.og_vs_1

igraph 1.0

igraph_vs_1

See also

vss_1

Vertex selector that borrows the caller's vector of vertex ids.

og_error_t og_vs_vector(og_vs_t *vs, const og_vector_int_t *v);

No copy is made: v must stay alive and unchanged while the selector is used, and vs_destroy does not free it. Ids are visited in v's order, repeats included; each is checked when the selector is used.

Parameters

• vs Selector to fill.
• v Vertex ids (borrowed).

Returns

OG_SUCCESS.

Errors

• OG_EINVVID When used: v holds an id that is not a vertex of the graph.

Complexity

O(1) to make; O(k) to check k ids when used.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_vector

In notebooks

Og.Native.og_vs_vector

igraph 1.0

igraph_vs_vector

See also

vs_vector_copy, vss_vector

Vertex selector from int arguments ending in -1.

og_error_t og_vs_vector_small(og_vs_t *vs, ...);

vs_vector_small(&vs, 1, 4, 4, -1) selects 1, 4, 4. The ids are copied into a vector the selector owns, so release it with vs_destroy.

Parameters

• vs Selector to fill.
• ... Vertex ids as int, then -1.

Returns

OG_SUCCESS, or OG_ENOMEM.

Errors

• OG_ENOMEM Memory could not be allocated.
• OG_EINVVID When used: an id is not a vertex of the graph.

Complexity

O(k).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_vector_small

igraph 1.0

igraph_vs_vector_small

See also

vs_vector, vs_destroy

Vertex selector that keeps its own copy of a vector of vertex ids.

og_error_t og_vs_vector_copy(og_vs_t *vs, const og_vector_int_t *v);

Like vs_vector, but v is copied, so it may change or be destroyed afterwards. Release the selector with vs_destroy.

Parameters

• vs Selector to fill.
• v Vertex ids to copy.

Returns

OG_SUCCESS, or OG_ENOMEM.

Errors

• OG_ENOMEM Memory could not be allocated.
• OG_EINVVID When used: an id is not a vertex of the graph.

Complexity

O(k).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_vector_copy

In notebooks

Og.Native.og_vs_vector_copy

igraph 1.0

igraph_vs_vector_copy

See also

vs_vector, vs_destroy

Vertex selector for the ids start, start + 1, ..., end - 1.

og_error_t og_vs_range(og_vs_t *vs, og_int_t start, og_int_t end);

The range is half-open; start == end selects nothing. The bounds are checked when the selector is used.

Parameters

• vs Selector to fill.
• start First id.
• end One past the last id.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL When used: end is smaller than start.
• OG_EINVVID When used: the range reaches outside 0 .. vcount(graph).

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_range

In notebooks

Og.Native.og_vs_range

igraph 1.0

igraph_vs_range

See also

vss_range

Copies a vertex selector.

og_error_t og_vs_copy(og_vs_t *dest, const og_vs_t *src);

A selector that owns its ids (vs_vector_small, vs_vector_copy) gets its own copy of them; the others are copied as they are, so a borrowed vector stays borrowed. Release the copy with vs_destroy.

Parameters

• dest Selector to fill.
• src Selector to copy.

Returns

OG_SUCCESS, or OG_ENOMEM.

Errors

• OG_ENOMEM Memory could not be allocated.

Complexity

O(k) for a selector owning k ids, otherwise O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_copy

In notebooks

Og.Native.og_vs_copy

igraph 1.0

igraph_vs_copy

See also

vs_destroy

Frees what a vertex selector owns.

void og_vs_destroy(og_vs_t *vs);

Only selectors made by vs_vector_small and vs_vector_copy (and copies of them) own memory; for all others this does nothing. Immediate selectors (og_vss_*) never need it.

Parameters

• vs The selector.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_destroy

In notebooks

Og.Native.og_vs_destroy

igraph 1.0

igraph_vs_destroy

See also

vs_copy

Tells whether a selector is the all-vertices selector.

og_bool_t og_vs_is_all(const og_vs_t *vs);

true only for vs_all / vss_all. A range or vector that happens to list every vertex gives false.

Parameters

• vs The selector.

Returns

true or false.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_is_all

In notebooks

Og.Native.og_vs_is_all

igraph 1.0

igraph_vs_is_all

See also

vs_all

The number of vertices a selector resolves to in a graph.

og_error_t og_vs_size(
    const og_t *graph,
    const og_vs_t *vs,
    og_int_t *result
);

All, none, single, range and vector selectors are counted without building anything and without checking ids (a range whose end is below its start counts 0). Adjacent and non-adjacent selectors are resolved, which can fail the same way vit_create does.

Parameters

• graph The graph.
• vs The selector.
• result Receives the count.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID An adjacency selector names a vertex that does not exist.
• OG_EINVMODE An adjacency selector has an invalid mode.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(1) for most selectors; O(d) or O(|V|) for adjacency and non-adjacency.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_size

In notebooks

Og.Native.og_vs_size

igraph 1.0

igraph_vs_size

See also

vit_create

Reports which variant (all, range, vector, ...) a vertex selector is.

og_vs_type_t og_vs_type(const og_vs_t *vs);

Returns one of OG_VS_ALL, OG_VS_ADJ, OG_VS_NONE, OG_VS_1, OG_VS_VECTORPTR (borrowed vector), OG_VS_VECTOR (owned vector), OG_VS_RANGE, OG_VS_NONADJ.

Parameters

• vs The selector.

Returns

The selector kind.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vs_type

In notebooks

Og.Native.og_vs_type

igraph 1.0

igraph_vs_type

See also

vs_is_all

Immediate selector for every vertex.

og_vs_t og_vss_all(void);

An immediate selector is returned by value, owns nothing and is never destroyed, so it can be written straight into an argument list. degree(&g, &deg, vss_all(), OG_ALL, OG_LOOPS) gives every vertex's degree.

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vss_all

In notebooks

Og.Native.og_vss_all

igraph 1.0

igraph_vss_all

See also

vs_all

Immediate selector for no vertices.

og_vs_t og_vss_none(void);

An immediate selector is returned by value, owns nothing and is never destroyed, so it can be written straight into an argument list.

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vss_none

In notebooks

Og.Native.og_vss_none

igraph 1.0

igraph_vss_none

See also

vs_none

Immediate selector for a single vertex.

og_vs_t og_vss_1(og_int_t vid);

An immediate selector is returned by value, owns nothing and is never destroyed, so it can be written straight into an argument list. The id is checked when the selector is used (OG_EINVVID).

Parameters

• vid The vertex id.

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vss_1

In notebooks

Og.Native.og_vss_1

igraph 1.0

igraph_vss_1

See also

vs_1

Immediate selector that borrows a vector of vertex ids.

og_vs_t og_vss_vector(const og_vector_int_t *v);

An immediate selector is returned by value, owns nothing and is never destroyed, so it can be written straight into an argument list. v is borrowed: keep it alive while the selector is used.

Parameters

• v Vertex ids (borrowed).

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vss_vector

In notebooks

Og.Native.og_vss_vector

igraph 1.0

igraph_vss_vector

See also

vs_vector

Immediate selector for the ids start .. end - 1.

og_vs_t og_vss_range(og_int_t start, og_int_t end);

An immediate selector is returned by value, owns nothing and is never destroyed, so it can be written straight into an argument list. Bounds are checked when used, as for vs_range.

Parameters

• start First id.
• end One past the last id.

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vss_range

In notebooks

Og.Native.og_vss_range

igraph 1.0

igraph_vss_range

See also

vs_range

Edge selector for every edge, in a chosen order.

og_error_t og_es_all(og_es_t *es, og_edgeorder_type_t order);

OG_EDGEORDER_ID visits the ids 0 .. m - 1. OG_EDGEORDER_FROM groups the edges by first endpoint (ascending), then by second endpoint, parallel edges with the larger id first. OG_EDGEORDER_TO groups them by second endpoint, then by first. In an undirected graph both orders group by the smaller endpoint, as edges are stored (smaller, larger).

Only the id order counts as es_is_all.

Parameters

• es Selector to fill.
• order OG_EDGEORDER_ID, OG_EDGEORDER_FROM or OG_EDGEORDER_TO.

Returns

OG_SUCCESS, or OG_EINVAL.

Errors

• OG_EINVAL order is not one of the three edge orders.

Complexity

O(1) to make; O(|E|) to resolve the FROM and TO orders.

Checked

Unit tests: the FROM and TO orders group by endpoint, ties by the other endpoint and then by descending id.

C name

og_es_all

In notebooks

Og.Native.og_es_all

igraph 1.0

igraph_es_all

See also

ess_all, eit_create, edges

Edge selector for the edges incident on one vertex.

og_error_t og_es_incident(
    og_es_t *es,
    og_int_t vid,
    og_neimode_t mode,
    og_loops_t loops
);

Resolves to the list incident(graph, ..., vid, mode, loops) returns, in the same order. Arguments are checked when the selector is used.

Parameters

• es Selector to fill.
• vid The vertex.
• mode OG_OUT, OG_IN or OG_ALL.
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.

Returns

OG_SUCCESS.

Errors

• OG_EINVVID When used: vid is not a vertex of the graph.
• OG_EINVMODE When used: mode is invalid.

Complexity

O(1) to make; O(d) to resolve.

Checked

Unit tests; same order as incident, which is checked against python-igraph.

C name

og_es_incident

In notebooks

Og.Native.og_es_incident

igraph 1.0

igraph_es_incident

See also

incident

Selector that resolves to no edge at all.

og_error_t og_es_none(og_es_t *es);

Resolves to no edges in any graph.

Parameters

• es Selector to fill.

Returns

OG_SUCCESS.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_none

In notebooks

Og.Native.og_es_none

igraph 1.0

igraph_es_none

See also

ess_none

Selector naming exactly one edge id.

og_error_t og_es_1(og_es_t *es, og_int_t eid);

The id is checked when the selector is used.

Parameters

• es Selector to fill.
• eid The edge id.

Returns

OG_SUCCESS.

Errors

• OG_EINVEID When used: eid is not an edge of the graph.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_1

In notebooks

Og.Native.og_es_1

igraph 1.0

igraph_es_1

See also

ess_1

Edge selector for all edges between two vertices.

og_error_t og_es_all_between(
    og_es_t *es,
    og_int_t from,
    og_int_t to,
    og_bool_t directed
);

Resolves to get_all_eids_between(graph, ..., from, to, directed): every edge joining the two vertices, parallel edges included, in increasing id order. directed false also accepts the opposite direction in a directed graph; for undirected graphs it is ignored.

Parameters

• es Selector to fill.
• from First vertex.
• to Second vertex.
• directed In a directed graph: whether only from -> to counts.

Returns

OG_SUCCESS.

Errors

• OG_EINVVID When used: from or to is not a vertex of the graph.

Complexity

O(1) to make; O(log d + k) to resolve.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_all_between

In notebooks

Og.Native.og_es_all_between

igraph 1.0

igraph_es_all_between

See also

get_all_eids_between, es_pairs

Edge selector that borrows the caller's vector of edge ids.

og_error_t og_es_vector(og_es_t *es, const og_vector_int_t *v);

No copy is made: v must stay alive and unchanged while the selector is used. Ids are visited in v's order, repeats included, and checked when the selector is used.

Parameters

• es Selector to fill.
• v Edge ids (borrowed).

Returns

OG_SUCCESS.

Errors

• OG_EINVEID When used: v holds an id that is not an edge of the graph.

Complexity

O(1) to make; O(k) to check when used.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_vector

In notebooks

Og.Native.og_es_vector

igraph 1.0

igraph_es_vector

See also

es_vector_copy, ess_vector

Edge selector for the ids start, start + 1, ..., end - 1.

og_error_t og_es_range(og_es_t *es, og_int_t start, og_int_t end);

Half-open range, checked when used.

Parameters

• es Selector to fill.
• start First id.
• end One past the last id.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL When used: end is smaller than start.
• OG_EINVEID When used: the range reaches outside 0 .. ecount(graph).

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_range

In notebooks

Og.Native.og_es_range

igraph 1.0

igraph_es_range

See also

ess_range

Edge selector for the edges between given vertex pairs.

og_error_t og_es_pairs(
    og_es_t *es,
    const og_vector_int_t *v,
    og_bool_t directed
);

v holds from0, to0, from1, to1, ... and is copied into the selector. When used, each pair resolves to one edge, the way get_eid with error true finds it (the largest id among parallel edges). directed false also accepts the opposite direction in a directed graph.

Parameters

• es Selector to fill.
• v Vertex ids, two per edge (copied).
• directed In a directed graph: whether only the given direction counts.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL v has an odd length; when used: a pair has no edge.
• OG_EINVVID When used: a vertex does not exist.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(k) to make; O(k log d) to resolve.

Checked

Unit tests; the length must be even (checked when the selector is made).

C name

og_es_pairs

In notebooks

Og.Native.og_es_pairs

igraph 1.0

igraph_es_pairs

See also

get_eids, es_pairs_small, es_path

Edge selector for vertex pairs given as int arguments ending in -1.

og_error_t og_es_pairs_small(
    og_es_t *es,
    og_bool_t directed,
    int first,
    ...
);

es_pairs_small(&es, OG_DIRECTED, 0, 4, 4, 0, -1) selects the edge 0 -> 4 and the edge 4 -> 0. first == -1 gives an empty selector. The selector owns its ids; release it with es_destroy.

Parameters

• es Selector to fill.
• directed In a directed graph: whether only the given direction counts.
• first The first vertex id, or -1.
• ... The other vertex ids as int, then -1.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL An odd number of ids was given; when used: a pair has no edge.
• OG_EINVVID When used: a vertex does not exist.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(k) to make; O(k log d) to resolve.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_pairs_small

igraph 1.0

igraph_es_pairs_small

See also

es_pairs

Edge selector for the edges along a vertex path.

og_error_t og_es_path(
    og_es_t *es,
    const og_vector_int_t *v,
    og_bool_t directed
);

v lists the vertices v0, v1, ..., vk and is copied. The selector resolves to the edge between each consecutive pair (k edges), found as es_pairs finds them. A path of fewer than two vertices selects nothing.

Parameters

• es Selector to fill.
• v Vertex ids along the path (copied).
• directed In a directed graph: whether each step must follow edge direction.

Returns

OG_SUCCESS, or OG_ENOMEM.

Errors

• OG_ENOMEM Memory could not be allocated.
• OG_EINVAL When used: two consecutive vertices are not joined by an edge.
• OG_EINVVID When used: a vertex does not exist.

Complexity

O(k) to make; O(k log d) to resolve.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_path

In notebooks

Og.Native.og_es_path

igraph 1.0

igraph_es_path

See also

es_pairs, expand_path_to_pairs

Edge selector that keeps its own copy of a vector of edge ids.

og_error_t og_es_vector_copy(og_es_t *es, const og_vector_int_t *v);

Like es_vector, but v is copied, so it may change or be destroyed afterwards. Release with es_destroy.

Parameters

• es Selector to fill.
• v Edge ids to copy.

Returns

OG_SUCCESS, or OG_ENOMEM.

Errors

• OG_ENOMEM Memory could not be allocated.
• OG_EINVEID When used: an id is not an edge of the graph.

Complexity

O(k).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_vector_copy

In notebooks

Og.Native.og_es_vector_copy

igraph 1.0

igraph_es_vector_copy

See also

es_vector, es_destroy

Immediate selector for every edge, in a chosen order.

og_es_t og_ess_all(og_edgeorder_type_t order);

An immediate selector is returned by value, owns nothing and is never destroyed. The orders are those of es_all; a value other than OG_EDGEORDER_FROM or OG_EDGEORDER_TO gives the id order.

Parameters

• order OG_EDGEORDER_ID, OG_EDGEORDER_FROM or OG_EDGEORDER_TO.

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_ess_all

In notebooks

Og.Native.og_ess_all

igraph 1.0

igraph_ess_all

See also

es_all

Immediate selector for no edges.

og_es_t og_ess_none(void);

An immediate selector is returned by value, owns nothing and is never destroyed.

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_ess_none

In notebooks

Og.Native.og_ess_none

igraph 1.0

igraph_ess_none

See also

es_none

Immediate selector for a single edge.

og_es_t og_ess_1(og_int_t eid);

An immediate selector is returned by value, owns nothing and is never destroyed. The id is checked when used (OG_EINVEID).

Parameters

• eid The edge id.

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_ess_1

In notebooks

Og.Native.og_ess_1

igraph 1.0

igraph_ess_1

See also

es_1

Immediate selector that borrows a vector of edge ids.

og_es_t og_ess_vector(const og_vector_int_t *v);

An immediate selector is returned by value, owns nothing and is never destroyed. v is borrowed: keep it alive while the selector is used.

Parameters

• v Edge ids (borrowed).

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_ess_vector

In notebooks

Og.Native.og_ess_vector

igraph 1.0

igraph_ess_vector

See also

es_vector

Immediate selector for the edge ids start .. end - 1.

og_es_t og_ess_range(og_int_t start, og_int_t end);

An immediate selector is returned by value, owns nothing and is never destroyed. Bounds are checked when used, as for es_range.

Parameters

• start First id.
• end One past the last id.

Returns

The selector.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_ess_range

In notebooks

Og.Native.og_ess_range

igraph 1.0

igraph_ess_range

See also

es_range

The edge ids a selector resolves to, as a vector.

og_error_t og_es_as_vector(
    const og_t *graph,
    og_es_t es,
    og_vector_int_t *v
);

Resolves es against graph and writes the ids to v (resized), in the selector's order.

Parameters

• graph The graph.
• es The selector.
• v Initialised integer vector for the ids.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVEID The selector names an edge outside 0 .. ecount(graph) - 1.
• OG_EINVAL A range selector ends before it starts, or a pairs/path selector names two vertices with no edge between them.
• OG_EINVVID A pairs, path, incident or all-between selector names a vertex that does not exist.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(k) plus resolving the selector.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_as_vector

In notebooks

Og.Native.og_es_as_vector

igraph 1.0

igraph_es_as_vector

See also

eit_create, edges

Copies an edge selector.

og_error_t og_es_copy(og_es_t *dest, const og_es_t *src);

Selectors that own their ids (es_vector_copy, es_pairs, es_pairs_small, es_path) get their own copy of them; the others are copied as they are. Release the copy with es_destroy.

Parameters

• dest Selector to fill.
• src Selector to copy.

Returns

OG_SUCCESS, or OG_ENOMEM.

Errors

• OG_ENOMEM Memory could not be allocated.

Complexity

O(k) for a selector owning k ids, otherwise O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_copy

In notebooks

Og.Native.og_es_copy

igraph 1.0

igraph_es_copy

See also

es_destroy

Frees what an edge selector owns.

void og_es_destroy(og_es_t *es);

Selectors made by es_vector_copy, es_pairs, es_pairs_small and es_path (and copies of them) own memory; for all others this does nothing.

Parameters

• es The selector.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_destroy

In notebooks

Og.Native.og_es_destroy

igraph 1.0

igraph_es_destroy

See also

es_copy

Tells whether a selector is the all-edges selector in id order.

og_bool_t og_es_is_all(const og_es_t *es);

true only for es_all / ess_all with OG_EDGEORDER_ID.

Parameters

• es The selector.

Returns

true or false.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_is_all

In notebooks

Og.Native.og_es_is_all

igraph 1.0

igraph_es_is_all

See also

es_all

The number of edges a selector resolves to in a graph.

og_error_t og_es_size(
    const og_t *graph,
    const og_es_t *es,
    og_int_t *result
);

All (any order), none, single, range, vector, pairs (half the number of ids) and path (one less than the number of vertices) selectors are counted without resolving them and without checking ids. Incident and all-between selectors are resolved, which can fail like eit_create.

Parameters

• graph The graph.
• es The selector.
• result Receives the count.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID An incident or all-between selector names a vertex that does not exist.
• OG_EINVMODE An incident selector has an invalid mode.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(1) for most selectors; O(d) for incident and all-between.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_size

In notebooks

Og.Native.og_es_size

igraph 1.0

igraph_es_size

See also

eit_create

Reports which variant (all, pairs, path, ...) an edge selector is.

og_es_type_t og_es_type(const og_es_t *es);

Returns one of OG_ES_ALL, OG_ES_ALLFROM, OG_ES_ALLTO, OG_ES_INCIDENT, OG_ES_NONE, OG_ES_1, OG_ES_VECTORPTR (borrowed vector), OG_ES_VECTOR (owned vector), OG_ES_RANGE, OG_ES_PAIRS, OG_ES_PATH, OG_ES_ALL_BETWEEN.

Parameters

• es The selector.

Returns

The selector kind.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_es_type

In notebooks

Og.Native.og_es_type

igraph 1.0

igraph_es_type

See also

es_is_all

Resolves a vertex selector against a graph into an iterator.

og_error_t og_vit_create(const og_t *graph, og_vs_t vs, og_vit_t *vit);

Checks the selector's ids against graph and prepares *vit for stepping: OG_VIT_GET(vit) is the current vertex, OG_VIT_NEXT(vit) moves on, OG_VIT_END(vit) becomes true after the last one, OG_VIT_SIZE(vit) is the count and OG_VIT_RESET(vit) starts again. The macros take the iterator itself, not a pointer.

All, single and range selectors and vector selectors are stepped through without copying; adjacency and non-adjacency selectors build their vertex list once here. Release the iterator with vit_destroy.

Parameters

• graph The graph.
• vs The selector.
• vit Iterator to fill.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID The selector names a vertex that does not exist.
• OG_EINVAL A range selector ends before it starts, or the selector kind is unknown.
• OG_EINVMODE An adjacency selector has an invalid mode.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(1) for all, none, single and range; O(k) to check k ids of a vector; O(d) for adjacency; O(|V|) for non-adjacency.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vit_create

In notebooks

Og.Native.og_vit_create

igraph 1.0

igraph_vit_create

See also

vit_destroy, vs_all, eit_create

og_vit_t vit;
og_int_t deg, total = 0;
og_vit_create(&g, og_vss_range(2, 5), &vit);   /* vertices 2, 3 and 4 */
while (!OG_VIT_END(vit)) {
    og_degree_1(&g, &deg, OG_VIT_GET(vit), OG_ALL, OG_LOOPS_TWICE);
    total += deg;
    OG_VIT_NEXT(vit);
}
og_vit_destroy(&vit);   /* in og_small's bow tie, total = 4 + 2 + 2 = 8 */

Releases any id list a vertex iterator built.

void og_vit_destroy(const og_vit_t *vit);

Call it after every successful vit_create. It frees the list built for adjacency and non-adjacency selectors and does nothing for the others. Calling it twice is harmless.

Parameters

• vit The iterator.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_vit_destroy

In notebooks

Og.Native.og_vit_destroy

igraph 1.0

igraph_vit_destroy

See also

vit_create

Resolves an edge selector against a graph into an iterator.

og_error_t og_eit_create(const og_t *graph, og_es_t es, og_eit_t *eit);

Checks the selector against graph and prepares *eit for stepping with OG_EIT_GET, OG_EIT_NEXT, OG_EIT_END, OG_EIT_SIZE and OG_EIT_RESET (they take the iterator itself). Id order, single, range and vector selectors are stepped without copying; the other kinds build their edge list once here. Release with eit_destroy.

Parameters

• graph The graph.
• es The selector.
• eit Iterator to fill.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVEID The selector names an edge outside 0 .. ecount(graph) - 1.
• OG_EINVAL A range selector ends before it starts, or a pairs/path selector names two vertices with no edge between them.
• OG_EINVVID A pairs, path, incident or all-between selector names a vertex that does not exist.
• OG_ENOMEM Memory could not be allocated.
• OG_EINVMODE An incident selector has an invalid mode.

Complexity

O(1) for id order, single and range; O(k) for k vector ids; O(|E|) for the FROM/TO orders; O(d) for incident; O(k log d) for pairs and paths.

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_eit_create

In notebooks

Og.Native.og_eit_create

igraph 1.0

igraph_eit_create

See also

eit_destroy, es_all, vit_create

Releases any id list an edge iterator built.

void og_eit_destroy(const og_eit_t *eit);

Call it after every successful eit_create. Calling it twice is harmless.

Parameters

• eit The iterator.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests in tests/foundation/iterators.c.

C name

og_eit_destroy

In notebooks

Og.Native.og_eit_destroy

igraph 1.0

igraph_eit_destroy

See also

eit_create

Function type for the routine that receives every reported error.

typedef void og_error_handler_t(
    const char *reason,
    const char *file,
    int line,
    og_error_t og_errno
);

An error handler receives a reason text, the source file and line where the error was raised, and the error code. Open Graph calls the installed handler once where an error starts (with the reason) and once more for every function the error passes on its way up (through OG_CHECK, with an empty reason).

A handler either never returns (abort, longjmp) or returns after running the cleanup stack, as error_handler_ignore does, so that the error code reaches the caller. One handler serves the whole process.

Parameters

• reason Text describing the error; empty for the reports made while an error travels up.
• file Source file where the error was raised.
• line Line in that file.
• og_errno The error code.

Checked

Unit tests in tests/foundation/error.c.

C name

og_error_handler_t

In notebooks

Og.ErrorHandler

igraph 1.0

igraph_error_handler_t

See also

set_error_handler, error_handler_abort, error_handler_ignore, error_handler_printignore

The default error handler: prints the error and stops the process.

OG_NORETURN void og_error_handler_abort(
    const char *reason,
    const char *file,
    int line,
    og_error_t og_errno
);

Writes "Open Graph error at <file>:<line>: <reason> (<code text>)" to stderr and calls abort(). It stays installed until set_error_handler installs another. Programs that check return codes (OpenBI, the test framework) install error_handler_ignore instead.

Parameters

• reason Text describing the error; empty for the reports made while an error travels up.
• file Source file where the error was raised.
• line Line in that file.
• og_errno The error code.

Returns

Does not return.

Checked

Unit tests in tests/foundation/error.c.

C name

og_error_handler_abort

In notebooks

Og.Native.og_error_handler_abort

igraph 1.0

igraph_error_handler_abort

See also

set_error_handler, error_handler_ignore

Error handler that frees the failing call's temporary objects and lets the error code reach the caller.

void og_error_handler_ignore(
    const char *reason,
    const char *file,
    int line,
    og_error_t og_errno
);

Runs the cleanup stack: every object registered with OG_FINALLY since the innermost OG_FINALLY_ENTER is destroyed, newest first. Nothing is printed. The failing function then returns its code, and so does every caller on the way up.

Install it with set_error_handler when your program checks the codes Open Graph returns.

Parameters

• reason Text describing the error; empty for the reports made while an error travels up.
• file Source file where the error was raised.
• line Line in that file.
• og_errno The error code.

Returns

Nothing.

Checked

Unit tests in tests/foundation/error.c.

C name

og_error_handler_ignore

In notebooks

Og.Native.og_error_handler_ignore

igraph 1.0

igraph_error_handler_ignore

See also

set_error_handler, error_handler_printignore, strerror

og_t g;
og_error_t err;
og_set_error_handler(og_error_handler_ignore);
err = og_empty(&g, -1, OG_DIRECTED);
if (err != OG_SUCCESS) {
    fprintf(stderr, "og_empty failed: %s\n", og_strerror(err));   /* Invalid argument value */
}

Like error_handler_ignore, but prints the error first.

void og_error_handler_printignore(
    const char *reason,
    const char *file,
    int line,
    og_error_t og_errno
);

Writes "Open Graph error at <file>:<line>: <reason> (<code text>)" to stderr once, where the error started (the reports made while the error travels up have an empty reason and print nothing), then runs the cleanup stack and returns.

Parameters

• reason Text describing the error; empty for the reports made while an error travels up.
• file Source file where the error was raised.
• line Line in that file.
• og_errno The error code.

Returns

Nothing.

Checked

Unit tests in tests/foundation/error.c.

C name

og_error_handler_printignore

In notebooks

Og.Native.og_error_handler_printignore

igraph 1.0

igraph_error_handler_printignore

See also

error_handler_ignore, set_error_handler

The return type of every Open Graph function that can fail.

typedef og_error_type_t og_error_t;

A typedef of error_type_t. OG_SUCCESS (0) means success; every other value names the failure. The numeric values are igraph 1.0's, so code that compares error numbers keeps working after renaming igraph_ to og_.

Checked

Unit tests: every code with its numeric value.

C name

og_error_t

In notebooks

Og.Error

igraph 1.0

igraph_error_t

See also

error_type_t, strerror

The enumeration of Open Graph's error codes.

typedef enum og_error_type_t { OG_SUCCESS = 0, OG_FAILURE = 1, OG_ENOMEM = 2, OG_PARSEERROR = 3, OG_EINVAL = 4, OG_EXISTS = 5, OG_EINVVID = 7, OG_EINVEID = 8, OG_EINVMODE = 9, OG_EFILE = 10, OG_UNIMPLEMENTED = 12, OG_INTERRUPTED = 13, OG_DIVERGED = 14, OG_EARPACK = 15, OG_ENEGCYCLE = 37, OG_EINTERNAL = 38, OG_EATTRCOMBINE = 52, OG_EOVERFLOW = 55, OG_EUNDERFLOW = 58, OG_ERWSTUCK = 59, OG_STOP = 60, OG_ERANGE = 61, OG_ENOSOL = 62 } og_error_type_t;

OG_SUCCESS 0; OG_FAILURE 1 (unspecified failure); OG_ENOMEM 2 (out of memory); OG_PARSEERROR 3 (unreadable input); OG_EINVAL 4 (invalid argument); OG_EXISTS 5 (attribute name taken); OG_EINVVID 7 (no such vertex); OG_EINVEID 8 (no such edge); OG_EINVMODE 9 (bad mode argument); OG_EFILE 10 (file operation failed); OG_UNIMPLEMENTED 12; OG_INTERRUPTED 13; OG_DIVERGED 14 (an iteration did not converge); OG_EARPACK 15 (eigensolver failure; also spelled OG_ARPACK); OG_ENEGCYCLE 37 (negative cycle); OG_EINTERNAL 38 (a bug in Open Graph); OG_EATTRCOMBINE 52; OG_EOVERFLOW 55; OG_EUNDERFLOW 58; OG_ERWSTUCK 59 (a random walk cannot continue); OG_STOP 60 (a callback asked to stop; not an error); OG_ERANGE 61 (too many vertices or edges); OG_ENOSOL 62 (no solution).

The numbers are igraph 1.0's; the missing numbers are codes igraph no longer uses.

Checked

Unit tests: every code with its numeric value.

C name

og_error_type_t

In notebooks

Og.Error

igraph 1.0

igraph_error_type_t

See also

error_t, strerror

A short English text for an error code.

const char *og_strerror(const og_error_t og_errno);

Returns a constant string such as "Out of memory" or "Vertex ID out of range"; never NULL, never to be freed. An unknown code gives "Unknown error code". The texts are Open Graph's own.

Parameters

• og_errno The error code.

Returns

The text.

Complexity

O(1).

Checked

Unit tests: a text for every code.

C name

og_strerror

In notebooks

Og.Native.og_strerror

igraph 1.0

igraph_strerror

See also

error_type_t

Function type for the routine that receives warnings.

typedef void og_warning_handler_t(
    const char *reason,
    const char *file,
    int line
);

A warning handler receives the warning text and the file and line where it was raised. A warning reports something worth knowing that is not an error (for example a result of limited accuracy); the computation continues after the handler returns.

Parameters

• reason The warning text.
• file Source file where the warning was raised.
• line Line in that file.

Checked

Unit tests in tests/foundation/error.c.

C name

og_warning_handler_t

In notebooks

Og.WarningHandler

igraph 1.0

igraph_warning_handler_t

See also

set_warning_handler, warning_handler_print, warning_handler_ignore

Chooses which routine receives warnings, for the whole process.

og_warning_handler_t *og_set_warning_handler(
    og_warning_handler_t *new_handler
);

Returns the handler installed before. NULL removes the handler, after which warnings are dropped. The default is warning_handler_print.

Warnings can be raised on Open Graph's worker threads when threads are on (set_num_threads above 1), so a custom handler must then be thread-safe.

Parameters

• new_handler The handler, or NULL for none.

Returns

The previous handler.

Complexity

O(1).

Checked

Unit tests in tests/foundation/error.c.

C name

og_set_warning_handler

In notebooks

Og.Native.og_set_warning_handler

igraph 1.0

igraph_set_warning_handler

See also

warning_handler_t, warning

Passes a warning message to the installed warning handler.

void og_warning(const char *reason, const char *file, int line);

Passes reason, file and line to the installed warning handler, if there is one. Library code uses the macro OG_WARNING(reason), which fills in __FILE__ and __LINE__.

Parameters

• reason The warning text.
• file Source file.
• line Line in the file.

Returns

Nothing.

Checked

Unit tests in tests/foundation/error.c.

C name

og_warning

In notebooks

Og.Native.og_warning

igraph 1.0

igraph_warning

See also

warningf, set_warning_handler

Raises a warning with a printf-style message.

void og_warningf(const char *reason, const char *file, int line, ...);

Formats reason with the extra arguments into a per-thread buffer of 2048 bytes (longer messages are cut) and calls warning. The macro OG_WARNINGF(format, ...) fills in the file and line.

Parameters

• reason printf format string.
• file Source file.
• line Line in the file.
• ... Values for the format.

Returns

Nothing.

Checked

Unit tests in tests/foundation/error.c.

C name

og_warningf

igraph 1.0

igraph_warningf

See also

warning

Warning handler that does nothing.

void og_warning_handler_ignore(
    const char *reason,
    const char *file,
    int line
);

Install it with set_warning_handler to silence warnings while keeping a handler installed (NULL has the same effect).

Parameters

• reason Ignored.
• file Ignored.
• line Ignored.

Returns

Nothing.

Checked

Unit tests in tests/foundation/error.c.

C name

og_warning_handler_ignore

In notebooks

Og.Native.og_warning_handler_ignore

igraph 1.0

igraph_warning_handler_ignore

See also

set_warning_handler, warning_handler_print

The default warning handler: prints the warning to stderr.

void og_warning_handler_print(
    const char *reason,
    const char *file,
    int line
);

Writes "Open Graph warning at <file>:<line>: <reason>" to stderr and returns.

Parameters

• reason The warning text.
• file Source file.
• line Line in the file.

Returns

Nothing.

Checked

Unit tests in tests/foundation/error.c.

C name

og_warning_handler_print

In notebooks

Og.Native.og_warning_handler_print

igraph 1.0

igraph_warning_handler_print

See also

set_warning_handler, warning_handler_ignore

Installs the process-wide error handler.

og_error_handler_t *og_set_error_handler(og_error_handler_t *new_handler);

Returns the handler installed before. NULL restores the default, error_handler_abort. The handler is shared by the whole process: install it before other threads start calling Open Graph.

Parameters

• new_handler The handler, or NULL for the default.

Returns

The previous handler.

Complexity

O(1).

Checked

Unit tests in tests/foundation/error.c.

C name

og_set_error_handler

In notebooks

Og.Native.og_set_error_handler

igraph 1.0

igraph_set_error_handler

See also

error_handler_t, error_handler_ignore, error_handler_abort

Hands an error code and message to the current error handler.

og_error_t og_error(
    const char *reason,
    const char *file,
    int line,
    og_error_t og_errno
);

Calls the error handler with reason, file, line and code and, if the handler returns, returns the code. Library code (and callbacks or extensions written in the same style) uses the macros: OG_ERROR(reason, code) reports and returns the code from the current function; OG_CHECK(expr) passes the code of a failed call upward; OG_CHECK_OOM(ptr, reason) reports OG_ENOMEM for a NULL allocation.

Parameters

• reason What went wrong.
• file Source file.
• line Line in the file.
• og_errno The error code.

Returns

og_errno.

Checked

Unit tests in tests/foundation/error.c.

C name

og_error

In notebooks

Og.Native.og_error

igraph 1.0

igraph_error

See also

errorf, set_error_handler

Reports an error with a printf-style message.

og_error_t og_errorf(
    const char *reason,
    const char *file,
    int line,
    og_error_t og_errno,
    ...
);

Formats reason with the extra arguments into a per-thread buffer of 2048 bytes (longer messages are cut) and calls error. The macro OG_ERRORF(format, code, ...) fills in the file and line and returns the code.

Parameters

• reason printf format string.
• file Source file.
• line Line in the file.
• og_errno The error code.
• ... Values for the format.

Returns

og_errno.

Checked

Unit tests in tests/foundation/error.c.

C name

og_errorf

igraph 1.0

igraph_errorf

See also

error

Function type for the routine called on unrecoverable internal failures.

typedef void og_fatal_handler_t(
    const char *reason,
    const char *file,
    int line
);

Called for conditions that must never happen, such as a broken internal invariant or an overflowing cleanup stack. Invalid input is never fatal: it is an ordinary error. A fatal handler must not return: it aborts the process or jumps out with longjmp.

Parameters

• reason Description of the condition.
• file Source file.
• line Line in the file.

Checked

Unit tests in tests/foundation/error.c.

C name

og_fatal_handler_t

In notebooks

Og.FatalHandler

igraph 1.0

igraph_fatal_handler_t

See also

set_fatal_handler, fatal

Replaces the routine fatal calls, for the whole process.

og_fatal_handler_t *og_set_fatal_handler(og_fatal_handler_t *new_handler);

Returns the handler installed before. NULL removes the handler; fatal then prints and aborts by itself.

Parameters

• new_handler The handler, or NULL.

Returns

The previous handler.

Complexity

O(1).

Checked

Unit tests in tests/foundation/error.c.

C name

og_set_fatal_handler

In notebooks

Og.Native.og_set_fatal_handler

igraph 1.0

igraph_set_fatal_handler

See also

fatal_handler_t, fatal_handler_abort

The default fatal-error handler: prints the message and aborts.

OG_NORETURN void og_fatal_handler_abort(
    const char *reason,
    const char *file,
    int line
);

Writes "Open Graph fatal error at <file>:<line>: <reason>" to stderr and calls abort().

Parameters

• reason Description.
• file Source file.
• line Line in the file.

Returns

Does not return.

Checked

Unit tests in tests/foundation/error.c.

C name

og_fatal_handler_abort

In notebooks

Og.Native.og_fatal_handler_abort

igraph 1.0

igraph_fatal_handler_abort

See also

set_fatal_handler, fatal

Stops on an unrecoverable condition through the fatal handler; never returns.

OG_NORETURN void og_fatal(const char *reason, const char *file, int line);

Calls the installed fatal handler. If none is installed, or the handler returns after all, the message is printed and the process aborts. The macros OG_FATAL(reason) and OG_ASSERT(condition) use it; OG_ASSERT stays active in release builds (also with NDEBUG).

Parameters

• reason Description.
• file Source file.
• line Line in the file.

Returns

Does not return.

Checked

Unit tests in tests/foundation/error.c.

C name

og_fatal

In notebooks

Og.Native.og_fatal

igraph 1.0

igraph_fatal

See also

fatalf, set_fatal_handler

Reports a fatal error with a printf-style message; never returns.

OG_NORETURN void og_fatalf(
    const char *reason,
    const char *file,
    int line,
    ...
);

Formats the message into a per-thread buffer of 2048 bytes and calls fatal. The macro OG_FATALF(format, ...) fills in the file and line.

Parameters

• reason printf format string.
• file Source file.
• line Line in the file.
• ... Values for the format.

Returns

Does not return.

Checked

Unit tests in tests/foundation/error.c.

C name

og_fatalf

igraph 1.0

igraph_fatalf

See also

fatal

Allocates memory the way Open Graph does.

void *og_malloc(size_t size);

A wrapper of the C library's malloc. A request for zero bytes still returns a valid block that free accepts.

Memory that Open Graph frees on your behalf (for example the items vector_ptr_free_all releases) must come from malloc, calloc or realloc, and memory Open Graph hands you to release goes back through free, so that one allocator handles both sides (on Windows a library and a program can use different C runtimes). Test builds count every block and can make chosen allocations fail.

Parameters

• size Number of bytes.

Returns

The block, or NULL when memory is short.

Complexity

That of the C library's malloc.

Checked

Unit tests in tests/foundation/memory.c (block counting and injected allocation failures).

C name

og_malloc

In notebooks

Og.Native.og_malloc

igraph 1.0

igraph_malloc

See also

calloc, realloc, free

Allocates zero-filled memory for an array.

void *og_calloc(size_t count, size_t size);

A wrapper of calloc: count * size bytes, all zero. A count or size of 0 still returns a valid block.

Memory that Open Graph frees on your behalf (for example the items vector_ptr_free_all releases) must come from malloc, calloc or realloc, and memory Open Graph hands you to release goes back through free, so that one allocator handles both sides (on Windows a library and a program can use different C runtimes). Test builds count every block and can make chosen allocations fail.

Parameters

• count Number of elements.
• size Bytes per element.

Returns

The block, or NULL when memory is short.

Complexity

O(count * size).

Checked

Unit tests in tests/foundation/memory.c (block counting and injected allocation failures).

C name

og_calloc

In notebooks

Og.Native.og_calloc

igraph 1.0

igraph_calloc

See also

malloc, free

Changes the size of a block from malloc, calloc or realloc.

void *og_realloc(void *ptr, size_t size);

A wrapper of realloc. ptr NULL allocates a new block. A size of 0 keeps a valid small block instead of freeing. On failure NULL is returned and the old block is left intact.

Parameters

• ptr The block, or NULL.
• size New size in bytes.

Returns

The (possibly moved) block, or NULL when memory is short.

Complexity

That of the C library's realloc.

Checked

Unit tests in tests/foundation/memory.c (block counting and injected allocation failures).

C name

og_realloc

In notebooks

Og.Native.og_realloc

igraph 1.0

igraph_realloc

See also

malloc, free

Frees a block from malloc, calloc or realloc.

void og_free(void *ptr);

NULL is ignored.

Parameters

• ptr The block, or NULL.

Returns

Nothing.

Complexity

That of the C library's free.

Checked

Unit tests in tests/foundation/memory.c (block counting and injected allocation failures).

C name

og_free

In notebooks

Og.Native.og_free

igraph 1.0

igraph_free

See also

malloc

Returns the generator that randomised functions use on this thread.

og_rng_t *og_rng_default(void);

Every randomised function in Open Graph draws from this generator. Each thread has its own: a PCG32 generator, created on first use and seeded from the clock mixed with the thread's address, so two threads never share a stream. PCG32 is what igraph 1.0 really uses by default (its manual's text names MT19937).

Seed it with rng_seed(rng_default(), seed) for reproducible results; one seed gives the same results on Windows and macOS.

Returns

The generator (never NULL).

Complexity

O(1).

Checked

Unit tests; the default is per thread and is PCG32, as igraph 1.0 really uses.

C name

og_rng_default

In notebooks

Og.Native.og_rng_default

igraph 1.0

igraph_rng_default

See also

rng_seed, rng_set_default, rngtype_pcg32

og_rng_seed(og_rng_default(), 42);
og_int_t die = og_rng_get_integer(og_rng_default(), 1, 6);
og_real_t u = og_rng_get_unif01(og_rng_default());
printf("%" OG_PRId " %g\n", die, u);

Makes another generator the calling thread's default.

og_rng_t *og_rng_set_default(og_rng_t *rng);

Returns the previous default. rng must stay initialised and alive while it is the default. NULL changes nothing and just returns the current default. Other threads are not affected.

Parameters

• rng The new default generator, or NULL.

Returns

The previous default generator.

Complexity

O(1).

Checked

Unit tests; the default is per thread.

C name

og_rng_set_default

In notebooks

Og.Native.og_rng_set_default

igraph 1.0

igraph_rng_set_default

See also

rng_default, rng_init

Creates a generator of a given type.

og_error_t og_rng_init(og_rng_t *rng, const og_rng_type_t *type);

type is rngtype_mt19937, rngtype_glibc2, rngtype_pcg32, rngtype_pcg64 or a table of your own (only name, bits, init, destroy, seed and get are required; distribution hooks left NULL use Open Graph's generic samplers). The new generator starts in its type's state for seed 0; call rng_seed. Free it with rng_destroy.

Parameters

• rng Generator object to initialise.
• type The generator type.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL type is NULL or its bits field is outside 1 .. 64.
• OG_ENOMEM Memory could not be allocated.

Complexity

O(state size): O(624) words for MT19937, O(1) for the others.

Checked

Unit tests in tests/foundation/random.c.

C name

og_rng_init

In notebooks

Og.Native.og_rng_init

igraph 1.0

igraph_rng_init

See also

rng_destroy, rng_seed, rng_set_default

Frees a generator's state.

void og_rng_destroy(og_rng_t *rng);

Do not destroy a generator while it is some thread's default.

Parameters

• rng The generator.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests in tests/foundation/random.c.

C name

og_rng_destroy

In notebooks

Og.Native.og_rng_destroy

igraph 1.0

igraph_rng_destroy

See also

rng_init

Restarts a generator's stream from a given seed value.

og_error_t og_rng_seed(og_rng_t *rng, og_uint_t seed);

What the seed does depends on the type. MT19937: the authors' 2002 initialisation with the low 32 bits (0 means 4357). GLIBC2: glibc's srandom with the low 32 bits (0 means 1). PCG32: O'Neill's reference seeding with PCG's default initial state 0x853c49e6748fea9b and the seed as the stream number, which is how igraph 1.0 seeds it (found by black-box observation); a seed and the same seed with its top bit flipped give the same stream. PCG64: stream 54, the seed added to the state.

For PCG32 the seeding, rng_get_integer and rng_get_unif01 follow what black-box tests of igraph 1.0 showed, so a function that draws the same numbers in the same order as igraph gives igraph's answer for the same seed.

Parameters

• rng The generator.
• seed The seed.

Returns

OG_SUCCESS (the built-in types cannot fail).

Complexity

O(1): a fixed number of steps (a few hundred for MT19937 and GLIBC2).

Checked

Unit tests against published reference streams for each type.

C name

og_rng_seed

In notebooks

Og.Native.og_rng_seed

igraph 1.0

igraph_rng_seed

See also

rng_default, rng_init

og_rng_t rng;
og_rng_init(&rng, &og_rngtype_mt19937);
og_rng_seed(&rng, 5489);
printf("%g\n", og_rng_get_unif01(&rng));
og_rng_destroy(&rng);

How many bits one raw draw of the generator holds.

og_int_t og_rng_bits(const og_rng_t *rng);

32 for MT19937 and PCG32, 31 for GLIBC2, 64 for PCG64.

Parameters

• rng The generator.

Returns

The bit count.

Complexity

O(1).

Checked

Unit tests in tests/foundation/random.c.

C name

og_rng_bits

In notebooks

Og.Native.og_rng_bits

igraph 1.0

igraph_rng_bits

See also

rng_max

The largest raw value the generator produces.

og_uint_t og_rng_max(const og_rng_t *rng);

2^bits - 1, so OG_UINT_MAX for PCG64.

Parameters

• rng The generator.

Returns

The largest raw value.

Complexity

O(1).

Checked

Unit tests in tests/foundation/random.c.

C name

og_rng_max

In notebooks

Og.Native.og_rng_max

igraph 1.0

igraph_rng_max

See also

rng_bits

The name of the generator's type.

const char *og_rng_name(const og_rng_t *rng);

"MT19937", "LIBC", "PCG32" or "PCG64" for the built-in types. The string belongs to the type: do not free it.

Parameters

• rng The generator.

Returns

The name.

Complexity

O(1).

Checked

Unit tests in tests/foundation/random.c.

C name

og_rng_name

In notebooks

Og.Native.og_rng_name

igraph 1.0

igraph_rng_name

See also

rng_init

A random true or false, each with probability one half.

og_bool_t og_rng_get_bool(og_rng_t *rng);

Uses one bit: the top bit of one raw draw.

Parameters

• rng The generator.

Returns

true or false.

Complexity

O(1).

Checked

Uniformity checked (chi-square, moments) for all four generators.

C name

og_rng_get_bool

In notebooks

Og.Native.og_rng_get_bool

igraph 1.0

igraph_rng_get_bool

See also

rng_get_integer

A uniform random integer between l and h, both included.

og_int_t og_rng_get_integer(og_rng_t *rng, og_int_t l, og_int_t h);

h <= l returns l without drawing. Ranges of up to 2^32 values use Lemire's nearly divisionless method on one 32-bit word per try; a word is drawn again only in the rare rejected case. This is how igraph 1.0 turns words into integers (249 of 249 black-box probes agreed), so a seeded PCG32 picks igraph's values. Wider ranges use 64-bit words. A generator type with its own get_int hook uses that instead.

Parameters

• rng The generator.
• l Lower bound.
• h Upper bound.

Returns

The integer.

Complexity

O(1) expected.

Checked

Same values as igraph 1.0 for ranges up to 2^32 (black-box probes); uniformity checked with chi-square tests for all four generators.

C name

og_rng_get_integer

In notebooks

Og.Native.og_rng_get_integer

igraph 1.0

igraph_rng_get_integer

See also

rng_get_unif01, rng_seed

A uniform random real in [0, 1).

og_real_t og_rng_get_unif01(og_rng_t *rng);

53 random bits divided by 2^53, so every value is a multiple of 2^-53. With a 32-bit generator the bits come from two words, the first one giving the high bits: the layout observed in igraph 1.0.

Parameters

• rng The generator.

Returns

The real.

Complexity

O(1).

Checked

Uniformity checked (chi-square, moments) for all four generators; the bit layout is the one black-box tests of igraph 1.0 showed.

C name

og_rng_get_unif01

In notebooks

Og.Native.og_rng_get_unif01

igraph 1.0

igraph_rng_get_unif01

See also

rng_get_unif, rng_get_integer

A uniform random real in [l, h).

og_real_t og_rng_get_unif(og_rng_t *rng, og_real_t l, og_real_t h);

Computed as l + (h - l) * rng_get_unif01(rng); h == l returns l without drawing.

Parameters

• rng The generator.
• l Lower bound.
• h Upper bound.

Returns

The real.

Complexity

O(1).

Checked

Uniformity checked (chi-square, moments) for all four generators.

C name

og_rng_get_unif

In notebooks

Og.Native.og_rng_get_unif

igraph 1.0

igraph_rng_get_unif

See also

rng_get_unif01

A normally distributed random real with mean m and standard deviation s.

og_real_t og_rng_get_normal(og_rng_t *rng, og_real_t m, og_real_t s);

Marsaglia and Bray's polar method (1964) gives a standard normal z; the result is m + s z. s = 0 returns m.

Parameters

• rng The generator.
• m Mean.
• s Standard deviation.

Returns

The real.

Complexity

O(1) expected.

Checked

Mean and variance over 200,000 draws and chi-square fits with fixed seeds, for all four generators. Open Graph's own sampler: a seed does not give igraph's exact draws.

C name

og_rng_get_normal

In notebooks

Og.Native.og_rng_get_normal

igraph 1.0

igraph_rng_get_normal

See also

rng_get_gamma

An exponentially distributed random real with the given rate.

og_real_t og_rng_get_exp(og_rng_t *rng, og_real_t rate);

The mean is 1 / rate. Drawn by inversion, -log(U) / rate with U in (0, 1]. rate 0 gives +infinity; a negative or NaN rate gives NaN.

Parameters

• rng The generator.
• rate Rate, 0 or more.

Returns

The real.

Complexity

O(1).

Checked

Mean and variance over 200,000 draws and chi-square fits with fixed seeds, for all four generators. Open Graph's own sampler: a seed does not give igraph's exact draws.

C name

og_rng_get_exp

In notebooks

Og.Native.og_rng_get_exp

igraph 1.0

igraph_rng_get_exp

See also

rng_get_gamma, rng_get_geom

A gamma-distributed random real with the given shape and scale.

og_real_t og_rng_get_gamma(og_rng_t *rng, og_real_t shape, og_real_t scale);

Marsaglia and Tsang's method (2000); for shape below 1, a draw for shape + 1 is multiplied by U^(1/shape). The mean is shape * scale. A shape or scale that is not positive, or NaN, gives NaN.

Parameters

• rng The generator.
• shape Shape, above 0.
• scale Scale, above 0.

Returns

The real.

Complexity

O(1) expected.

Checked

Mean and variance over 200,000 draws and chi-square fits with fixed seeds, for all four generators. Open Graph's own sampler: a seed does not give igraph's exact draws.

C name

og_rng_get_gamma

In notebooks

Og.Native.og_rng_get_gamma

igraph 1.0

igraph_rng_get_gamma

See also

rng_get_normal, rng_get_exp

A binomial random count: successes in n independent trials of probability p.

og_real_t og_rng_get_binom(og_rng_t *rng, og_int_t n, og_real_t p);

Returned as a real. While n p is 30 or more, Knuth's splitting by beta-distributed order statistics reduces the problem; the rest is drawn by inverting the distribution function. A p above 0.5 is drawn as n minus a draw for 1 - p. n = 0 or p = 0 gives 0, p = 1 gives n; n below 0 or p outside [0, 1] gives NaN.

Parameters

• rng The generator.
• n Number of trials.
• p Success probability.

Returns

The count, as a real.

Complexity

O(log n) splitting steps, then O(1 + n p) expected for the inversion (n p is below 30 by then).

Checked

Mean and variance over 200,000 draws and chi-square fits with fixed seeds, for all four generators. Open Graph's own sampler: a seed does not give igraph's exact draws.

C name

og_rng_get_binom

In notebooks

Og.Native.og_rng_get_binom

igraph 1.0

igraph_rng_get_binom

See also

rng_get_pois

A geometric random count: failures before the first success, with success probability p.

og_real_t og_rng_get_geom(og_rng_t *rng, og_real_t p);

Takes the values 0, 1, 2, ... with probability (1 - p)^k p; the mean is (1 - p) / p. Drawn by inversion. p = 1 gives 0; p outside (0, 1] or NaN gives NaN.

Parameters

• rng The generator.
• p Success probability, in (0, 1].

Returns

The count, as a real.

Complexity

O(1).

Checked

Mean and variance over 200,000 draws and chi-square fits with fixed seeds, for all four generators. Open Graph's own sampler: a seed does not give igraph's exact draws.

C name

og_rng_get_geom

In notebooks

Og.Native.og_rng_get_geom

igraph 1.0

igraph_rng_get_geom

See also

rng_get_exp

A Poisson random count with the given mean.

og_real_t og_rng_get_pois(og_rng_t *rng, og_real_t rate);

Returned as a real. Means above 30 are reduced with Knuth's gamma splitting; small means multiply uniforms until the product drops below exp(-rate). rate 0 gives 0, +infinity gives +infinity, a negative or NaN rate gives NaN.

Parameters

• rng The generator.
• rate Mean, 0 or more.

Returns

The count, as a real.

Complexity

O(log rate) splitting steps for large means, then O(1 + rate) expected for the rest (rate is at most 30 by then).

Checked

Mean and variance over 200,000 draws and chi-square fits with fixed seeds, for all four generators. Open Graph's own sampler: a seed does not give igraph's exact draws.

C name

og_rng_get_pois

In notebooks

Og.Native.og_rng_get_pois

igraph 1.0

igraph_rng_get_pois

See also

rng_get_binom

Generator type: the Mersenne Twister MT19937, 32 bits per draw.

extern const og_rng_type_t og_rngtype_mt19937;

Matsumoto and Nishimura (1998) with the authors' 2002 seeding. Pass &rngtype_mt19937 to rng_init.

Checked

Matches the published reference outputs: seed 5489 starts 3499211612 and the 10000th output is 4123659995; seed 0 means 4357.

C name

og_rngtype_mt19937

In notebooks

Og.Native.og_rngtype_mt19937

igraph 1.0

igraph_rngtype_mt19937

See also

rng_init, rngtype_pcg32

Generator type: the additive feedback generator behind glibc's random(), 31 bits per draw.

extern const og_rng_type_t og_rngtype_glibc2;

r[i] = r[i-3] + r[i-31] modulo 2^32, seeded by the 16807 linear congruential generator, the first 310 values thrown away, output r >> 1 (as described by Selinger, 2007). Its name is "LIBC".

Checked

Matches glibc random() after srandom(1): 1804289383, 846930886, ...

C name

og_rngtype_glibc2

In notebooks

Og.Native.og_rngtype_glibc2

igraph 1.0

igraph_rngtype_glibc2

See also

rng_init

Generator type: PCG32 (XSH-RR 64/32), the default generator.

extern const og_rng_type_t og_rngtype_pcg32;

O'Neill (2014). Seeded the way igraph 1.0 seeds it: PCG's default initial state with the seed as the stream number.

Checked

Seed 42 starts 0x2324ffe8, checked against an independent Python implementation that also reproduces the pcg-c demo stream.

C name

og_rngtype_pcg32

In notebooks

Og.Native.og_rngtype_pcg32

igraph 1.0

igraph_rngtype_pcg32

See also

rng_default, rng_seed

Generator type: PCG64 (XSL-RR 128/64), 64 bits per draw.

extern const og_rng_type_t og_rngtype_pcg64;

O'Neill (2014), stream 54. The 128-bit state arithmetic is done on 64-bit halves, so it also builds with MSVC.

Checked

Seed 42 starts 0x86b1da1d72062b68; the pcg-c demo stream (initstate 42, sequence 54) is reproduced.

C name

og_rngtype_pcg64

In notebooks

Og.Native.og_rngtype_pcg64

igraph 1.0

igraph_rngtype_pcg64

See also

rng_init