Cycles, motifs and epidemics

The type of the function simple_cycles_callback calls for each cycle.

typedef og_error_t og_cycle_handler_t(
    const og_vector_int_t *vertices,
    const og_vector_int_t *edges,
    void *arg
);

The handler receives one cycle: its vertex ids and its edge ids in walking order, and the arg pointer given to simple_cycles_callback. Both vectors are owned by the search and change after the call returns, so the handler must copy anything it keeps and must not modify or destroy them.

Parameters

• vertices The cycle's vertex ids in walking order (read only, valid during the call).
• edges The cycle's edge ids in walking order (read only, valid during the call).
• arg The caller's pointer, unchanged.

Returns

OG_SUCCESS to go on, OG_STOP to stop the search quietly, any other code to stop it with that error.

Checked

Same signature as igraph 1.0's type, with og_ names.

C name

og_cycle_handler_t

In notebooks

Og.CycleHandler

igraph 1.0

igraph_cycle_handler_t

See also

simple_cycles_callback

The type of the function motifs_randesu_callback calls for each motif.

typedef og_error_t og_motifs_handler_t(
    const og_t *graph,
    const og_vector_int_t *vids,
    og_int_t isoclass,
    void *extra
);

The handler receives the graph searched, the vertex ids of one motif and the motif's isomorphism class, plus the extra pointer given to motifs_randesu_callback. vids belongs to the search: read it during the call, copy what you keep, never modify it.

Parameters

• graph The graph being searched.
• vids The motif's vertex ids (read only, valid during the call).
• isoclass The motif's isomorphism class, as isoclass numbers it.
• extra The caller's pointer, unchanged.

Returns

OG_SUCCESS to go on, OG_STOP to stop quietly, any other code to stop with that error.

Checked

Same signature as igraph 1.0's type, with og_ names.

C name

og_motifs_handler_t

In notebooks

Og.MotifsHandler

igraph 1.0

igraph_motifs_handler_t

See also

motifs_randesu_callback

One simulated SIR epidemic: event times and compartment sizes.

typedef struct og_sir_t {
    og_vector_t times;
    og_vector_int_t no_s, no_i, no_r;
} og_sir_t;

All four vectors have the same length, one entry per event plus the start: entry 0 is time 0 with one infected vertex, and the last entry is the time the last infected vertex recovered. no_s + no_i + no_r equals |V| at every entry. sir allocates these structs; sir_destroy releases their vectors.

Parameters

• times Event times, increasing, starting at 0.
• no_s Susceptible vertices after each event.
• no_i Infected vertices after each event.
• no_r Recovered vertices after each event.

Checked

The four fields igraph 1.0's type has, with og_ vector types.

C name

og_sir_t

In notebooks

Og.SirType

igraph 1.0

igraph_sir_t

See also

sir, sir_destroy

Returns one cycle of the graph, or two empty vectors when it has none.

og_error_t og_find_cycle(
    const og_t *graph,
    og_vector_int_t *vertices,
    og_vector_int_t *edges,
    og_neimode_t mode
);

A depth-first search starts from vertex 0, then from each vertex not yet visited, and stops at the first edge that leads back to a vertex still on the search stack (a self-loop counts). That vertex and the part of the stack above it are the cycle: vertices lists them in walking order, and edges[i] is the edge from vertices[i] to the next vertex, the last one closing the cycle at vertices[0].

In a directed graph, mode OG_OUT follows edge directions, OG_IN walks them backwards and OG_ALL ignores them; in an undirected graph the mode does not matter. The edge just used to arrive is never walked back, but a parallel copy of it may be, so two parallel undirected edges form a cycle of length 2.

Which cycle is returned is Open Graph's own choice (the first one this search meets). Use simple_cycles to list them all.

Parameters

• graph The graph.
• vertices Output, may be NULL: the cycle's vertex ids in walking order (emptied when there is no cycle).
• edges Output, may be NULL: the cycle's edge ids in walking order (emptied when there is no cycle).
• mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs.

Returns

OG_SUCCESS, also when the graph has no cycle.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

python-igraph exposes no find_cycle, so the cycle chosen is not compared. Checked by properties in all three modes on the 410 DAG fixture graphs and a third of the simple-cycle fixtures (loops, multi-edges, both directednesses): a cycle comes back exactly when one exists, and it is a valid closed walk with matching edges.

C name

og_find_cycle

In notebooks

Og.FindCycle

igraph 1.0

igraph_find_cycle

See also

simple_cycles, is_dag, is_acyclic

Lists every simple cycle of the graph, as vertex lists, edge lists or both.

og_error_t og_simple_cycles(
    const og_t *graph,
    og_vector_int_list_t *vertices,
    og_vector_int_list_t *edges,
    og_neimode_t mode,
    og_int_t min_cycle_length,
    og_int_t max_cycle_length,
    og_int_t max_results
);

A simple cycle repeats no vertex. Each one is reported once. Lengths are counted in edges: a self-loop is a cycle of length 1, two parallel undirected edges (or u->v and v->u in a directed graph) a cycle of length 2. vertices and edges get one vector per cycle, at the same position for the same cycle, both in walking order.

The search is Johnson's circuit enumeration (SIAM J. Comput., 1975): one start vertex at a time, kept inside the start's strongly connected part (for undirected searches, its 2-edge-connected part), with blocking so that no dead end is walked twice. With a maximum length it uses backtracking pruned by breadth-first distances back to the start instead, since blocking is not valid under a length bound.

The order of the cycles and of the ids inside each is python-igraph 1.0's: start vertices in increasing id, neighbours in adjacency order. In a directed graph mode OG_ALL treats the edges as undirected. python-igraph 1.0 misses some directed cycles; Open Graph reports all of them, with python-igraph's list a subsequence of its own.

Parameters

• graph The graph.
• vertices Output list, may be NULL: one vertex-id vector per cycle. Cleared first.
• edges Output list, may be NULL: one edge-id vector per cycle. Cleared first.
• mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs.
• min_cycle_length Shortest cycle to report, in edges; negative means no lower bound.
• max_cycle_length Longest cycle to report, in edges; negative means no upper bound. 0, or a maximum below the minimum, gives no cycles.
• max_results Stop after this many cycles; OG_UNLIMITED (any negative value) keeps them all, 0 returns none.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL mode is not OG_OUT, OG_IN or OG_ALL (EINVAL, as python-igraph reports it, not EINVMODE).
• OG_ENOMEM Not enough memory.

Complexity

Without a maximum length O((|V| + |E|)(c + 1)) for c cycles (Johnson's bound). The number of cycles itself can grow exponentially with the graph; with a maximum length the backtracking search may take longer on dense graphs.

Checked

Identical lists in python-igraph's order on 860 fixture cases (all modes, length bounds, loops, multi-edges, 0-300 vertices) and 13,700 more random cases. In 30 directed fixture cases python-igraph 1.0 misses cycles; there an independent brute-force enumeration is the reference and Open Graph returns every cycle. Benchmark (22k-60k edges): 0.04-0.20x python-igraph's time.

C name

og_simple_cycles

In notebooks

Og.SimpleCycles

igraph 1.0

igraph_simple_cycles

See also

simple_cycles_callback, find_cycle, minimum_cycle_basis

#include "og.h"
#include <stdio.h>

int main(void) {
    og_t g;
    og_vector_int_list_t cycles;
    og_int_t i, j;
    /* directed square 0->1->2->3->0 with the chord 1->3 */
    og_small(&g, 4, OG_DIRECTED, 0,1, 1,2, 2,3, 3,0, 1,3, -1);
    og_vector_int_list_init(&cycles, 0);
    og_simple_cycles(&g, &cycles, NULL, OG_OUT, -1, -1, OG_UNLIMITED);
    for (i = 0; i < og_vector_int_list_size(&cycles); i++) {
        const og_vector_int_t *c = og_vector_int_list_get_ptr(&cycles, i);
        for (j = 0; j < og_vector_int_size(c); j++) {
            printf("%" OG_PRId " ", OG_VECTOR(*c)[j]);
        }
        printf("\n");          /* 0 1 2 3, then 0 1 3 */
    }
    og_vector_int_list_destroy(&cycles);
    og_destroy(&g);
    return 0;
}

Calls a function for every simple cycle instead of collecting them.

og_error_t og_simple_cycles_callback(
    const og_t *graph,
    og_neimode_t mode,
    og_int_t min_cycle_length,
    og_int_t max_cycle_length,
    og_cycle_handler_t *callback,
    void *arg
);

The same search as simple_cycles: the same cycles, in the same order, with the same length bounds and modes. Each cycle is handed to callback as two vectors (vertex ids and edge ids in walking order) that belong to the search and are valid only during the call; copy what you want to keep.

The handler returns OG_SUCCESS to go on, OG_STOP to end the search with success, or any other code to end it with that error. This is the way to process very many cycles without holding them in memory, or to stop at the first one that meets a condition.

Parameters

• graph The graph.
• mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs.
• min_cycle_length Shortest cycle to report, in edges; negative means no lower bound.
• max_cycle_length Longest cycle to report, in edges; negative means no upper bound.
• callback The handler, called once per cycle. Must not be NULL.
• arg Passed unchanged to every call of the handler.

Returns

OG_SUCCESS when the search finished or the handler returned OG_STOP; otherwise the handler's error code.

Errors

• OG_EINVAL callback is NULL, or mode is not OG_OUT, OG_IN or OG_ALL.
• handler's code: The handler returned an error code other than OG_STOP.
• OG_ENOMEM Not enough memory.

Complexity

As simple_cycles, plus the handler's own time.

Checked

Same engine and order as simple_cycles, compared on the same fixtures; OG_STOP ends quietly and other codes are passed on (tested).

C name

og_simple_cycles_callback

In notebooks

Og.SimpleCyclesCallback

igraph 1.0

igraph_simple_cycles_callback

See also

simple_cycles, cycle_handler_t

Returns the cycles closed by the non-tree edges of a breadth-first tree: a cycle basis.

og_error_t og_fundamental_cycles(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_list_t *result,
    og_int_t start_vid,
    og_real_t bfs_cutoff
);

Edge directions are ignored. A breadth-first search builds a spanning tree; each edge outside the tree closes exactly one cycle with the tree paths from its ends to their lowest common ancestor. Searching every component gives |E| - |V| + c cycles (c components), a basis of the cycle space. Each cycle is a vector of edge ids: the closing edge, the tree path from one end up to the common ancestor, then the path down to the other end. A self-loop is a cycle of one edge, two parallel edges one of two.

start_vid >= 0 searches only that vertex's component, from that vertex; a negative start_vid searches every component from its smallest vertex, in that order. A bfs_cutoff >= 0 stops the search at that depth, so only cycles near the root are found (then not a full basis); negative means no limit. The order of the cycles and of the edges inside each is python-igraph 1.0's.

Parameters

• graph The graph (directions ignored).
• weights Not used (as in igraph 1.0); pass NULL.
• result Output list: one edge-id vector per cycle. Cleared first.
• start_vid Root vertex, or negative for every component.
• bfs_cutoff Depth limit of the search; negative for none.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL start_vid is not a vertex of the graph (EINVAL, the code python-igraph 1.0 reports, not EINVVID).
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) for the search, plus the total length of the cycles returned.

Checked

269 fixture graphs x start (none or a random vertex) x cutoff (none, 0 to 3): identical cycles in identical order, edge order inside each cycle included.

C name

og_fundamental_cycles

In notebooks

Og.FundamentalCycles

igraph 1.0

igraph_fundamental_cycles

See also

minimum_cycle_basis, simple_cycles

Returns a cycle basis of the smallest total length (lengths in edges).

og_error_t og_minimum_cycle_basis(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_list_t *result,
    og_real_t bfs_cutoff,
    og_bool_t complete,
    og_bool_t use_cycle_order
);

Edge directions are ignored and every edge has length 1 (weights are not used). The basis has |E| - |V| + c cycles for c connected components. Candidates are the fundamental cycles of breadth-first trees grown from candidate roots (vertices of degree 2 or more that have degree 3 or more, a self-loop, or were not reached by an earlier root's search); they are sorted by length, then lexicographically by their sorted edge ids, and taken in that order whenever they are independent over GF(2) of those already taken (Horton, SIAM J. Comput., 1987).

Each cycle is a vector of edge ids, in increasing order, or in the order of a walk around the cycle starting with its smallest edge when use_cycle_order is true. The cycles come sorted by length, then lexicographically. A bfs_cutoff >= 0 limits the depth of each search, and the basis can then be incomplete; with complete true the first root of each component searches without the limit, so the basis is always complete. A negative cutoff means no limit.

Parameters

• graph The graph (directions ignored).
• weights Not used (as in igraph 1.0); pass NULL.
• result Output list: one edge-id vector per basis cycle. Cleared first.
• bfs_cutoff Depth limit of each breadth-first search; negative for none.
• complete With a cutoff: still return a complete basis.
• use_cycle_order true: edges in walking order around each cycle; false: ascending ids.

Returns

OG_SUCCESS.

Errors

• OG_ENOMEM Not enough memory.

Complexity

Polynomial: one breadth-first search per candidate root, O(|V| (|V| + |E|)) in all, then Gaussian elimination over GF(2) of the sorted candidates.

Checked

269 fixture graphs (62 of them multigraphs) x cutoff (none, 1, 2) x complete x use_cycle_order: identical bases, order and edge order; 2,100 random multigraphs x 18 argument sets identical.

C name

og_minimum_cycle_basis

In notebooks

Og.MinimumCycleBasis

igraph 1.0

igraph_minimum_cycle_basis

See also

fundamental_cycles, simple_cycles

Tests for a DAG: a directed graph without directed cycles.

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

True when the graph is directed and has no directed cycle. A self-loop is a cycle, so a graph with one is not a DAG. Undirected graphs always give false; is_acyclic answers the corresponding question for them.

The test is Kahn's (CACM, 1962): repeatedly remove a vertex with no incoming edge left; the graph is a DAG exactly when every vertex gets removed. The answer is stored in the graph's property cache, so asking again costs nothing until the graph changes.

Parameters

• graph The graph.
• res Output: true for a DAG.

Returns

OG_SUCCESS.

Errors

• OG_ENOMEM Not enough memory.

Complexity

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

Checked

410 fixture graphs (self-loops, undirected graphs), the cached answer and its reset after a change. Benchmark (20k vertices, 100k edges): 0.37x (a DAG) and 0.48x (not a DAG) python-igraph's time.

C name

og_is_dag

In notebooks

Og.IsDag

igraph 1.0

igraph_is_dag

See also

is_acyclic, topological_sorting, find_cycle, feedback_arc_set

Tells whether the graph has no cycle at all, directed or undirected.

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

For a directed graph this is is_dag: no directed cycle. For an undirected graph it asks whether the graph is a forest, so a self-loop or two parallel edges already make it cyclic. Both answers are kept in the graph's property cache.

Parameters

• graph The graph.
• res Output: true when the graph has no cycle.

Returns

OG_SUCCESS.

Errors

• OG_ENOMEM Not enough memory.

Complexity

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

Checked

410 fixture graphs, directed and undirected (loops and multi-edges included), cached and recomputed. Undirected graphs use is_forest.

C name

og_is_acyclic

In notebooks

Og.IsAcyclic

igraph 1.0

igraph_is_acyclic

See also

is_dag, is_forest, find_cycle

Orders the vertices of a DAG so that every edge points the same way along the order.

og_error_t og_topological_sorting(
    const og_t *graph,
    og_vector_int_t *res,
    og_neimode_t mode
);

With OG_OUT every edge goes from an earlier to a later vertex of res (sources first); with OG_IN every edge goes from a later to an earlier one (sinks first). Self-loops are ignored, so a graph whose only cycles are self-loops can still be sorted.

The order is Kahn's with a first-in, first-out queue: the vertices with no incoming edge (OG_OUT; no outgoing edge for OG_IN) enter the queue in increasing id, and taking a vertex out releases its successors in adjacency order. This is exactly python-igraph 1.0's order. A graph with a directed cycle has no such order: res is then emptied and the function fails.

Parameters

• graph A directed graph.
• res Output: the |V| vertex ids in order.
• mode OG_OUT (edges point forward) or OG_IN (edges point backward).

Returns

OG_SUCCESS.

Errors

• OG_EINVAL The graph is undirected (checked before the mode).
• OG_EINVAL mode is OG_ALL.
• OG_EINVAL The graph has a directed cycle other than a self-loop; res is emptied.
• OG_EINVMODE mode is not a known mode.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

Identical orders for OG_OUT and OG_IN on 410 fixture graphs. Benchmark (20k vertices, 100k edges): 0.21x (OUT) and 0.23x (IN) python-igraph's time.

C name

og_topological_sorting

In notebooks

Og.TopologicalSorting

igraph 1.0

igraph_topological_sorting

See also

is_dag, feedback_arc_set

#include "og.h"
#include <stdio.h>

int main(void) {
    og_t g;
    og_vector_int_t order;
    og_bool_t dag;
    og_int_t i;
    og_small(&g, 5, OG_DIRECTED, 3,1, 1,0, 3,2, 2,0, 4,2, -1);
    og_is_dag(&g, &dag);
    og_vector_int_init(&order, 0);
    if (dag) {
        og_topological_sorting(&g, &order, OG_OUT);
        for (i = 0; i < og_vector_int_size(&order); i++) {
            printf("%" OG_PRId " ", OG_VECTOR(order)[i]);   /* 3 4 1 2 0 */
        }
    }
    og_vector_int_destroy(&order);
    og_destroy(&g);
    return 0;
}

Finds a set of edges whose removal leaves the graph without cycles, exactly or with the Eades heuristic.

og_error_t og_feedback_arc_set(
    const og_t *graph,
    og_vector_int_t *result,
    const og_vector_t *weights,
    og_fas_algorithm_t algo
);

A feedback arc set meets every cycle: removing it leaves a DAG (directed graphs) or a forest (undirected graphs). The aim is the lightest such set (with weights) or the smallest (without). result gets the edge ids of the set in increasing order. Self-loops are always in the set.

Undirected graphs: the edges outside a maximum-weight spanning forest (without weights, a breadth-first forest), which is always optimal. Directed graphs, by algo: OG_FAS_APPROX_EADES orders the vertices greedily (Eades, Lin and Smyth, 1993: sinks to the back, sources to the front, otherwise the vertex with the largest out-weight minus in-weight) and returns the edges that point backwards: fast, not always optimal. OG_FAS_EXACT_IP and OG_FAS_EXACT_IP_CG (the same method) return a minimum-weight set: a minimum hitting set of a family of cycles that grows (shortest cycles, found by breadth-first search) until what is left is acyclic, solved per strongly connected part by Open Graph's own branch and bound, with no external solver. OG_FAS_EXACT_IP_TI reaches the same minimum through the vertex-ordering form of the problem.

With the hitting-set methods an edge of negative weight is always taken (it only lowers the total) and a DAG gives an empty set. Among equally light sets they return the colexicographically smallest by edge id, the choice python-igraph makes in the cases checked. The problem is NP-hard: the exact methods can take very long on large, dense strongly connected parts.

Parameters

• graph The graph.
• result Output, may be NULL: the edge ids of the set, ascending.
• weights Edge weights, or NULL for all 1. Length |E|, finite; negative values are allowed.
• algo og_fas_algorithm_t: OG_FAS_APPROX_EADES, OG_FAS_EXACT_IP, OG_FAS_EXACT_IP_CG or OG_FAS_EXACT_IP_TI. Not used for undirected graphs (always optimal there).

Returns

OG_SUCCESS.

Errors

• OG_EINVAL algo is not one of the four methods.
• OG_EINVAL weights does not have |E| entries, or holds NaN or an infinity.
• OG_ENOMEM Not enough memory.

Complexity

Eades: O((|V| + |E|) log |V|) with its heap. Exact methods: exponential in the worst case (NP-hard), fast when the strongly connected parts are small. Undirected graphs: O(|V| + |E|) without weights, O(|E| log |E|) with weights.

Checked

Coverage status partial. Exact methods always reach igraph's minimum weight; the same set as igraph's on 230/230 fixture graphs and 257/260 tie-heavy ones (EXACT_IP_TI: same weight on 201/201, same set on 164/201). Eades: identical on every loop-free graph and on 517 of 525 graphs with self-loops; in 3 of the rest python-igraph's own answer is not a feedback arc set, while Open Graph's always is. All 430 undirected cases identical.

C name

og_feedback_arc_set

In notebooks

Og.FeedbackArcSet

igraph 1.0

igraph_feedback_arc_set

See also

feedback_vertex_set, is_dag, topological_sorting, minimum_spanning_tree

Finds a minimum-weight set of vertices that meets every cycle.

og_error_t og_feedback_vertex_set(
    const og_t *graph,
    og_vector_int_t *result,
    const og_vector_t *vertex_weights,
    og_fvs_algorithm_t algo
);

Removing the vertices of result leaves the graph acyclic: a DAG for a directed graph (edge directions respected), a forest for an undirected one. The set is a true minimum of the total vertex weight (of the vertex count without weights). result lists the vertex ids in increasing order.

The search is Open Graph's own branch and bound for a minimum hitting set over cycles generated as needed: in directed graphs a shortest cycle through each vertex, in undirected graphs, for each edge, a shortest path between its ends that avoids it. Each strongly connected part (directed) or connected part (undirected) is solved on its own. A vertex with a self-loop, and a vertex of negative weight, is always taken; an acyclic graph gives an empty set.

When several sets are optimal, the one returned can differ from igraph's, whose choice comes from its integer-programming solver.

Parameters

• graph The graph.
• result Output, may be NULL: the vertex ids of the set, ascending.
• vertex_weights Vertex weights, or NULL for all 1. Length |V|, finite.
• algo og_fvs_algorithm_t: OG_FVS_EXACT_IP, the only method.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL algo is not OG_FVS_EXACT_IP.
• OG_EINVAL vertex_weights does not have |V| entries, or holds NaN or an infinity.
• OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case (the problem is NP-hard); fast when the cyclic parts are small.

Checked

Minimum weight equal to igraph's on all 240 fixture graphs (directed and undirected, loops, multi-edges, weights); the same set on 231 of them, other optima on the rest. Parity here means an equal optimal weight.

C name

og_feedback_vertex_set

In notebooks

Og.FeedbackVertexSet

igraph 1.0

igraph_feedback_vertex_set

See also

feedback_arc_set, is_acyclic

Tells whether the graph has an Eulerian path and whether it has an Eulerian cycle.

og_error_t og_is_eulerian(
    const og_t *graph,
    og_bool_t *has_path,
    og_bool_t *has_cycle
);

An Eulerian path uses every edge exactly once; an Eulerian cycle is such a path that ends where it started. All edges must lie in one connected part (isolated vertices do not matter; in a directed graph connectivity ignores directions). Undirected: a cycle needs every degree even, a path at most two odd degrees. Directed: a cycle needs every vertex's in-degree equal to its out-degree, a path allows one vertex with one more out-edge and one with one more in-edge. A self-loop adds 2 to its vertex's degree.

A graph without edges has both (the empty walk).

Parameters

• graph The graph.
• has_path Output, may be NULL: true when an Eulerian path exists.
• has_cycle Output, may be NULL: true when an Eulerian cycle exists.

Returns

OG_SUCCESS.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

python-igraph has no Eulerian functions: 26 cases recorded from the igraph 1.0.1 C library used as a black box, plus 600 random graphs against the degree and connectivity conditions.

C name

og_is_eulerian

In notebooks

Og.IsEulerian

igraph 1.0

igraph_is_eulerian

See also

eulerian_cycle, eulerian_path

Returns an Eulerian cycle: a closed walk that uses every edge exactly once.

og_error_t og_eulerian_cycle(
    const og_t *graph,
    og_vector_int_t *edge_res,
    og_vector_int_t *vertex_res
);

Hierholzer's algorithm with an explicit stack. The walk starts at the lowest vertex that has an edge and, at each vertex, takes the first unused edge in incidence order (undirected graphs: the edges listed by incident, directed graphs: the out-edges). edge_res gets the |E| edge ids in walking order and vertex_res the |E| + 1 vertices passed, the first repeated at the end. These rules give igraph 1.0's walks on every recorded case. A graph without edges gives two empty vectors.

Parameters

• graph The graph.
• edge_res Output, may be NULL: the edge ids in walking order.
• vertex_res Output, may be NULL: the vertex ids in walking order, start repeated at the end.

Returns

OG_SUCCESS.

Errors

• OG_ENOSOL The graph has no Eulerian cycle.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

Identical vertex and edge walks on the cases recorded from the igraph 1.0.1 C library (loops, multi-edges, isolated vertices; 10 of them predicted before recording); 600 random walks validated.

C name

og_eulerian_cycle

In notebooks

Og.EulerianCycle

igraph 1.0

igraph_eulerian_cycle

See also

eulerian_path, is_eulerian

Returns an Eulerian path: a walk that uses every edge exactly once.

og_error_t og_eulerian_path(
    const og_t *graph,
    og_vector_int_t *edge_res,
    og_vector_int_t *vertex_res
);

As eulerian_cycle, except for the start: in an undirected graph the lowest vertex of odd degree when there is one, in a directed graph the vertex with one more out-edge than in-edges when there is one, otherwise the lowest vertex that has an edge (the path is then a cycle). edge_res gets |E| edge ids, vertex_res |E| + 1 vertex ids.

Parameters

• graph The graph.
• edge_res Output, may be NULL: the edge ids in walking order.
• vertex_res Output, may be NULL: the vertex ids in walking order.

Returns

OG_SUCCESS.

Errors

• OG_ENOSOL The graph has no Eulerian path.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

Identical walks on the cases recorded from the igraph 1.0.1 C library, start vertex included.

C name

og_eulerian_path

In notebooks

Og.EulerianPath

igraph 1.0

igraph_eulerian_path

See also

eulerian_cycle, is_eulerian

Counts the mutual, asymmetric and unconnected pairs of vertices.

og_error_t og_dyad_census(
    const og_t *graph,
    og_real_t *mut,
    og_real_t *asym,
    og_real_t *null
);

Each unordered pair of distinct vertices is a dyad (Holland and Leinhardt, 1970): mutual when edges join it in both directions, asymmetric when only one direction is present, null when no edge joins it. In an undirected graph every connected pair is mutual. Self-loops are ignored and parallel edges count once. The three numbers add up to |V| (|V| - 1) / 2 and are returned as reals, which do not overflow on large graphs.

Parameters

• graph The graph.
• mut Output, may be NULL: the number of mutual pairs.
• asym Output, may be NULL: the number of asymmetric pairs.
• null Output, may be NULL: the number of unconnected pairs.

Returns

OG_SUCCESS.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

262 fixture graphs, directed and undirected, with loops and multi-edges.

C name

og_dyad_census

In notebooks

Og.DyadCensus

igraph 1.0

igraph_dyad_census

See also

triad_census, reciprocity

Counts the triads of a directed graph in each of the 16 isomorphism classes.

og_error_t og_triad_census(const og_t *graph, og_vector_t *res);

Every set of three vertices is a triad, classified by the dyads among its members (Davis and Leinhardt, 1972). res gets 16 counts in the standard MAN order: 003, 012, 102, 021D, 021U, 021C, 111D, 111U, 030T, 030C, 201, 120D, 120U, 120C, 210, 300. For example 003 is the empty triad, 012 a single edge, 102 a single mutual pair, 021D the out-star A->B, A->C, 021U the in-star, 021C the path A->B->C, 030T the transitive triad, 030C the directed 3-cycle and 300 three mutual pairs.

The count uses Batagelj and Mrvar's subquadratic method (Social Networks, 2001): each triad with at least one connected pair is found once, from its smallest connected pair, and the empty triads come by subtraction from |V| (|V| - 1) (|V| - 2) / 6. Self-loops are ignored. On multigraphs python-igraph's rule is followed for the triads with a single connected pair: a directed pair joined by two or more arcs counts as mutual (102), an undirected pair joined by two or more edges as unconnected. An undirected graph gives a warning, and each edge then counts as a mutual pair.

Parameters

• graph The graph, normally directed.
• res Output: 16 counts, resized as needed.

Returns

OG_SUCCESS.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(|E| x d_max + |V|), d_max the largest degree.

Checked

Identical to python-igraph on 262 fixture graphs, multigraphs included. Benchmark (20k vertices / 100k edges and 2k vertices / 100k edges): 0.07x and 0.03x python-igraph's time.

Threads

With set_num_threads > 1 and enough work, the vertices are split over tasks that count into their own integer counters; the sums are exactly the one-thread result for any thread count.

C name

og_triad_census

In notebooks

Og.TriadCensus

igraph 1.0

igraph_triad_census

See also

dyad_census, motifs_randesu

#include "og.h"
#include <stdio.h>

/* Who follows whom among six accounts: down a hierarchy, or round in circles? */
int main(void) {
    og_t follows;
    og_vector_t census;

    og_small(&follows, 6, OG_DIRECTED,
             1,2, 2,3, 1,3,    /* 1 follows 2 and 3, and 2 follows 3 */
             3,4, 4,5, 5,3,    /* 3, 4 and 5 follow each other round */
             -1);              /* 0 follows no one */
    og_vector_init(&census, 0);
    og_triad_census(&follows, &census);
    /* in the MAN order: 003 (no ties) at 0, 030T (transitive) at 8, 030C (a cycle) at 9 */
    printf("transitive %g, cyclic %g, without ties %g, of %g triads\n",
           OG_VECTOR(census)[8], OG_VECTOR(census)[9], OG_VECTOR(census)[0],
           og_vector_sum(&census));
    /* prints: transitive 1, cyclic 1, without ties 4, of 20 triads */
    og_vector_destroy(&census);
    og_destroy(&follows);
    return 0;
}

Counts, for each selected vertex, the triangles it belongs to.

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

A triangle is three vertices joined pairwise. Edge directions, self-loops and edge multiplicities are ignored. res[i] is the count for the i-th vertex of vids, in the selector's order.

When vids covers at least an eighth of the vertices, every triangle is listed once by the forward method of Schank and Wagner (2005) and credited to its three corners. For fewer vertices, each one's common neighbours with every neighbour are counted from the smaller side, so a high-degree neighbour costs no more than the vertex's own degree.

Parameters

• graph The graph.
• res Output: one count per selected vertex.
• vids The vertices to count for (a vertex selector, e.g. vss_all()).

Returns

OG_SUCCESS.

Errors

• OG_EINVVID vids holds a vertex id outside the graph.
• OG_ENOMEM Not enough memory.

Complexity

Many vertices: O(|E|^1.5). A few: for each, the sum over its neighbours of the smaller of the two degrees (times a logarithm for the lookups).

Checked

Not in python-igraph's API: compared with a brute-force count from the definition on 262 graphs (all vertices and one at a time, so both methods), with counts derived from python-igraph's list_triangles on 900 more random graphs, and on a 3,000-spoke wheel.

C name

og_count_adjacent_triangles

In notebooks

Og.CountAdjacentTriangles

igraph 1.0

igraph_count_adjacent_triangles

See also

count_triangles, list_triangles, transitivity_local_undirected

Counts the triangles of the graph.

og_error_t og_count_triangles(const og_t *graph, og_real_t *res);

A triangle is three vertices joined pairwise; edge directions, self-loops and edge multiplicities are ignored. The count uses the forward method of Schank and Wagner (WEA 2005): vertices are ranked by degree, largest first, and each vertex looks only towards neighbours ranked after it, so every triangle is found once. The result is a real number.

Parameters

• graph The graph.
• res Output: the number of triangles.

Returns

OG_SUCCESS.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(|E|^1.5).

Checked

Equal to the number of triangles python-igraph's list_triangles gives, on 262 graphs.

C name

og_count_triangles

In notebooks

Og.CountTriangles

igraph 1.0

igraph_count_triangles

See also

list_triangles, count_adjacent_triangles

Lists every triangle of the graph, three vertex ids each.

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

res gets 3k vertex ids for k triangles: res[3i], res[3i+1] and res[3i+2] are the corners of triangle i. Same conventions and method as count_triangles (directions, loops and multiplicities ignored; each triangle once). The order of the triangles and of the corners inside each is python-igraph 1.0's: it follows the degree ranking (largest degree first, ties by id) of the vertex each triangle is found from.

Parameters

• graph The graph.
• res Output: the corners, three per triangle.

Returns

OG_SUCCESS.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(|E|^1.5) plus the size of the output.

Checked

Identical listing, python-igraph's order, on 262 graphs.

C name

og_list_triangles

In notebooks

Og.ListTriangles

igraph 1.0

igraph_list_triangles

See also

count_triangles, count_adjacent_triangles, cliques

Counts the motifs (connected induced subgraphs) of a given size in each isomorphism class.

og_error_t og_motifs_randesu(
    const og_t *graph,
    og_vector_t *hist,
    og_int_t size,
    const og_vector_t *cut_prob
);

Every connected induced subgraph on size vertices is enumerated once, with Wernicke's ESU algorithm (IEEE/ACM TCBB, 2006): each subgraph is grown from its smallest vertex, extending only to larger neighbours. hist gets one entry per isomorphism class of graphs with size vertices, indexed as isoclass numbers the classes; the entries of classes that are not connected are NaN, since such subgraphs are never counted. Directed graphs support sizes 3 and 4 (edge directions define the class), undirected graphs sizes 3 to 6. Self-loops are ignored and parallel edges count once.

cut_prob (one entry per level of the search, or NULL) turns the count into RAND-ESU: at level d a branch is cut with probability cut_prob[d], so each subgraph is counted with probability equal to the product of (1 - cut_prob[d]). The random draws come from Open Graph's default generator. NULL or all zeros counts exactly.

Parameters

• graph The graph.
• hist Output: one count per isomorphism class (NaN for the disconnected classes).
• size Motif size: 3 or 4 for directed graphs, 3 to 6 for undirected ones.
• cut_prob Cut probabilities, one per level (length size), or NULL for an exact count.

Returns

OG_SUCCESS.

Errors

• OG_UNIMPLEMENTED size is not supported for this kind of graph.
• OG_EINVAL cut_prob does not have size entries.
• OG_ENOMEM Not enough memory.

Complexity

Proportional to the number of connected induced subgraphs of that size, which grows quickly with the size and the degrees.

Checked

With cut_prob NULL or all zeros: identical histograms (NaN classes included) for sizes 3-4 directed and 3-6 undirected on the fixture graphs. With cut probabilities (random): parity quality, the mean over seeds matches the expected count within confidence bounds.

Threads

Without cut probabilities the start vertices are split over tasks, each with its own search state and histogram; counts are whole numbers, so the result is the one-thread result. With cut probabilities the search stays on the calling thread.

C name

og_motifs_randesu

In notebooks

Og.MotifsRandesu

igraph 1.0

igraph_motifs_randesu

See also

motifs_randesu_no, motifs_randesu_estimate, motifs_randesu_callback, isoclass, triad_census

#include "og.h"
#include <stdio.h>

int main(void) {
    og_t g;
    og_vector_t hist;
    og_int_t c;
    og_famous(&g, "Zachary");
    og_vector_init(&hist, 0);
    og_motifs_randesu(&g, &hist, 3, NULL);   /* exact count */
    for (c = 0; c < og_vector_size(&hist); c++) {
        printf("class %" OG_PRId ": %g\n", c, OG_VECTOR(hist)[c]);   /* NaN for 0 and 1 */
    }
    og_vector_destroy(&hist);
    og_destroy(&g);
    return 0;
}

Counts all connected induced subgraphs of a given size, without classifying them.

og_error_t og_motifs_randesu_no(
    const og_t *graph,
    og_real_t *no,
    og_int_t size,
    const og_vector_t *cut_prob
);

The same enumeration as motifs_randesu, keeping only the total. Since no class tables are needed, any size of 3 or more works, in directed and undirected graphs. With cut_prob the total counts only the subgraphs the random search keeps (see motifs_randesu). The result is a real number.

Parameters

• graph The graph.
• no Output: the number of connected induced subgraphs found.
• size Subgraph size, 3 or more.
• cut_prob Cut probabilities, one per level (length size), or NULL.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL size is below 3.
• OG_EINVAL cut_prob does not have size entries.
• OG_ENOMEM Not enough memory.

Complexity

Proportional to the number of connected induced subgraphs of that size.

Checked

Identical totals for every size tried, also sizes without class tables, on the fixture graphs.

Threads

As motifs_randesu: start vertices split over tasks when there are no cut probabilities; whole-number counts, identical result.

C name

og_motifs_randesu_no

In notebooks

Og.MotifsRandesuNo

igraph 1.0

igraph_motifs_randesu_no

See also

motifs_randesu, motifs_randesu_estimate

Estimates the number of connected subgraphs of a given size from a sample of start vertices.

og_error_t og_motifs_randesu_estimate(
    const og_t *graph,
    og_real_t *est,
    og_int_t size,
    const og_vector_t *cut_prob,
    og_int_t sample_size,
    const og_vector_int_t *parsample
);

ESU finds each connected induced subgraph from its smallest vertex. This function runs the search from the sampled vertices only and scales the count by |V| / (sample size). With parsample the sample is the given vertices; without it, sample_size distinct vertices are drawn uniformly (a partial Fisher-Yates shuffle) with Open Graph's default random generator. Any size of 3 or more works; cut_prob applies as in motifs_randesu.

Parameters

• graph The graph.
• est Output: the estimated total.
• size Subgraph size, 3 or more.
• cut_prob Cut probabilities, one per level (length size), or NULL.
• sample_size Number of vertices to draw when parsample is NULL: 1 to |V|.
• parsample The sample of start vertices, or NULL to draw one.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL size is below 3, or cut_prob does not have size entries.
• OG_EINVAL parsample is empty.
• OG_EINVVID parsample holds a vertex id outside the graph.
• OG_EINVAL parsample is NULL and sample_size is below 1 or above |V|.
• OG_ENOMEM Not enough memory.

Complexity

Proportional to the number of subgraphs found from the sampled vertices.

Checked

With a given sample: identical to python-igraph. With a drawn sample the draws are Open Graph's own; the estimate is unbiased (tested statistically).

Threads

Without cut probabilities the sampled start vertices are split over tasks; whole-number counts, identical result. The sample itself is drawn on the calling thread.

C name

og_motifs_randesu_estimate

In notebooks

Og.MotifsRandesuEstimate

igraph 1.0

igraph_motifs_randesu_estimate

See also

motifs_randesu_no, motifs_randesu

Hands every motif found, with its vertices and its isomorphism class, to a handler.

og_error_t og_motifs_randesu_callback(
    const og_t *graph,
    og_int_t size,
    const og_vector_t *cut_prob,
    og_motifs_handler_t *callback,
    void *extra
);

The same search as motifs_randesu (sizes 3-4 directed, 3-6 undirected; cut_prob as there). For each connected induced subgraph the handler gets the graph, the subgraph's vertex ids (a vector owned by the search, valid only during the call) and its isomorphism class as isoclass numbers it. The calls come in python-igraph's order. The handler returns OG_SUCCESS to go on, OG_STOP to end the search with success, or another code to end it with that error.

Parameters

• graph The graph.
• size Motif size: 3 or 4 for directed graphs, 3 to 6 for undirected ones.
• cut_prob Cut probabilities, one per level, or NULL.
• callback The handler. Must not be NULL.
• extra Passed unchanged to every call.

Returns

OG_SUCCESS when the search finished or the handler returned OG_STOP; otherwise the handler's error code.

Errors

• OG_UNIMPLEMENTED size is not supported for this kind of graph.
• OG_EINVAL cut_prob does not have size entries, or callback is NULL.
• handler's code: The handler returned an error code other than OG_STOP.
• OG_ENOMEM Not enough memory.

Complexity

As motifs_randesu, plus the handler's own time.

Checked

The (vertex set, class) calls in python-igraph's order on the small fixture graphs; OG_STOP and error codes from the handler tested.

C name

og_motifs_randesu_callback

In notebooks

Og.MotifsRandesuCallback

igraph 1.0

igraph_motifs_randesu_callback

See also

motifs_randesu, motifs_handler_t

Decomposes a weighted graph into weighted cliques (graphlets).

og_error_t og_graphlets(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_list_t *cliques,
    og_vector_t *Mu,
    og_int_t niter
);

The model of Azari Soufiani and Airoldi (AISTATS 2012): every edge's weight is explained as the sum of the weights of the cliques that contain it. graphlets runs graphlets_candidate_basis, then graphlets_project from all-ones starting weights for niter iterations, and returns the cliques sorted by decreasing weight Mu (equal weights keep the candidate order).

The graph must be simple once directions are ignored: no self-loops, no parallel edges, no pair joined in both directions. Weights must be finite and not negative; NULL means all 1.

Parameters

• graph A simple graph (directions ignored).
• weights Edge weights, or NULL for all 1; length |E|, finite, >= 0.
• cliques Output list: the vertex ids of each graphlet.
• Mu Output: each graphlet's weight, in the order of cliques (decreasing).
• niter Number of EM iterations, >= 0.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL The graph has a self-loop, parallel edges or a mutual pair.
• OG_EINVAL weights has the wrong length, or a negative, NaN or infinite entry.
• OG_EINVAL niter is negative.
• OG_ENOMEM Not enough memory.

Complexity

The candidate search enumerates maximal cliques at every weight level (exponential in the worst case, fast on sparse graphs); each EM iteration costs the total number of edges inside the candidates.

Checked

python-igraph has no graphlets: 18 cases recorded from the igraph 1.0.1 C library (black box) and 220 model cases; cliques equal and Mu within 1e-9 (2 more recorded graphs within 7e-15 relative).

C name

og_graphlets

In notebooks

Og.Graphlets

igraph 1.0

igraph_graphlets

See also

graphlets_candidate_basis, graphlets_project, maximal_cliques

Finds the candidate cliques for a graphlet decomposition, each with its threshold.

og_error_t og_graphlets_candidate_basis(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_list_t *cliques,
    og_vector_t *thresholds
);

Algorithm 1 of Azari Soufiani and Airoldi (2012): a clique is a candidate when it is maximal in the graph of the edges of weight >= t for some weight level t. Each candidate is listed once, with its threshold: the largest such t, which is its own smallest edge weight. Isolated vertices are single-vertex candidates with an infinite threshold.

Maximal cliques are found by Bron-Kerbosch with Tomita's pivot in a degeneracy order (Eppstein, Loffler and Strash). The order of the candidates is Open Graph's own and can differ from igraph's; compare the result as a set. The graph must be simple once directions are ignored.

Parameters

• graph A simple graph (directions ignored).
• weights Edge weights, or NULL for all 1; length |E|, finite, >= 0.
• cliques Output list: the vertex ids of each candidate.
• thresholds Output, may be NULL: each candidate's threshold, in the order of cliques.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL The graph has a self-loop, parallel edges or a mutual pair.
• OG_EINVAL weights has the wrong length, or a negative, NaN or infinite entry.
• OG_ENOMEM Not enough memory.

Complexity

Maximal-clique enumeration at each weight level: exponential in the worst case, fast on sparse graphs.

Checked

Equal to igraph's candidates and thresholds as a set (order not compared) on the 18 cases recorded from the igraph 1.0.1 C library, and to the model set built from python-igraph's maximal_cliques on 220 seeded graphs.

C name

og_graphlets_candidate_basis

In notebooks

Og.GraphletsCandidateBasis

igraph 1.0

igraph_graphlets_candidate_basis

See also

graphlets, graphlets_project, maximal_cliques

Fits weights to given cliques so that together they explain the edge weights.

og_error_t og_graphlets_project(
    const og_t *graph,
    const og_vector_t *weights,
    const og_vector_int_list_t *cliques,
    og_vector_t *Mu,
    og_bool_t startMu,
    og_int_t niter
);

Expectation-maximisation (the Richardson-Lucy update) for the Poisson model of Azari Soufiani and Airoldi (2012). With lambda_e the sum of Mu over the cliques that contain edge e, one iteration updates every clique at once: Mu_k becomes Mu_k times the sum, over the edges e inside clique k, of w_e / (lambda_e + 1e-4), divided by s_k (s_k + 1) / 2, where s_k is the clique's vertex count. The constant 1e-4 and the size term were measured on the igraph 1.0.1 C library used as a black box, so the weights agree with igraph's.

startMu true starts from the values in Mu (one per clique), false from all ones. Mu receives the weights after niter iterations, in the order of cliques. Pairs inside a clique that are not edges of the graph are skipped.

Parameters

• graph A simple graph (directions ignored).
• weights Edge weights, or NULL for all 1; length |E|, finite, >= 0.
• cliques The cliques to weigh: one vertex-id vector each.
• Mu Input (when startMu is true) and output: one weight per clique.
• startMu true: start from Mu; false: start from all ones.
• niter Number of iterations, >= 0.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL The graph has a self-loop, parallel edges or a mutual pair.
• OG_EINVAL weights has the wrong length, or a negative, NaN or infinite entry.
• OG_EINVAL niter is negative, or startMu is true and Mu does not have one entry per clique.
• OG_EINVAL A clique lists the same vertex twice.
• OG_EINVVID A clique holds a vertex id outside the graph.
• OG_ENOMEM Not enough memory.

Complexity

O(niter x the total number of edges inside the cliques), after one pass that collects those edges.

Checked

Mu within 1e-9 of the answers recorded from the igraph 1.0.1 C library (given cliques, niter, startMu true and false); the measured update constants reproduce every recorded Mu to 1e-15.

C name

og_graphlets_project

In notebooks

Og.GraphletsProject

igraph 1.0

igraph_graphlets_project

See also

graphlets, graphlets_candidate_basis

Simulates the SIR epidemic model on the graph, no_sim times.

og_error_t og_sir(
    const og_t *graph,
    og_real_t beta,
    og_real_t gamma,
    og_int_t no_sim,
    og_vector_ptr_t *result
);

Each run starts with one infected vertex, drawn uniformly, and every other vertex susceptible. An infected vertex recovers at rate gamma; a susceptible vertex is infected at rate beta times its number of infected neighbours (Kermack and McKendrick's model on a network). Events are simulated exactly in continuous time with Gillespie's direct method (1977) until no vertex is infected. Each run becomes an sir_t: the event times and the numbers of susceptible, infected and recovered vertices after each event, entry 0 being the start at time 0.

The graph must be simple once directions are ignored; a directed graph is treated as undirected, with a warning. Random numbers come from Open Graph's default generator: one seed repeats the runs exactly on every platform, but the runs differ from igraph's for the same seed.

result is a pointer vector of the caller's. Whatever it held is released first; it then receives no_sim pointers to sir_t (allocated with malloc), and sir_destroy becomes its item destructor, so vector_ptr_destroy_all(result) frees everything.

Parameters

• graph A graph that is simple once directions are ignored, with at least one vertex.
• beta Infection rate per infected neighbour: finite, >= 0.
• gamma Recovery rate: finite, > 0.
• no_sim Number of runs, >= 0.
• result An initialised pointer vector; receives one sir_t * per run.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL The graph has no vertices.
• OG_EINVAL beta is negative or not finite, or gamma is not positive or not finite.
• OG_EINVAL The graph has a self-loop, parallel edges or a mutual pair.
• OG_EINVAL no_sim is negative.
• OG_ENOMEM Not enough memory.

Complexity

Per run O((|V| + |E|) log |V|): each vertex is infected and recovers at most once, and each event updates its neighbours' rates in a partial-sum tree.

Checked

python-igraph has no SIR. Mean final size and mean peak within confidence bounds of 10,000 runs per graph recorded from the igraph 1.0.1 C library (black box) on 5 graphs; closed forms for one and two vertices; seeded runs repeat exactly.

C name

og_sir

In notebooks

Og.Sir

igraph 1.0

igraph_sir

See also

sir_t, sir_destroy

#include "og.h"
#include <stdio.h>

int main(void) {
    og_t g;
    og_vector_ptr_t runs;
    og_int_t i;
    og_famous(&g, "Zachary");
    og_rng_seed(og_rng_default(), 42);
    og_vector_ptr_init(&runs, 0);
    og_sir(&g, 0.1, 1.0, 100, &runs);          /* beta 0.1, gamma 1, 100 runs */
    for (i = 0; i < 3; i++) {
        const og_sir_t *r = (const og_sir_t *) og_vector_ptr_get(&runs, i);
        og_int_t last = og_vector_size(&r->times) - 1;
        printf("run %" OG_PRId ": %" OG_PRId " recovered at t = %.2f\n", i,
               OG_VECTOR(r->no_r)[last], OG_VECTOR(r->times)[last]);
    }
    og_vector_ptr_destroy_all(&runs);           /* frees every run too */
    og_destroy(&g);
    return 0;
}

Releases the four vectors of one sir_t.

void og_sir_destroy(og_sir_t *sir);

Destroys times, no_s, no_i and no_r; the struct itself is not freed (sir allocated it with malloc, and vector_ptr_destroy_all on sir's result frees both). Safe on NULL and on a run already destroyed. sir installs it as its result vector's item destructor.

Parameters

• sir The run to release, or NULL.

Returns

Nothing.

Complexity

O(1).

Checked

Frees the four vectors; safe twice; tested as the result vector's item destructor.

C name

og_sir_destroy

In notebooks

Og.SirDestroy

igraph 1.0

igraph_sir_destroy

See also

sir, sir_t