Components and structure

Connectivity and components, cut vertices and bridges, percolation, spanning trees, self-loops and multi-edges, cores and trusses, density and degree summaries, and the graph as a matrix.

50 entries: 48 functions and 2 types. Part of the Open Graph reference; All functions lists every entry on one page, with a filter. The badges say how each entry is checked.

Types

`loops_t`type#

Exact

Tells a function how to count self-loops.

typedef enum og_loops_t {
    OG_NO_LOOPS = 0,
    OG_LOOPS_TWICE = 1,
    OG_LOOPS_ONCE = 2,
    OG_LOOPS = OG_LOOPS_TWICE
} og_loops_t;

OG_NO_LOOPS (0): self-loops are left out. OG_LOOPS_TWICE (1): an undirected self-loop counts twice, once per end, the convention under which degrees and adjacency row sums agree. OG_LOOPS_ONCE (2): a self-loop counts once. OG_LOOPS is another name for OG_LOOPS_TWICE. In directed graphs a self-loop has one out-end and one in-end, so it adds 1 to an out- or in-count either way.

Declared by the foundation (og/foundation/types.h) and used across the library, for example by get_adjacency() and degree().

Checked: Same values as igraph 1.0.
C name: og_loops_t
In notebooks: Og.Loops
igraph 1.0: igraph_loops_t
See also: get_adjacency, get_adjacency_sparse, degree

`neimode_t`type#

Exact

Chooses which edges of a directed graph a function follows.

typedef enum og_neimode_t {
    OG_OUT = 1,
    OG_IN = 2,
    OG_ALL = 3
} og_neimode_t;

OG_OUT (1): the edges leaving a vertex (successors, out-degree). OG_IN (2): the edges arriving at it (predecessors, in-degree). OG_ALL (3): both, directions ignored. In undirected graphs every function treats the three alike. Functions that take a mode report OG_EINVMODE for any other value.

Declared by the foundation (og/foundation/types.h) and used across the library.

Checked: Same values as igraph 1.0.
C name: og_neimode_t
In notebooks: Og.Neimode
igraph 1.0: igraph_neimode_t
See also: subcomponent, coreness, degree, neighbors

Adjacency and reachability

`are_adjacent`#

Exact

Tells whether there is an edge from one vertex to another.

og_error_t og_are_adjacent(
    const og_t *graph,
    og_int_t v1,
    og_int_t v2,
    og_bool_t *res
);

Sets res to true when the graph has at least one edge from v1 to v2. In a directed graph the direction counts: an edge 1 -> 0 does not make 0 adjacent to 1. In an undirected graph the order of v1 and v2 does not matter. v1 equal to v2 asks for a self-loop.

The search is a binary search in the sorted adjacency of the graph, done on the shorter of the two lists that can hold the edge (the out-list of v1 or the in-list of v2).

Parameters

graph The input graph; it is not changed.
v1 The first vertex (the tail in a directed graph).
v2 The second vertex (the head in a directed graph).
res Receives true when the edge exists.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVVID v1 or v2 is not a vertex of the graph.

Complexity

O(log d), d the length of the shorter of the two adjacency lists searched.

Checked

Identical to igraph 1.0 on 280 random graphs (python-igraph as oracle).

C name

og_are_adjacent

In notebooks

Og.AreAdjacent

igraph 1.0

igraph_are_adjacent

og_t g;
og_bool_t a, b;
og_small(&g, 3, OG_DIRECTED, 0,1, 1,2, -1);
og_are_adjacent(&g, 0, 1, &a);   /* true */
og_are_adjacent(&g, 1, 0, &b);   /* false: wrong direction */
og_destroy(&g);

`spanner`#

Same quality

Picks a sparse subset of edges that keeps every distance within a stretch factor.

og_error_t og_spanner(
    const og_t *graph,
    og_vector_int_t *spanner,
    og_real_t stretch,
    const og_vector_t *weights
);

Returns the ids of edges forming a spanner H of the graph: for every pair of vertices the distance in H is at most stretch times the distance in the graph. Distances use the edge weights, or 1 per edge when weights is NULL. Edge directions are ignored and self-loops are never chosen.

The method is the randomized clustering algorithm of Baswana and Sen (2007). With k = floor((stretch + 1) / 2), capped at 64, it runs k - 1 clustering rounds and a final joining round and returns a (2k - 1)-spanner with an expected O(k n^(1 + 1/k)) edges. The cap changes nothing in practice: from k = 64 on n^(1/k) < 2 for any vertex count, so an infinite stretch is handled like any large one.

The result is random: it draws from the default random number generator (seed it with rng_seed for a repeatable answer). Edge ids are returned in increasing order.

Parameters

graph The input graph; it is not changed.
spanner Receives the ids of the chosen edges, ascending.
stretch The stretch factor t, at least 1.
weights Edge weights (non-negative, not NaN), or NULL for unit weights.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL stretch is below 1 or NaN; weights has the wrong length or holds a negative or NaN value.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

Expected O(k (|V| + |E|)) with k = min(floor((stretch + 1) / 2), 64).

Checked

python-igraph has no spanner: the stretch bound was verified for all pairs on 240 random multigraphs; the answer is random, so edges differ from igraph's.

C name

og_spanner

In notebooks

Og.Spanner

igraph 1.0

igraph_spanner

See also

minimum_spanning_tree, distances

`subcomponent`#

Exact

Lists the vertices reachable from a vertex, in breadth-first order.

og_error_t og_subcomponent(
    const og_t *graph,
    og_vector_int_t *res,
    og_int_t vertex,
    og_neimode_t mode
);

Returns every vertex that can be reached from vertex, including vertex itself, in the order a breadth-first search meets them (vertex first). In a directed graph mode chooses the direction: OG_OUT follows edges forward (vertices reachable from vertex), OG_IN backward (vertices that can reach vertex), OG_ALL ignores directions (the weak component). Undirected graphs ignore mode.

Neighbours are visited in the order incident() reports them, so the order of the result is the one python-igraph reports.

Parameters

graph The input graph; it is not changed.
res Receives the reachable vertices, vertex first.
vertex The start vertex.
mode OG_OUT, OG_IN or OG_ALL (directed graphs only).

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVVID vertex is not a vertex of the graph.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|) in the worst case; in practice the size of the part reached.

Checked

Identical to igraph 1.0, order included, on 243 random graphs.

C name

og_subcomponent

In notebooks

Og.Subcomponent

igraph 1.0

igraph_subcomponent

og_t g;
og_vector_int_t res;
og_small(&g, 4, OG_DIRECTED, 0,1, 1,2, 3,0, -1);
og_vector_int_init(&res, 0);
og_subcomponent(&g, &res, 0, OG_OUT);   /* res = 0 1 2 */
og_subcomponent(&g, &res, 0, OG_IN);    /* res = 0 3 */
og_vector_int_destroy(&res);
og_destroy(&g);

`reachability`#

Exact SIMD

Computes, for every component, the set of vertices it can reach, as bitsets.

og_error_t og_reachability(
    const og_t *graph,
    og_vector_int_t *membership,
    og_vector_int_t *csize,
    og_int_t *no_of_components,
    og_bitset_list_t *reach,
    og_neimode_t mode
);

First finds the components along mode: strongly connected components followed forward (OG_OUT) or backward (OG_IN), or weak components (OG_ALL, and always for undirected graphs). membership, csize and no_of_components describe them as in connected_components(); the ids follow a topological order of the condensation.

reach then holds one bitset per component: bit v of bitset c is set when vertex v can be reached from the vertices of component c along mode (its own vertices included). For OG_IN this means v can reach component c.

The bitsets are filled from the last component backwards, each as the union of its own vertices and the bitsets of the components it has edges to (the dynamic programme for the transitive closure of a DAG). The table takes |C| |V| / 8 bytes.

Parameters

graph The input graph; it is not changed.
membership Receives the component id of every vertex.
csize Receives the size of every component; may be NULL.
no_of_components Receives the number of components; may be NULL.
reach An initialized og_bitset_list_t; receives one bitset of |V| bits per component.
mode OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_ENOMEM Not enough memory; also when |C| |V| / 8 bytes would not fit.

Complexity

O(|V| + |E| + |E_C| |V| / 64), |E_C| the number of edges between different components.

Checked

Bitsets equal the oracle's reachable sets on graphs up to 60 vertices, every mode.

SIMD

The union of two bitsets runs on Open Graph's SIMD kernel (bits_or: AVX2, AVX-512 or NEON when the CPU has it).

C name

og_reachability

In notebooks

Og.Reachability

igraph 1.0

igraph_reachability

`count_reachable`#

Exact SIMD

Counts, for every vertex, how many vertices it can reach.

og_error_t og_count_reachable(
    const og_t *graph,
    og_vector_int_t *counts,
    og_neimode_t mode
);

counts[v] is the number of vertices reachable from v along mode, v itself included. OG_OUT follows edges forward, OG_IN backward. With OG_ALL, or in an undirected graph, a vertex reaches exactly its weak component, so counts[v] is that component's size and no reachability table is built.

For OG_OUT and OG_IN the counts come from the bitsets of reachability(): one population count per component.

Parameters

graph The input graph; it is not changed.
counts Receives one count per vertex.
mode OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_ENOMEM Not enough memory; for OG_OUT/OG_IN also when the |C| |V| / 8-byte table would not fit.

Complexity

O(|V| + |E|) for OG_ALL or undirected graphs; otherwise as reachability().

Checked

python-igraph has no such function: equal to the size of subcomponent() for every vertex and mode on 243 graphs.

SIMD

Directed modes use the SIMD kernels for the bitset unions (bits_or) and the population counts (popcount).

C name

og_count_reachable

In notebooks

Og.CountReachable

igraph 1.0

igraph_count_reachable

`transitive_closure`#

Unit tests SIMD

Builds the graph with an edge from every vertex to every vertex it can reach.

og_error_t og_transitive_closure(const og_t *graph, og_t *closure);

closure gets the same vertices as the graph and one edge u -> v for every vertex v != u that u can reach. No self-loops are added, even for vertices on a cycle. Edges are ordered by source, then target. An undirected graph gives an undirected closure: an edge between every two vertices of the same component, u < v, ordered by u then v (built from the components, without a reachability table).

closure must be uninitialized (or destroyed); the function initializes it.

Parameters

graph The input graph; it is not changed.
closure An uninitialized graph; receives the closure.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EOVERFLOW An undirected closure would have more edges than an og_int_t can count.
OG_ENOMEM Not enough memory, also for the reachability table of a directed graph.

Complexity

Directed: O(|V|^2 + |E_C| |V| / 64 + output). Undirected: O(|V| + |E| + output).

Checked

python-igraph has no such function: edge set checked against the oracle's reachable sets; no self-loops and the edge order are our conventions, not checked against the reference.

SIMD

Directed graphs use the SIMD bitset union of reachability().

C name

og_transitive_closure

In notebooks

Og.TransitiveClosure

igraph 1.0

igraph_transitive_closure

See also

reachability, count_reachable

Components

`connected_components`#

Exact

Finds the weakly or strongly connected components of a graph.

og_error_t og_connected_components(
    const og_t *graph,
    og_vector_int_t *membership,
    og_vector_int_t *csize,
    og_int_t *no,
    og_connectedness_t mode
);

Labels every vertex with the id of its component. OG_WEAK ignores edge directions; OG_STRONG (directed graphs) puts two vertices in the same component when each can reach the other. Undirected graphs ignore mode.

Weak component ids are given in order of each component's smallest vertex. Strong components come from Tarjan's algorithm and are numbered in a topological order of the condensation: every edge between two components goes from a smaller id to a larger one (this is also python-igraph's numbering).

Every output may be NULL. The result is stored in the graph's property cache, so a later is_connected() answers at once.

Parameters

graph The input graph; it is not changed.
membership Receives the component id of every vertex; may be NULL.
csize Receives the number of vertices of every component; may be NULL.
no Receives the number of components; may be NULL.
mode OG_WEAK or OG_STRONG (directed graphs only).

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL The graph is directed and mode is neither OG_WEAK nor OG_STRONG.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 (membership, sizes, count; strong ids in the same topological numbering) on 243 random graphs.

C name

og_connected_components

In notebooks

Og.ConnectedComponents

igraph 1.0

igraph_connected_components

og_t g;
og_vector_int_t memb, csize;
og_int_t no;
og_small(&g, 6, OG_UNDIRECTED, 0,1, 1,2, 3,4, -1);
og_vector_int_init(&memb, 0);
og_vector_int_init(&csize, 0);
og_connected_components(&g, &memb, &csize, &no, OG_WEAK);
/* no = 3, memb = 0 0 0 1 1 2, csize = 3 2 1 */
og_vector_int_destroy(&csize);
og_vector_int_destroy(&memb);
og_destroy(&g);

`is_connected`#

Exact

Tells whether a graph is weakly or strongly connected.

og_error_t og_is_connected(
    const og_t *graph,
    og_bool_t *res,
    og_connectedness_t mode
);

Sets res to true when every vertex can reach every other: ignoring directions for OG_WEAK, along the directions for OG_STRONG (directed graphs). Undirected graphs ignore mode. The null graph (no vertices) is not connected; a single vertex is.

Edge counts answer many cases at once (fewer than |V| - 1 edges cannot connect |V| vertices, fewer than |V| cannot connect them strongly). Otherwise a breadth-first search from vertex 0 decides, forward and backward for strong connectivity. The answer is kept in the graph's property cache.

Parameters

graph The input graph; it is not changed.
res Receives the answer.
mode OG_WEAK or OG_STRONG (directed graphs only).

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL The graph is directed and mode is neither OG_WEAK nor OG_STRONG.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|); O(1) when the answer is cached or follows from the edge count.

Checked

Identical to igraph 1.0 on 243 random graphs, weak and strong.

C name

og_is_connected

In notebooks

Og.IsConnected

igraph 1.0

igraph_is_connected

`decompose`#

Exact

Splits a graph into its connected components, each as a graph of its own.

og_error_t og_decompose(
    const og_t *graph,
    og_graph_list_t *components,
    og_connectedness_t mode,
    og_int_t maxcompno,
    og_int_t minelements
);

Fills components with one new graph per weak (OG_WEAK) or strong (OG_STRONG) component, in the order of connected_components(). The list is cleared first and owns the graphs. Each component keeps the directedness of the input; its vertices keep their relative order (new id = rank of the old id inside the component).

maxcompno limits how many components are returned (negative: no limit) and minelements skips components with fewer vertices. Edges keep their relative id order when the component holds more than half of the vertices; otherwise they are listed vertex by vertex. Both orders are the ones python-igraph reports.

With an attribute handler installed, every component gets the graph attributes and the attributes of its own vertices and edges.

Parameters

graph The input graph; it is not changed.
components An initialized og_graph_list_t; receives the components.
mode OG_WEAK or OG_STRONG; strong only differs for directed graphs.
maxcompno The largest number of components to return; negative for all.
minelements The smallest number of vertices a returned component must have.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL mode is neither OG_WEAK nor OG_STRONG (checked for every graph).
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|) plus the cost of building the component graphs.

Checked

Identical to igraph 1.0 (vertex and edge order, attributes) on 360 random graphs plus 4,000 verifier cases.

C name

og_decompose

In notebooks

Og.Decompose

igraph 1.0

igraph_decompose

`biconnected_components`#

Exact

Finds the biconnected components of a graph and its articulation points.

og_error_t og_biconnected_components(
    const og_t *graph,
    og_int_t *no,
    og_vector_int_list_t *tree_edges,
    og_vector_int_list_t *component_edges,
    og_vector_int_list_t *components,
    og_vector_int_t *articulation_points
);

A biconnected component is a maximal set of edges in which any two edges lie on a common simple cycle; a single edge that is a bridge forms a component of its own. Edge directions are ignored. Self-loops belong to no component, parallel edges do, and an isolated vertex is in no component.

The depth-first search of Hopcroft and Tarjan runs from the vertices in increasing order, with neighbours in incident() order; components are reported in the order the search completes them (python-igraph's order). Every output may be NULL:

tree_edges: per component, the edges of the search tree inside it, in the order they leave the edge stack (latest discovered first);
component_edges: per component, all its edges, ascending ids;
components: per component, its vertices, ascending;
articulation_points: the vertices whose removal disconnects their component, ascending.

Parameters

graph The input graph; it is not changed.
no Receives the number of components; may be NULL.
tree_edges Receives the tree edges of each component; may be NULL.
component_edges Receives the edges of each component; may be NULL.
components Receives the vertices of each component; may be NULL.
articulation_points Receives the articulation points; may be NULL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 (count, order, vertex lists, tree edges, articulation points) on 266 graphs; component edge lists checked structurally.

C name

og_biconnected_components

In notebooks

Og.BiconnectedComponents

igraph 1.0

igraph_biconnected_components

og_t g;
og_vector_int_list_t comps;
og_vector_int_t art;
og_int_t no;
/* two triangles sharing vertex 2, and a pendant vertex 5 */
og_small(&g, 6, OG_UNDIRECTED, 0,1, 1,2, 0,2, 2,3, 3,4, 2,4, 4,5, -1);
og_vector_int_list_init(&comps, 0);
og_vector_int_init(&art, 0);
og_biconnected_components(&g, &no, NULL, NULL, &comps, &art);
/* no = 3; components {4 5}, {2 3 4}, {0 1 2}; art = 2 4 */
og_vector_int_destroy(&art);
og_vector_int_list_destroy(&comps);
og_destroy(&g);

`articulation_points`#

Exact

Lists the vertices whose removal splits their component.

og_error_t og_articulation_points(const og_t *graph, og_vector_int_t *res);

An articulation point (cut vertex) is a vertex whose removal, with its edges, leaves its connected component in more pieces. Edge directions are ignored; self-loops and parallel edges make no difference. The vertices are returned in increasing order.

Computed by the same depth-first search as biconnected_components(), keeping only the articulation flags.

Parameters

graph The input graph; it is not changed.
res Receives the articulation points, ascending.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 266 graphs.

C name

og_articulation_points

In notebooks

Og.ArticulationPoints

igraph 1.0

igraph_articulation_points

`bridges`#

Exact

Lists the edges whose removal splits their component.

og_error_t og_bridges(const og_t *graph, og_vector_int_t *bridges);

A bridge (cut edge) is an edge whose removal leaves its component in two pieces. Edge directions are ignored. A self-loop is never a bridge, and neither is an edge with a parallel copy (the copy keeps the two ends together). Edge ids are returned in increasing order.

Uses Tarjan's low-point test on a depth-first search: a tree edge to v is a bridge when nothing below v reaches above v's parent.

Parameters

graph The input graph; it is not changed.
bridges Receives the bridge edge ids, ascending.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 266 graphs.

C name

og_bridges

In notebooks

Og.Bridges

igraph 1.0

igraph_bridges

og_t g;
og_vector_int_t br;
/* a triangle 0-1-2 with a path 2-3-4 */
og_small(&g, 5, OG_UNDIRECTED, 0,1, 1,2, 2,0, 2,3, 3,4, -1);
og_vector_int_init(&br, 0);
og_bridges(&g, &br);   /* br = 3 4 (edges 2-3 and 3-4) */
og_vector_int_destroy(&br);
og_destroy(&g);

`is_biconnected`#

Exact

Tells whether a graph is biconnected.

og_error_t og_is_biconnected(const og_t *graph, og_bool_t *res);

A graph is biconnected when it is connected, has at least two vertices and has no articulation point. Edge directions are ignored. By this definition the graphs with 0 or 1 vertices are not biconnected, and two vertices joined by an edge are.

Edge counts and is_connected() answer first; otherwise the articulation-point search decides.

Parameters

graph The input graph; it is not changed.
res Receives the answer; may be NULL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 266 graphs, including 0, 1 and 2 vertices, loops and parallel edges.

C name

og_is_biconnected

In notebooks

Og.IsBiconnected

igraph 1.0

igraph_is_biconnected

Percolation

`site_percolation`#

Unit tests

Adds vertices one by one and records the size of the largest component after each.

og_error_t og_site_percolation(
    const og_t *graph,
    og_vector_int_t *giant_size,
    og_vector_int_t *edge_count,
    const og_vector_int_t *vertex_order
);

Starts from an empty graph and adds the vertices of vertex_order one at a time, each with its edges to vertices already added. After the i-th vertex, giant_size[i] is the number of vertices of the largest connected component and edge_count[i] the number of edges present (both ends added; self-loops and parallel edges count). Edge directions are ignored.

vertex_order may list only some of the vertices; the curves then have that many entries. With vertex_order NULL a random order of all vertices is drawn (Fisher-Yates with the default random number generator). The method is the union-find scheme of Newman and Ziff (2000).

Parameters

graph The input graph; it is not changed.
giant_size Receives the largest component size after each step; may be NULL.
edge_count Receives the number of edges present after each step; may be NULL.
vertex_order The order in which vertices are added (distinct ids), or NULL for a random order.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVVID vertex_order holds an id that is not a vertex.
OG_EINVAL vertex_order holds the same vertex twice.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| a(|V|)), a the inverse Ackermann function.

Checked

python-igraph has no percolation: checked against a brute-force component count on 200 random multigraphs.

C name

og_site_percolation

In notebooks

Og.SitePercolation

igraph 1.0

igraph_site_percolation

`bond_percolation`#

Unit tests

Adds edges one by one and records the size of the largest component after each.

og_error_t og_bond_percolation(
    const og_t *graph,
    og_vector_int_t *giant_size,
    og_vector_int_t *vertex_count,
    const og_vector_int_t *edge_order
);

Starts with all vertices and no edges, then adds the edges of edge_order one at a time. After the i-th edge, giant_size[i] is the number of vertices in the largest connected component and vertex_count[i] the number of vertices touched by at least one added edge. Edge directions are ignored.

edge_order may list only some edges; the curves then have that many entries. With edge_order NULL a random order of all edges is drawn from the default random number generator. Union-find after Newman and Ziff (2000).

Parameters

graph The input graph; it is not changed.
giant_size Receives the largest component size after each edge; may be NULL.
vertex_count Receives the number of vertices touched so far after each edge; may be NULL.
edge_order The order in which edges are added (distinct ids), or NULL for a random order.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVEID edge_order holds an id that is not an edge.
OG_EINVAL edge_order holds the same edge twice.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

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

Checked

python-igraph has no percolation: checked against connected components of every prefix on 200 random multigraphs.

C name

og_bond_percolation

In notebooks

Og.BondPercolation

igraph 1.0

igraph_bond_percolation

`edgelist_percolation`#

Unit tests

Bond percolation on a plain list of vertex pairs, without building a graph.

og_error_t og_edgelist_percolation(
    const og_vector_int_t *edges,
    og_vector_int_t *giant_size,
    og_vector_int_t *vertex_count
);

edges holds pairs (a0, b0, a1, b1, ...). The pairs are joined in that order; after the i-th pair giant_size[i] is the size of the largest component formed so far and vertex_count[i] the number of distinct vertices seen so far. Only vertices that occur in the list count.

Ids may be any non-negative og_int_t values: when an id is at or above the list's length the vertices are first relabelled through a hash table, so time and memory stay O(|E|) however large the ids are.

Parameters

edges The vertex pairs, flattened; an even number of non-negative ids.
giant_size Receives the largest component size after each pair; may be NULL.
vertex_count Receives the number of distinct vertices seen after each pair; may be NULL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL edges has an odd number of entries.
OG_EINVVID edges holds a negative id.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|E| a(|E|)) expected.

Checked

python-igraph has no percolation: agrees with bond percolation on 200 graphs.

C name

og_edgelist_percolation

In notebooks

Og.EdgelistPercolation

igraph 1.0

igraph_edgelist_percolation

See also

bond_percolation, site_percolation

Trees and spanning trees

`minimum_spanning_tree`#

Exact

Finds a minimum spanning forest and returns its edge ids.

og_error_t og_minimum_spanning_tree(
    const og_t *graph,
    og_vector_int_t *res,
    const og_vector_t *weights,
    og_mst_algorithm_t method
);

Returns the edges of a spanning tree of every connected component (a spanning forest) of least total weight. Edge directions are ignored. Negative weights are allowed.

method chooses the algorithm: OG_MST_UNWEIGHTED, a breadth-first forest (weights ignored); OG_MST_KRUSKAL, Kruskal's algorithm; OG_MST_PRIM, Prim's algorithm with a binary heap; OG_MST_AUTOMATIC, breadth-first without weights and Kruskal with them. Prim and Kruskal also fall back to breadth-first when weights is NULL.

The edges come in the order the algorithm takes them. Among equal weights both weighted methods pick exactly the edges python-igraph picks: Kruskal sorts with the Bentley-McIlroy quicksort, Prim's heap treats ties as the reference does.

Parameters

graph The input graph; it is not changed.
res Receives the edge ids of the forest.
weights Edge weights (not NaN), or NULL.
method OG_MST_AUTOMATIC, OG_MST_UNWEIGHTED, OG_MST_PRIM or OG_MST_KRUSKAL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL Unknown method; weights has the wrong length or holds NaN.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|) unweighted; O(|E| log |E|) for Kruskal and Prim.

Checked

Identical to igraph 1.0, edge order and tie choices included, for all methods on 780 graphs with special weights.

C name

og_minimum_spanning_tree

In notebooks

Og.MinimumSpanningTree

igraph 1.0

igraph_minimum_spanning_tree

og_t g;
og_vector_t w;
og_vector_int_t tree;
og_small(&g, 4, OG_UNDIRECTED, 0,1, 1,2, 2,3, 3,0, 0,2, -1);
og_vector_init_real(&w, 5, 4.0, 1.0, 2.0, 3.0, 5.0);
og_vector_int_init(&tree, 0);
og_minimum_spanning_tree(&g, &tree, &w, OG_MST_KRUSKAL);   /* tree = 1 2 3, weight 6 */
og_vector_int_destroy(&tree);
og_vector_destroy(&w);
og_destroy(&g);

`random_spanning_tree`#

Same quality

Draws a spanning tree uniformly at random.

og_error_t og_random_spanning_tree(
    const og_t *graph,
    og_vector_int_t *res,
    og_int_t vid
);

Returns the edge ids of a spanning tree chosen uniformly among all spanning trees, using Wilson's loop-erased random walks (1996). Edge directions are ignored. Parallel edges are separate choices, so in a multigraph every spanning tree as a set of edge ids is equally likely.

With vid >= 0 only the component of vid is spanned (vid is the root). With vid < 0 the whole graph gets a spanning forest: one uniform tree per component, rooted at its smallest vertex. The walks use the default random number generator.

Parameters

graph The input graph; it is not changed.
res Receives the edge ids of the tree or forest.
vid The vertex whose component is spanned, or a negative number for every component.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVVID vid >= 0 is not a vertex of the graph.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

Expected time proportional to the mean hitting time of the random walk; O(|V| + |E|) memory.

Checked

Same distribution as igraph (uniform, chi-square tested); different random draws.

C name

og_random_spanning_tree

In notebooks

Og.RandomSpanningTree

igraph 1.0

igraph_random_spanning_tree

See also

minimum_spanning_tree, rng_seed

`is_tree`#

Exact

Tells whether a graph is a tree, and finds its root.

og_error_t og_is_tree(
    const og_t *graph,
    og_bool_t *res,
    og_int_t *root,
    og_neimode_t mode
);

A tree here has n >= 1 vertices, exactly n - 1 edges, and reaches every vertex from a root. With OG_ALL (and always in undirected graphs) directions are ignored and the root is vertex 0. With OG_OUT the graph must be an out-tree: the root is the vertex without in-edges and every vertex is reached along the edges. OG_IN asks for an in-tree, edges pointing towards the root. The null graph is not a tree.

root, when not NULL, receives the root only if the answer is true.

Parameters

graph The input graph; it is not changed.
res Receives the answer.
root Receives the root when the graph is a tree; may be NULL.
mode OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL mode is not OG_OUT, OG_IN or OG_ALL.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 280 graphs and 3 modes, root included.

C name

og_is_tree

In notebooks

Og.IsTree

igraph 1.0

igraph_is_tree

`is_forest`#

Exact

Tells whether a graph is a forest, and lists one root per tree.

og_error_t og_is_forest(
    const og_t *graph,
    og_bool_t *res,
    og_vector_int_t *roots,
    og_neimode_t mode
);

A forest is a graph whose every weak component is a tree in the sense of is_tree(): ignoring directions for OG_ALL (and in undirected graphs), or with every edge pointing away from (OG_OUT) or towards (OG_IN) its tree's root. The null graph is a forest.

roots, when not NULL, receives one root per component if the answer is true: for OG_ALL the smallest vertex of each component; for OG_OUT the vertices without in-edges and for OG_IN those without out-edges, ascending. The undirected answer is kept in the graph's property cache.

Parameters

graph The input graph; it is not changed.
res Receives the answer; may be NULL.
roots Receives one root per tree; may be NULL.
mode OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|); O(1) when the undirected answer is cached.

Checked

Derived from the oracle's is_tree per component on 280 graphs; root order confirmed against the native igraph 1.0.1 C library.

C name

og_is_forest

In notebooks

Og.IsForest

igraph 1.0

igraph_is_forest

See also

is_tree, connected_components

`to_prufer`#

Exact

Encodes a labelled tree as its Pruefer sequence.

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

Returns the n - 2 entries of the Pruefer sequence of a tree with n >= 2 vertices: repeatedly remove the leaf with the smallest id and write down its neighbour. Edge directions are ignored. The leaves are found by a linear scan and each vertex keeps the XOR of its neighbours, so a leaf's only neighbour is known without a search.

Parameters

graph The input graph; it is not changed.
prufer Receives the sequence (n - 2 vertex ids).

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL The graph is not a tree (directions ignored) or has fewer than two vertices.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V|).

Checked

Identical to igraph 1.0 on 60 random trees.

C name

og_to_prufer

In notebooks

Og.ToPrufer

igraph 1.0

igraph_to_prufer

See also

from_prufer, is_tree

Degree sequences

`is_graphical`#

Exact

Tells whether a degree sequence can be realized by a graph with the allowed edge types.

og_error_t og_is_graphical(
    const og_vector_int_t *out_degrees,
    const og_vector_int_t *in_degrees,
    const og_edge_type_sw_t allowed_edge_types,
    og_bool_t *res
);

With in_degrees NULL the question is undirected: is there a graph whose vertex degrees are out_degrees? Otherwise it is directed: is there a graph with these out- and in-degrees? allowed_edge_types combines OG_LOOPS_SW (self-loops allowed; a loop adds 2 to an undirected degree) and OG_MULTI_SW (parallel edges allowed); OG_SIMPLE_SW allows neither. A sequence with a negative entry is never graphical (no error).

The tests: undirected simple graphs, Erdos-Gallai; with single self-loops, the Cairns-Mendan condition; with multi-edges, an even sum and no degree above the sum of the others; with both, an even sum. Directed simple graphs, Fulkerson-Chen-Anstee; with self-loops, Gale-Ryser; with multi-edges, equal sums and out_i + in_i not above the sum; with both, equal sums. All run in linear time with counting sorts, and degree sums are exact in 128-bit arithmetic.

Parameters

out_degrees The degrees (undirected) or out-degrees (directed).
in_degrees The in-degrees, same length as out_degrees, or NULL for the undirected question.
allowed_edge_types Bits of edge_type_sw_t: OG_LOOPS_SW, OG_MULTI_SW, or OG_SIMPLE_SW (0).
res Receives the answer.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL in_degrees is given and its length differs from out_degrees.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(n), n the length of the sequence.

Checked

Identical to igraph 1.0 on 2,000 sequences and every small sequence (exhaustive), all four edge-type switches.

C name

og_is_graphical

In notebooks

Og.IsGraphical

igraph 1.0

igraph_is_graphical

`is_bigraphical`#

Exact

Tells whether two degree sequences can be the sides of a bipartite graph.

og_error_t og_is_bigraphical(
    const og_vector_int_t *degrees1,
    const og_vector_int_t *degrees2,
    const og_edge_type_sw_t allowed_edge_types,
    og_bool_t *res
);

Asks for a bipartite graph whose first part has degrees degrees1 and whose second part has degrees2, every edge joining the two parts. With OG_MULTI_SW in allowed_edge_types parallel edges are allowed and equal sums suffice; without it the Gale-Ryser condition is checked (in linear time with counting sorts). Self-loops cannot occur in a bipartite graph, so OG_LOOPS_SW changes nothing. A negative entry makes the answer false.

Parameters

degrees1 The degrees of the first part.
degrees2 The degrees of the second part.
allowed_edge_types Bits of edge_type_sw_t; only OG_MULTI_SW matters.
res Receives the answer.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(n1 + n2).

Checked

Identical to igraph 1.0 on 600 pairs and every small pair (exhaustive).

C name

og_is_bigraphical

In notebooks

Og.IsBigraphical

igraph 1.0

igraph_is_bigraphical

See also

is_graphical

Direction

`to_directed`#

Exact

Turns an undirected graph into a directed one, in place.

og_error_t og_to_directed(og_t *graph, og_to_directed_t mode);

Does nothing to a graph that is already directed. Otherwise every undirected edge becomes directed, as mode says:

OG_TO_DIRECTED_ARBITRARY: one edge, from the smaller to the larger vertex id;
OG_TO_DIRECTED_ACYCLIC: the same orientation, which makes the result acyclic (apart from self-loops);
OG_TO_DIRECTED_RANDOM: one edge, its direction drawn by a fair coin from the default random number generator;
OG_TO_DIRECTED_MUTUAL: two edges, one each way; edge e keeps its id and its reverse gets id e + |E|.

Graph and vertex attributes are kept; edge attributes follow their edges (in MUTUAL mode both copies get the values). On failure the graph is unchanged.

Parameters

graph The graph to convert; changed in place.
mode OG_TO_DIRECTED_ARBITRARY (0), OG_TO_DIRECTED_MUTUAL (1), OG_TO_DIRECTED_RANDOM (2) or OG_TO_DIRECTED_ACYCLIC (3).

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL mode is not one of the four values.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 for ARBITRARY, MUTUAL and ACYCLIC (edge lists and attributes); RANDOM checked statistically.

C name

og_to_directed

In notebooks

Og.ToDirected

igraph 1.0

igraph_to_directed

See also

to_undirected, is_directed

`to_undirected`#

Exact

Turns a directed graph into an undirected one, in place.

og_error_t og_to_undirected(
    og_t *graph,
    og_to_undirected_t mode,
    const og_attribute_combination_t *edge_comb
);

Does nothing to a graph that is already undirected. Otherwise, as mode says:

OG_TO_UNDIRECTED_EACH: every directed edge becomes one undirected edge, with the same id and attributes;
OG_TO_UNDIRECTED_COLLAPSE: one undirected edge for every pair of vertices joined in either direction (and one self-loop for every vertex that has any);
OG_TO_UNDIRECTED_MUTUAL: one undirected edge for every reciprocated pair: between u and v with a edges u -> v and b edges v -> u, min(a, b) edges are kept; self-loops are kept as they are.

In COLLAPSE and MUTUAL mode the new edges are ordered by their larger end, then their smaller end. edge_comb tells how the attributes of merged edges are combined (COLLAPSE: all edges of the pair; MUTUAL: the k-th edge of each direction); with edge_comb NULL the edge attributes are dropped. Graph and vertex attributes are kept. On failure the graph is unchanged.

Parameters

graph The graph to convert; changed in place.
mode OG_TO_UNDIRECTED_EACH (0), OG_TO_UNDIRECTED_COLLAPSE (1) or OG_TO_UNDIRECTED_MUTUAL (2).
edge_comb How to combine edge attributes of merged edges, or NULL to drop them.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL mode is not one of the three values.
OG_EATTRCOMBINE A combination rule does not fit an attribute's type (reported by the attributes area).
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|) plus the attribute combination.

Checked

Identical to igraph 1.0 edge lists for all modes on 200 graphs; combined attributes equal python-igraph's.

C name

og_to_undirected

In notebooks

Og.ToUndirected

igraph 1.0

igraph_to_undirected

See also

to_directed, simplify

Self-loops, multi-edges and mutual edges

`is_simple`#

Exact

Tells whether a graph has no self-loops and no multi-edges.

og_error_t og_is_simple(
    const og_t *graph,
    og_bool_t *res,
    og_bool_t directed
);

A graph is simple when it has no self-loop and no two edges join the same ordered pair (the same unordered pair in undirected graphs). For a directed graph with directed set to false the directions are ignored, so a mutual pair u -> v, v -> u counts as a multi-edge. Undirected graphs ignore the directed argument.

Uses has_loop(), has_multiple() and has_mutual(), whose answers are cached.

Parameters

graph The input graph; it is not changed.
res Receives the answer.
directed For directed graphs: false to judge the graph with directions ignored.

Returns

OG_SUCCESS, or the error code of the failure.

Complexity

O(|V| + |E|); O(1) when the answers are cached.

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_is_simple

In notebooks

Og.IsSimple

igraph 1.0

igraph_is_simple

See also

has_loop, has_multiple, simplify

`is_loop`#

Exact

Tells, for each selected edge, whether it is a self-loop.

og_error_t og_is_loop(const og_t *graph, og_vector_bool_t *res, og_es_t es);

res[i] is true when the i-th edge of the selector es starts and ends at the same vertex. The results follow the selector's order, repeats included.

Parameters

graph The input graph; it is not changed.
res Receives one flag per selected edge.
es The edges to test.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVEID The selector names an edge that does not exist.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(number of selected edges).

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_is_loop

In notebooks

Og.IsLoop

igraph 1.0

igraph_is_loop

`has_loop`#

Exact

Tells whether a graph has at least one self-loop.

og_error_t og_has_loop(const og_t *graph, og_bool_t *res);

Scans the edges until a self-loop is found. The answer is kept in the graph's property cache.

Parameters

graph The input graph; it is not changed.
res Receives the answer.

Returns

OG_SUCCESS, or the error code of the failure.

Complexity

O(|E|); O(1) when cached.

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_has_loop

In notebooks

Og.HasLoop

igraph 1.0

igraph_has_loop

See also

is_loop, count_loops, is_simple

`count_loops`#

Exact

Counts the self-loops of a graph.

og_error_t og_count_loops(const og_t *graph, og_int_t *loop_count);

Sets loop_count to the number of edges that start and end at the same vertex. Answers 0 at once when the property cache already knows there is no loop, and records in the cache whether there is one.

Parameters

graph The input graph; it is not changed.
loop_count Receives the number of self-loops.

Returns

OG_SUCCESS, or the error code of the failure.

Complexity

O(|E|).

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_count_loops

In notebooks

Og.CountLoops

igraph 1.0

igraph_count_loops

See also

has_loop, is_loop

`is_multiple`#

Exact

Tells, for each selected edge, whether it repeats an earlier parallel edge.

og_error_t og_is_multiple(
    const og_t *graph,
    og_vector_bool_t *res,
    og_es_t es
);

Edges joining the same ordered pair of vertices (the same unordered pair in undirected graphs) form a parallel group. res[i] is true for every edge of a group except the one with the smallest id, so removing the flagged edges leaves one edge per group. Self-loops at the same vertex form a group too. In a directed graph u -> v and v -> u are not parallel.

Parameters

graph The input graph; it is not changed.
res Receives one flag per selected edge.
es The edges to test.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVEID The selector names an edge that does not exist.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(k log d): k selected edges, d the largest degree (binary search in the sorted adjacency).

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_is_multiple

In notebooks

Og.IsMultiple

igraph 1.0

igraph_is_multiple

`has_multiple`#

Exact

Tells whether a graph has at least one pair of parallel edges.

og_error_t og_has_multiple(const og_t *graph, og_bool_t *res);

True when two edges join the same ordered pair (unordered in undirected graphs), self-loops included. A directed mutual pair is not a multi-edge. The answer is kept in the graph's property cache.

Parameters

graph The input graph; it is not changed.
res Receives the answer.

Returns

OG_SUCCESS, or the error code of the failure.

Complexity

O(|V| + |E|); O(1) when cached.

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_has_multiple

In notebooks

Og.HasMultiple

igraph 1.0

igraph_has_multiple

`count_multiple`#

Exact

Gives, for each selected edge, how many edges are parallel to it (itself included).

og_error_t og_count_multiple(
    const og_t *graph,
    og_vector_int_t *res,
    og_es_t es
);

res[i] is the size of the parallel group of the i-th selected edge: the number of edges joining the same ordered pair (unordered in undirected graphs), the edge itself included, so an edge without copies gets 1. Self-loops at the same vertex count as one group.

Parameters

graph The input graph; it is not changed.
res Receives one multiplicity per selected edge.
es The edges to examine.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVEID The selector names an edge that does not exist.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(k log d), k the number of selected edges.

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_count_multiple

In notebooks

Og.CountMultiple

igraph 1.0

igraph_count_multiple

See also

count_multiple_1, is_multiple

`count_multiple_1`#

Exact

Gives the multiplicity of a single edge.

og_error_t og_count_multiple_1(
    const og_t *graph,
    og_int_t *res,
    og_int_t eid
);

The one-edge form of count_multiple(): res is the number of edges parallel to eid, eid included.

Parameters

graph The input graph; it is not changed.
res Receives the multiplicity.
eid The edge.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVEID eid is not an edge of the graph.

Complexity

O(log d).

Checked

Identical to igraph 1.0 on 280 graphs, every edge.

C name

og_count_multiple_1

In notebooks

Og.CountMultiple1

igraph 1.0

igraph_count_multiple_1

See also

count_multiple, is_multiple

`is_mutual`#

Exact

Tells, for each selected edge, whether its reverse edge exists too.

og_error_t og_is_mutual(
    const og_t *graph,
    og_vector_bool_t *res,
    og_es_t es,
    og_bool_t loops
);

In a directed graph res[i] is true when the i-th selected edge u -> v has a partner v -> u. A directed self-loop is its own reverse: it counts as mutual only when loops is true. In an undirected graph every edge is mutual.

Parameters

graph The input graph; it is not changed.
res Receives one flag per selected edge.
es The edges to test.
loops Whether directed self-loops count as mutual.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVEID The selector names an edge that does not exist.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(k log d), k the number of selected edges.

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_is_mutual

In notebooks

Og.IsMutual

igraph 1.0

igraph_is_mutual

See also

has_mutual, reciprocity

`has_mutual`#

Exact

Tells whether a directed graph has at least one pair of opposite edges.

og_error_t og_has_mutual(
    const og_t *graph,
    og_bool_t *res,
    og_bool_t loops
);

True when some u -> v has a partner v -> u with u != v, or, with loops true, when the graph has a self-loop. An undirected graph answers true when it has any edge. The loop-free answer is kept in the graph's property cache.

Parameters

graph The input graph; it is not changed.
res Receives the answer.
loops Whether a self-loop counts as a mutual edge.

Returns

OG_SUCCESS, or the error code of the failure.

Complexity

O(|V| + |E|); O(1) when cached.

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_has_mutual

In notebooks

Og.HasMutual

igraph 1.0

igraph_has_mutual

See also

is_mutual, reciprocity, is_simple

Cores, trusses and chordal graphs

`coreness`#

Exact

Computes the k-core index (shell index) of every vertex.

og_error_t og_coreness(
    const og_t *graph,
    og_vector_int_t *cores,
    og_neimode_t mode
);

The k-core of a graph is the largest subgraph in which every vertex has degree at least k. cores[v] is the largest k for which v belongs to the k-core. In directed graphs mode chooses the degree: OG_OUT out-degree, OG_IN in-degree, OG_ALL both; undirected graphs use OG_ALL. Parallel edges count with their multiplicity; a self-loop adds 2 to the OG_ALL degree and 1 to the out- and in-degree.

Batagelj and Zaversnik's bucket algorithm: vertices are sorted by degree and peeled in increasing order, each removal lowering its neighbours' degrees.

Parameters

graph The input graph; it is not changed.
cores Receives the core index of every vertex.
mode OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 280 graphs, all modes.

C name

og_coreness

In notebooks

Og.Coreness

igraph 1.0

igraph_coreness

See also

trussness, degree

og_t g;
og_vector_int_t cores;
/* a 4-clique 0..3 with a tail 3-4-5 */
og_small(&g, 6, OG_UNDIRECTED, 0,1, 0,2, 0,3, 1,2, 1,3, 2,3, 3,4, 4,5, -1);
og_vector_int_init(&cores, 0);
og_coreness(&g, &cores, OG_ALL);   /* cores = 3 3 3 3 1 1 */
og_vector_int_destroy(&cores);
og_destroy(&g);

`trussness`#

Exact

Computes the trussness of every edge.

og_error_t og_trussness(const og_t *graph, og_vector_int_t *trussness);

The k-truss of a graph is the largest subgraph in which every edge lies in at least k - 2 triangles of that subgraph. trussness[e] is the largest k for which edge e belongs to the k-truss; an edge in no triangle, and every self-loop, gets 2. Edge directions are ignored.

The graph must have no multi-edges once directions are ignored: parallel edges, two self-loops at one vertex and a directed mutual pair are refused with OG_UNIMPLEMENTED, as the reference does. Triangle supports come from degree-ordered triangle listing (Chiba-Nishizeki); the peeling follows Wang and Cheng (2012).

Parameters

graph The input graph; it is not changed.
trussness Receives one value per edge.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_UNIMPLEMENTED The graph has multi-edges with directions ignored.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|E|^1.5) for the supports; the peeling adds a logarithmic factor for edge look-ups.

Checked

Identical to the native igraph 1.0.1 C library on test graphs and to a brute-force peeling on 250 random graphs; multigraphs refused as igraph does.

C name

og_trussness

In notebooks

Og.Trussness

igraph 1.0

igraph_trussness

See also

coreness, count_triangles

`maximum_cardinality_search`#

Exact

Orders the vertices by maximum cardinality search, the first step of a chordality test.

og_error_t og_maximum_cardinality_search(
    const og_t *graph,
    og_vector_int_t *alpha,
    og_vector_int_t *alpham1
);

Maximum cardinality search (Tarjan and Yannakakis, 1984) numbers the vertices from |V| - 1 down to 0: each step takes an unnumbered vertex with the most numbered neighbours. alpha[v] is the rank given to v, and alpham1[i] the vertex with rank i (the inverse). Vertex 0 is taken first; among equal candidates the most recently promoted vertex is taken, which gives python-igraph's order. Edge directions are ignored and parallel edges count once.

Parameters

graph The input graph; it is not changed.
alpha Receives the rank of every vertex.
alpham1 Receives the inverse: the vertex of every rank; may be NULL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 (alpha and its inverse, tie order included) on 280 graphs.

C name

og_maximum_cardinality_search

In notebooks

Og.MaximumCardinalitySearch

igraph 1.0

igraph_maximum_cardinality_search

See also

is_chordal

`is_chordal`#

Exact

Tells whether a graph is chordal, and gives the edges that would make it chordal.

og_error_t og_is_chordal(
    const og_t *graph,
    const og_vector_int_t *alpha,
    const og_vector_int_t *alpham1,
    og_bool_t *chordal,
    og_vector_int_t *fill_in,
    og_t *newgraph
);

A graph is chordal when every cycle of four or more vertices has a chord. The test eliminates the vertices in rank order (rank 0 first) and checks, with the follower method of Tarjan and Yannakakis (1984), that each vertex's earlier neighbours form a clique; every missing edge found is a fill-in edge. The ranks are alpha (or its inverse alpham1); when both are NULL they are computed by maximum_cardinality_search(), which makes the test exact. With another order the fill-in depends on that order.

Outputs may be NULL: chordal gets the answer, fill_in the fill-in edges as a flat list of vertex pairs, newgraph a copy of the graph with the fill-in edges added (newgraph must be uninitialized). When neither fill_in nor newgraph is asked for, the test stops at the first missing edge. Edge directions are ignored.

Parameters

graph The input graph; it is not changed.
alpha The rank of every vertex, or NULL.
alpham1 The vertex of every rank, or NULL.
chordal Receives the answer; may be NULL.
fill_in Receives the fill-in edges as vertex pairs; may be NULL.
newgraph An uninitialized graph that receives the graph plus its fill-in; may be NULL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL alpha or alpham1 does not have one entry per vertex, or is not a permutation of the vertices (python-igraph answers 'not chordal' there instead).
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|) for the test; computing the fill-in adds time for the edges it finds.

Checked

Identical to igraph 1.0 (answer and fill-in order) on 280 graphs; rank vectors that are not permutations give OG_EINVAL where python-igraph answers 'not chordal'.

C name

og_is_chordal

In notebooks

Og.IsChordal

igraph 1.0

igraph_is_chordal

See also

maximum_cardinality_search

Density and degree summaries

`density`#

Exact

Computes the density: edges present over edges possible.

og_error_t og_density(
    const og_t *graph,
    const og_vector_t *weights,
    og_real_t *res,
    og_bool_t loops
);

The number of edges (or, with weights, their total weight) divided by the number of vertex pairs that could carry an edge. With n vertices that is n(n - 1) for directed graphs and n(n - 1)/2 for undirected ones; with loops true self-loops are possible too, giving n^2 and n(n + 1)/2. Multi-edges are counted, so the density of a multigraph can exceed 1.

The result is NaN when no pair is possible (the null graph, or one vertex without loops).

Parameters

graph The input graph; it is not changed.
weights Edge weights, or NULL to count edges.
res Receives the density.
loops Whether self-loops count as possible edges.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL weights does not have one entry per edge.

Complexity

O(1) without weights; O(|E|) with weights.

Checked

Identical to igraph 1.0 on 280 graphs; the weighted form checked against its definition.

C name

og_density

In notebooks

Og.Density

igraph 1.0

igraph_density

See also

mean_degree, rich_club_sequence

og_t g;
og_real_t d;
og_small(&g, 4, OG_DIRECTED, 0,1, 1,0, 1,2, 2,3, -1);
og_density(&g, NULL, &d, false);   /* 4 edges / 12 pairs = 0.333 */
og_destroy(&g);

`mean_degree`#

Exact

Computes the average degree of the vertices.

og_error_t og_mean_degree(
    const og_t *graph,
    og_real_t *res,
    og_bool_t loops
);

2|E|/|V| for undirected graphs and |E|/|V| for directed ones (the average out-degree, equal to the average in-degree). With loops false self-loops are left out of the edge count. The null graph gives NaN.

Parameters

graph The input graph; it is not changed.
res Receives the mean degree.
loops Whether self-loops count.

Returns

OG_SUCCESS, or the error code of the failure.

Complexity

O(1) with loops true; O(|E|) with loops false (O(1) when the graph is known to have no loop).

Checked

Identical to igraph 1.0 on 280 graphs.

C name

og_mean_degree

In notebooks

Og.MeanDegree

igraph 1.0

igraph_mean_degree

See also

density, degree

`reciprocity`#

Exact

Measures how often directed edges are returned.

og_error_t og_reciprocity(
    const og_t *graph,
    og_real_t *res,
    og_bool_t ignore_loops,
    og_reciprocity_t mode
);

For undirected graphs the result is 1. In a directed graph, between two vertices with a edges one way and b edges the other, 2 min(a, b) edges are reciprocated and |a - b| are not. A self-loop is its own reverse: it counts as reciprocated, or is left out entirely when ignore_loops is true.

OG_RECIPROCITY_DEFAULT gives the share of edges that are reciprocated. OG_RECIPROCITY_RATIO gives mutual pairs over connected pairs: a reciprocated pair counts once, R / (R + N) with R half the reciprocated edges and N the rest. A graph without edges gives NaN.

Parameters

graph The input graph; it is not changed.
res Receives the reciprocity.
ignore_loops Whether to leave self-loops out.
mode OG_RECIPROCITY_DEFAULT (0) or OG_RECIPROCITY_RATIO (1).

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL mode is neither OG_RECIPROCITY_DEFAULT nor OG_RECIPROCITY_RATIO.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 280 graphs, both modes, loops on and off.

C name

og_reciprocity

In notebooks

Og.Reciprocity

igraph 1.0

igraph_reciprocity

See also

is_mutual, has_mutual

og_t g;
og_real_t r;
og_small(&g, 4, OG_DIRECTED, 0,1, 1,0, 1,2, 2,3, -1);
og_reciprocity(&g, &r, true, OG_RECIPROCITY_DEFAULT);   /* 2 of 4 edges: 0.5 */
og_reciprocity(&g, &r, true, OG_RECIPROCITY_RATIO);     /* 1 of 3 pairs: 0.333 */
og_destroy(&g);

`diversity`#

Exact

Computes the structural diversity of vertices: the evenness of their edge weights.

og_error_t og_diversity(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    const og_vs_t vids
);

For a vertex of degree d >= 2 the diversity is the Shannon entropy of its incident edge weights, normalised to sum 1, divided by log(d) (Eagle, Macy and Claxton, 2010): 1 when all weights are equal, smaller as they get uneven. Zero weights add nothing to the entropy. A vertex without edges gets NaN. A vertex of degree 1 gets 0 when its edge weight is positive and NaN when it is zero; here we use the vertex's own edge, where the reference looks at the first weight of the vector (a deliberate difference).

The graph must be undirected and without multi-edges. With weights NULL every vertex gets 1 and only the vertex selector is checked.

Parameters

graph The input graph; it is not changed.
weights Edge weights (non-negative, not NaN), or NULL.
res Receives one value per selected vertex.
vids The vertices to compute.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL With weights: the graph is directed or has multi-edges, or weights has the wrong length or a negative or NaN value.
OG_EINVVID The selector names a vertex that does not exist.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on about 180 weighted graphs, apart from the documented degree-one rule.

C name

og_diversity

In notebooks

Og.Diversity

igraph 1.0

igraph_diversity

See also

strength, degree

The graph as a matrix or an edge list

`get_adjacency`#

Exact

Builds the dense adjacency matrix of a graph.

og_error_t og_get_adjacency(
    const og_t *graph,
    og_matrix_t *res,
    og_get_adjacency_t type,
    const og_vector_t *weights,
    og_loops_t loops
);

res becomes an |V| x |V| matrix whose entry (u, v) is the number of edges u -> v, or their total weight. Parallel edges add up.

For undirected graphs type picks the part filled: OG_GET_ADJACENCY_UPPER (u < v), OG_GET_ADJACENCY_LOWER or OG_GET_ADJACENCY_BOTH (symmetric). Directed graphs ignore type. loops sets the diagonal: OG_NO_LOOPS leaves it zero, OG_LOOPS_ONCE adds 1 (or the weight) per self-loop, OG_LOOPS_TWICE adds 2 per self-loop in undirected graphs, the convention under which row sums equal degrees. In directed graphs a self-loop adds 1 under both ONCE and TWICE.

Parameters

graph The input graph; it is not changed.
res An initialized matrix; receives the adjacency matrix.
type OG_GET_ADJACENCY_UPPER (0), OG_GET_ADJACENCY_LOWER (1) or OG_GET_ADJACENCY_BOTH (2); undirected graphs only.
weights Edge weights, or NULL to count edges.
loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL type is invalid for an undirected graph, loops is invalid, or weights has the wrong length.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V|^2 + |E|).

Checked

Identical to igraph 1.0 for every type and loop mode on graphs up to 40 vertices.

C name

og_get_adjacency

In notebooks

Og.GetAdjacency

igraph 1.0

igraph_get_adjacency

`get_adjacency_sparse`#

Exact

Builds the adjacency matrix of a graph in sparse form.

og_error_t og_get_adjacency_sparse(
    const og_t *graph,
    og_sparsemat_t *res,
    og_get_adjacency_t type,
    const og_vector_t *weights,
    og_loops_t loops
);

The same values as get_adjacency(), stored in an sparsemat_t in triplet form: one entry for every cell that has at least one edge (parallel edges already summed), rows ascending and columns ascending within a row. The matrix is resized to |V| x |V| first.

Parameters

graph The input graph; it is not changed.
res An initialized sparse matrix; receives the adjacency matrix.
type OG_GET_ADJACENCY_UPPER, OG_GET_ADJACENCY_LOWER or OG_GET_ADJACENCY_BOTH; undirected graphs only.
weights Edge weights, or NULL to count edges.
loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL type is invalid for an undirected graph, loops is invalid, or weights has the wrong length.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| log d).

Checked

Equal to the dense matrix on every fixture and on 220 random multigraphs.

C name

og_get_adjacency_sparse

In notebooks

Og.GetAdjacencySparse

igraph 1.0

igraph_get_adjacency_sparse

`get_stochastic`#

Exact

Builds the transition matrix of the random walk on a graph.

og_error_t og_get_stochastic(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t column_wise,
    const og_vector_t *weights
);

Each entry of the adjacency matrix (self-loops counted twice in undirected graphs) is divided by its row's sum, so that every row sums to 1 (the transition matrix of a random walk), or with column_wise true by its column's sum, so that every column does. In a directed graph the row sums are the weighted out-degrees and the column sums the weighted in-degrees.

A vertex without edges keeps a zero row (column). A vertex whose edges weigh zero in total gets 0/0 = NaN in those edges' entries, as the reference does. Negative weights are not refused.

Parameters

graph The input graph; it is not changed.
res An initialized matrix; receives the |V| x |V| result.
column_wise false: rows sum to 1; true: columns sum to 1.
weights Edge weights, or NULL for 1 per edge.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL weights does not have one entry per edge.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V|^2 + |E|).

Checked

Checked against I - L for python-igraph's normalized Laplacians; zero-strength rows equal the native igraph 1.0.1 C library.

C name

og_get_stochastic

In notebooks

Og.GetStochastic

igraph 1.0

igraph_get_stochastic

`get_stochastic_sparse`#

Exact

Builds the random-walk transition matrix in sparse form.

og_error_t og_get_stochastic_sparse(
    const og_t *graph,
    og_sparsemat_t *res,
    og_bool_t column_wise,
    const og_vector_t *weights
);

The same values as get_stochastic(), stored in an sparsemat_t in triplet form: one entry per cell with an edge, rows ascending, columns ascending within a row.

Parameters

graph The input graph; it is not changed.
res An initialized sparse matrix; receives the result.
column_wise false: rows sum to 1; true: columns sum to 1.
weights Edge weights, or NULL for 1 per edge.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_EINVAL weights does not have one entry per edge.
OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| log d).

Checked

Equal to the dense matrix on 220 random multigraphs.

C name

og_get_stochastic_sparse

In notebooks

Og.GetStochasticSparse

igraph 1.0

igraph_get_stochastic_sparse

`get_edgelist`#

Exact

Returns the edges as a flat list of vertex pairs.

og_error_t og_get_edgelist(
    const og_t *graph,
    og_vector_int_t *res,
    og_bool_t bycol
);

res gets 2|E| vertex ids. With bycol false the pairs follow each other: from0, to0, from1, to1, ...; with bycol true all sources come first and then all targets: from0, from1, ..., to0, to1, .... Edges are in id order. Undirected edges are reported with the smaller vertex first.

Parameters

graph The input graph; it is not changed.
res Receives the 2|E| vertex ids.
bycol false: pair after pair; true: all sources, then all targets.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|E|).

Checked

Identical to the stored edges on 280 graphs.

C name

og_get_edgelist

In notebooks

Og.GetEdgelist

igraph 1.0

igraph_get_edgelist

See also

edge, create

Last updated 6 November 2026 · Open Graph 0.1.0 · OpenBI Studio 0.3.78

Components and structure

Types

loops_ttype#

neimode_ttype#

Adjacency and reachability

are_adjacent#

spanner#

subcomponent#

reachability#

count_reachable#

transitive_closure#

Components

connected_components#

is_connected#

decompose#

biconnected_components#

articulation_points#

bridges#

is_biconnected#

Percolation

site_percolation#

bond_percolation#

edgelist_percolation#

Trees and spanning trees

minimum_spanning_tree#

random_spanning_tree#

is_tree#

is_forest#

to_prufer#

Degree sequences

is_graphical#

is_bigraphical#

Direction

to_directed#

to_undirected#

Self-loops, multi-edges and mutual edges

is_simple#

is_loop#

has_loop#

count_loops#

is_multiple#

has_multiple#

count_multiple#

count_multiple_1#

is_mutual#

has_mutual#

Cores, trusses and chordal graphs

coreness#

trussness#

maximum_cardinality_search#

is_chordal#

Density and degree summaries

density#

mean_degree#

reciprocity#

diversity#

The graph as a matrix or an edge list

get_adjacency#

get_adjacency_sparse#

get_stochastic#

get_stochastic_sparse#

get_edgelist#

`loops_t`type#

`neimode_t`type#

`are_adjacent`#

`spanner`#

`subcomponent`#

`reachability`#

`count_reachable`#

`transitive_closure`#

`connected_components`#

`is_connected`#

`decompose`#

`biconnected_components`#

`articulation_points`#

`bridges`#

`is_biconnected`#

`site_percolation`#

`bond_percolation`#

`edgelist_percolation`#

`minimum_spanning_tree`#

`random_spanning_tree`#

`is_tree`#

`is_forest`#

`to_prufer`#

`is_graphical`#

`is_bigraphical`#

`to_directed`#

`to_undirected`#

`is_simple`#

`is_loop`#

`has_loop`#

`count_loops`#

`is_multiple`#

`has_multiple`#

`count_multiple`#

`count_multiple_1`#

`is_mutual`#

`has_mutual`#

`coreness`#

`trussness`#

`maximum_cardinality_search`#

`is_chordal`#

`density`#

`mean_degree`#

`reciprocity`#

`diversity`#

`get_adjacency`#

`get_adjacency_sparse`#

`get_stochastic`#

`get_stochastic_sparse`#

`get_edgelist`#