Paths and distances

Callback type for the A* distance estimate.

typedef og_error_t og_astar_heuristic_func_t(
    og_real_t *result,
    og_int_t from,
    og_int_t to,
    void *extra
);

get_shortest_path_astar calls it as heuristic(&result, from, to, extra): store in *result an estimate of the distance from vertex from to the goal to and return OG_SUCCESS. Any other return code stops the search, and get_shortest_path_astar returns that code.

For the result to be a shortest path the estimate must never exceed the true remaining distance (admissible). If, in addition, h(u) <= w(u, v) + h(v) for every edge (consistent), no vertex is expanded twice.

Parameters

• result Where the estimate goes.
• from The vertex being reached.
• to The goal vertex.
• extra The pointer given to get_shortest_path_astar.

Returns

OG_SUCCESS to go on; any error code to stop the search.

Complexity

Called once per vertex the search reaches.

Checked

A callback type; exercised by the A* tests (a table heuristic and a failing one).

C name

og_astar_heuristic_func_t

In notebooks

Og.AstarHeuristicFunc

igraph 1.0

igraph_astar_heuristic_func_t

See also

get_shortest_path_astar

Shortest-path lengths from a set of source vertices to a set of target vertices, with the algorithm chosen from the weights.

og_error_t og_distances(
    const og_t *graph,
    const og_vector_t *weights,
    og_matrix_t *res,
    const og_vs_t from,
    const og_vs_t to,
    og_neimode_t mode
);

Fills res with one row per source and one column per target. Entry (i, j) is the length of a shortest path from the i-th source to the j-th target: 0 from a vertex to itself, +infinity when there is no path. Without weights a path's length is its number of edges; with weights it is the sum of its edge weights, and edges of weight +infinity are never used.

The algorithm follows from the weights: breadth-first search when weights is NULL, Dijkstra when no weight is negative, otherwise Bellman-Ford, or Johnson when there are more than 100 sources and edge directions are followed. In an undirected graph, or with OG_ALL, a negative edge can be walked back and forth, so it is a negative cycle (OG_ENEGCYCLE).

A target listed twice is OG_EINVAL on every route except Bellman-Ford's (negative weights and at most 100 sources), which accepts it.

Parameters

• graph The input graph.
• weights Edge weights (lengths), one per edge in edge-id order; NULL means every edge has length 1.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN.
• OG_EINVAL A target vertex is listed twice.
• OG_ENEGCYCLE A cycle of negative total weight can be reached.
• OG_ENOMEM Not enough memory.

Complexity

s sources: O(s (|V| + |E|)) unweighted; O(s (|V| + |E|) log |V|) with non-negative weights; Bellman-Ford O(s |V| |E|) in the worst case; Johnson O(|V| |E| + s (|V| + |E|) log |V|).

Checked

Identical to python-igraph 1.0 distances() on 660 seeded graphs of 0-300 vertices (unweighted, non-negative weights with zeros and +infinity, signed weights on acyclic digraphs), every mode; the switch to Johnson at 101 sources matches. With OG_IN and a subset of sources or targets, python-igraph 1.0's Johnson route gives lengths that differ from its own Bellman-Ford; Open Graph's equal Bellman-Ford's there.

Threads

Rows (one per source) are shared out among threads in chunks of 16 consecutive rows, each computed exactly as one thread computes it: the result is bit-identical at any thread count. The Bellman-Ford route runs on the calling thread.

C name

og_distances

In notebooks

Og.Distances

igraph 1.0

igraph_distances

See also

distances_cutoff, distances_dijkstra, distances_bellman_ford, distances_johnson, distances_floyd_warshall, get_shortest_paths

og_t g;
og_vector_t w;
og_matrix_t d;
og_small(&g, 4, OG_UNDIRECTED, 0, 1, 1, 2, 2, 3, 0, 3, -1);
og_vector_init_real(&w, 4, 1.0, 2.0, 1.0, 5.0);
og_matrix_init(&d, 0, 0);
og_distances(&g, &w, &d, og_vss_all(), og_vss_all(), OG_ALL);
/* MATRIX(d, 0, 3) is 4: the way round 0-1-2-3 (1 + 2 + 1) beats the direct edge (5) */
og_matrix_destroy(&d);
og_vector_destroy(&w);
og_destroy(&g);

Shortest-path lengths as distances, but paths longer than a cutoff are not followed.

og_error_t og_distances_cutoff(
    const og_t *graph,
    const og_vector_t *weights,
    og_matrix_t *res,
    const og_vs_t from,
    const og_vs_t to,
    og_neimode_t mode,
    og_real_t cutoff
);

Same output as distances, except that a target whose shortest path is longer than cutoff reports +infinity, as if it could not be reached. The searches stop at the cutoff, so a small cutoff makes them much cheaper on large graphs.

Without weights the cutoff counts edges (a fractional cutoff is rounded down). With weights the search is Dijkstra's, so negative weights are refused (OG_EINVAL); there is no Bellman-Ford fallback here. A negative or NaN cutoff means no limit.

Parameters

• graph The input graph.
• weights Edge weights (lengths), one per edge in edge-id order; NULL means every edge has length 1.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• cutoff Largest path length that is followed; negative or NaN means no limit.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_EINVAL A target vertex is listed twice.
• OG_ENOMEM Not enough memory.

Complexity

At most that of distances without negative weights; each search only visits what lies within the cutoff.

Checked

python-igraph 1.0 has no cutoff argument: compared with its distances() with every entry above the cutoff set to +infinity, several cutoffs per graph including 0 and fractional ones, unweighted and weighted.

Threads

Rows (one per source) are shared out among threads in chunks of 16 consecutive rows, each computed exactly as one thread computes it: the result is bit-identical at any thread count.

C name

og_distances_cutoff

In notebooks

Og.DistancesCutoff

igraph 1.0

igraph_distances_cutoff

See also

distances, distances_dijkstra_cutoff, neighborhood

Shortest-path lengths with non-negative weights, by Dijkstra's algorithm from each source.

og_error_t og_distances_dijkstra(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t from,
    const og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

Output as distances. Every weight must be zero or positive; an edge of weight +infinity is allowed and never used. With weights NULL every edge has length 1 and a breadth-first search is run instead.

One search per source with an indexed binary heap; the workspace is reused from source to source.

Parameters

• graph The input graph.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_EINVAL A target vertex is listed twice.
• OG_ENOMEM Not enough memory.

Complexity

O(s (|V| + |E|) log |V|) for s sources.

Checked

Identical to python-igraph 1.0 distances() on 440 seeded graphs of 0-300 vertices (unweighted, and non-negative weights with zeros and +infinity), every mode.

Threads

Rows (one per source) are shared out among threads in chunks of 16 consecutive rows, each computed exactly as one thread computes it: the result is bit-identical at any thread count.

C name

og_distances_dijkstra

In notebooks

Og.DistancesDijkstra

igraph 1.0

igraph_distances_dijkstra

See also

distances, distances_dijkstra_cutoff, get_shortest_paths_dijkstra

Dijkstra shortest-path lengths that stop at a given path length.

og_error_t og_distances_dijkstra_cutoff(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t from,
    const og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode,
    og_real_t cutoff
);

As distances_dijkstra, but a target farther than cutoff reports +infinity and the search does not go beyond the cutoff. A negative or NaN cutoff means no limit. With weights NULL the cutoff counts edges (rounded down) and a breadth-first search is used.

Parameters

• graph The input graph.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• cutoff Largest path length that is followed; negative or NaN means no limit.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_EINVAL A target vertex is listed twice.
• OG_ENOMEM Not enough memory.

Complexity

At most O(s (|V| + |E|) log |V|) for s sources; less when the cutoff is small.

Checked

Compared with python-igraph 1.0 distances() with entries above the cutoff set to +infinity (python-igraph has no cutoff); NULL weights take the breadth-first form.

Threads

Rows (one per source) are shared out among threads in chunks of 16 consecutive rows, each computed exactly as one thread computes it: the result is bit-identical at any thread count.

C name

og_distances_dijkstra_cutoff

In notebooks

Og.DistancesDijkstraCutoff

igraph 1.0

igraph_distances_dijkstra_cutoff

See also

distances_dijkstra, distances_cutoff

Shortest-path lengths that allow negative weights, by the Bellman-Ford algorithm.

og_error_t og_distances_bellman_ford(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t from,
    const og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

Output as distances. Weights may be negative. The queue form of Bellman-Ford is used: every vertex starts in a FIFO queue, and a vertex goes back into the queue whenever its distance drops. A vertex queued again more than |V| times proves a reachable cycle of negative total weight, reported as OG_ENEGCYCLE. Edges of weight +infinity are ignored.

In an undirected graph, or with OG_ALL, a negative edge can be walked back and forth and is therefore a negative cycle. With weights, a target may be listed more than once. With weights NULL a breadth-first search is run (and repeated targets are refused).

Parameters

• graph The input graph.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• weights Edge weights, one per edge, negative values allowed; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN.
• OG_ENEGCYCLE A cycle of negative total weight can be reached.
• OG_ENOMEM Not enough memory.

Complexity

O(s |V| |E|) for s sources in the worst case; usually far less.

Checked

Identical to python-igraph 1.0 distances(algorithm='bellman_ford') on 440 graphs (non-negative weights, and signed weights on acyclic digraphs); negative cycles and undirected negative edges give OG_ENEGCYCLE as there.

C name

og_distances_bellman_ford

In notebooks

Og.DistancesBellmanFord

igraph 1.0

igraph_distances_bellman_ford

See also

distances, distances_johnson, get_shortest_paths_bellman_ford

Shortest-path lengths with negative weights, by Johnson's reweighting and one Dijkstra search per source.

og_error_t og_distances_johnson(
    const og_t *graph,
    og_matrix_t *res,
    og_vs_t from,
    og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

Output as distances. Johnson's method (1977) runs Bellman-Ford once from a virtual vertex joined to every vertex by a zero-length edge, uses those distances as potentials h, gives each followed edge u -> v the new length w + h(u) - h(v), which is never negative, runs Dijkstra from each source and restores the true lengths. This pays off over plain Bellman-Ford when there are many sources.

Any negative cycle in the graph is OG_ENEGCYCLE (the virtual vertex reaches every cycle). Negative weights in an undirected graph or with OG_ALL are OG_ENEGCYCLE straight away. Without negative weights the call is distances_dijkstra; with weights NULL a breadth-first search. OG_IN is handled as the reversed problem.

Parameters

• graph The input graph.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• weights Edge weights, one per edge, negative values allowed; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN.
• OG_EINVAL A target vertex is listed twice.
• OG_ENEGCYCLE The graph has a cycle of negative total weight, or a negative edge is followed in both directions.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| |E| + s (|V| + |E|) log |V|) for s sources.

Checked

Identical to python-igraph 1.0 distances(algorithm='johnson') on 220 acyclic digraphs with signed weights, all sources. In OG_IN mode with a subset of sources or targets python-igraph 1.0's Johnson differs from its own Bellman-Ford; Open Graph equals that Bellman-Ford in every such case.

Threads

The potentials are computed once on the calling thread; the Dijkstra rows are then shared out among threads in chunks of 16, bit-identical at any thread count.

C name

og_distances_johnson

In notebooks

Og.DistancesJohnson

igraph 1.0

igraph_distances_johnson

See also

distances, distances_bellman_ford, distances_floyd_warshall

All-pairs shortest-path lengths by the Floyd-Warshall algorithm, original or tree variant.

og_error_t og_distances_floyd_warshall(
    const og_t *graph,
    og_matrix_t *res,
    og_vs_t from,
    og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode,
    const og_floyd_warshall_algorithm_t method
);

Builds a dense |V| x |V| table of shortest-path lengths, then copies the rows of from and the columns of to into res. Negative weights are allowed; a negative cycle anywhere in the graph, a negative self-loop included, is OG_ENEGCYCLE. Edges of weight +infinity are ignored; weights NULL means length 1.

method picks the variant. OG_FLOYD_WARSHALL_ORIGINAL is the textbook triple loop. OG_FLOYD_WARSHALL_TREE is the variant of Brodnik, Grgurovic and Pozar (2021): in round k the paths through k are tried in the order of the tree of best paths out of k, and a whole subtree is skipped as soon as going through k does not improve its root. OG_FLOYD_WARSHALL_AUTOMATIC currently picks the tree variant. All give the same lengths.

The table takes |V|^2 numbers whatever the size of from and to, so this suits dense graphs or cases where most pairs are wanted.

Parameters

• graph The input graph.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• weights Edge weights, one per edge, negative values allowed; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• method OG_FLOYD_WARSHALL_AUTOMATIC, OG_FLOYD_WARSHALL_ORIGINAL or OG_FLOYD_WARSHALL_TREE.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL Unknown method, or the weight vector's length differs from the number of edges, or a weight is NaN.
• OG_EINVVID A vertex id is out of range.
• OG_ENEGCYCLE The graph has a cycle of negative total weight.
• OG_ENOMEM Not enough memory.

Complexity

O(|V|^3) time in the worst case (the tree variant usually does far less); O(|V|^2) memory.

Checked

python-igraph 1.0 does not expose Floyd-Warshall: both variants compared with the python-igraph distance fixture; every OG_ENEGCYCLE checked to have a real negative cycle, every other run equal to Bellman-Ford.

C name

og_distances_floyd_warshall

In notebooks

Og.DistancesFloydWarshall

igraph 1.0

igraph_distances_floyd_warshall

See also

distances, distances_johnson, widest_path_widths_floyd_warshall

One shortest path from a source to each target, as vertex lists and edge lists.

og_error_t og_get_shortest_paths(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_list_t *vertices,
    og_vector_int_list_t *edges,
    og_int_t from,
    const og_vs_t to,
    og_neimode_t mode,
    og_vector_int_t *parents,
    og_vector_int_t *inbound_edges
);

Searches from from and writes, for each target of to in selector order, one shortest path: item i of vertices holds its vertices (the source first), item i of edges its edge ids. An unreachable target gets empty lists and a warning. The algorithm follows from the weights: breadth-first search when weights is NULL, Dijkstra when no weight is negative, Bellman-Ford otherwise. In Dijkstra an edge of weight +infinity is still followed, so a vertex reachable only through such edges gets a path of infinite length; Bellman-Ford ignores such edges.

Among several shortest paths, the one returned depends on the order in which equally distant vertices are settled; Open Graph settles them as python-igraph 1.0 does, so the same path comes back. The search stops once every target is settled.

parents and inbound_edges describe the shortest-path tree. When to does not cover every vertex the search may stop early, and they then describe only the part explored so far.

Parameters

• graph The input graph.
• weights Edge weights (lengths), one per edge in edge-id order; NULL means every edge has length 1.
• vertices Integer-vector list (may be NULL), resized to |to|; item i receives the vertices of the path to the i-th target, the source first.
• edges Integer-vector list (may be NULL), resized to |to|; item i receives the edge ids of the path to the i-th target.
• from The source vertex.
• to Vertex selector of the targets, in the order the paths are wanted; repeats allowed.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• parents Integer vector or NULL. Resized to |V|: the previous vertex on each vertex's path, -1 for the source, -2 for a vertex not reached.
• inbound_edges Integer vector or NULL. Resized to |V|: the edge through which each vertex was reached, -1 for the source and for vertices not reached.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN.
• OG_ENEGCYCLE Negative weights: a negative cycle can be reached from from, or weights of -infinity close a loop.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) unweighted, O((|V| + |E|) log |V|) with non-negative weights, O(|V| |E|) worst case with negative weights.

Checked

Vertex and edge paths identical to python-igraph 1.0 get_shortest_paths() on 630 graphs from up to 4 sources, every mode, with many equal-length ties (integer weights 1-4 with zeros and +infinity) and signed weights; parents and inbound_edges (not returned by python-igraph) checked against the paths.

C name

og_get_shortest_paths

In notebooks

Og.GetShortestPaths

igraph 1.0

igraph_get_shortest_paths

See also

get_shortest_path, get_shortest_paths_dijkstra, get_shortest_paths_bellman_ford, get_all_shortest_paths, distances

A shortest route from a given source to a given target.

og_error_t og_get_shortest_path(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_t *vertices,
    og_vector_int_t *edges,
    og_int_t from,
    og_int_t to,
    og_neimode_t mode
);

The single-target form of get_shortest_paths: vertices receives the path's vertices from from to to, edges its edge ids; either may be NULL. The search stops as soon as to is settled. An unreachable target gives empty vectors and a warning; from equal to to gives the one-vertex path. The algorithm is chosen from the weights as in get_shortest_paths, and ties are broken the same way.

Parameters

• graph The input graph.
• weights Edge weights (lengths), one per edge in edge-id order; NULL means every edge has length 1.
• vertices Integer vector or NULL; receives the path's vertices from from to to.
• edges Integer vector or NULL; receives the path's edge ids in walking order.
• from The source vertex.
• to The target vertex.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN.
• OG_ENEGCYCLE A cycle of negative total weight can be reached.
• OG_ENOMEM Not enough memory.

Complexity

As get_shortest_paths; usually less, since the search stops at the target.

Checked

Identical to python-igraph 1.0 get_shortest_path() on the same fixture, unweighted, weighted and signed.

C name

og_get_shortest_path

In notebooks

Og.GetShortestPath

igraph 1.0

igraph_get_shortest_path

See also

get_shortest_paths, get_shortest_path_dijkstra, get_shortest_path_bellman_ford, get_shortest_path_astar

One shortest path from a source to each target with non-negative weights (Dijkstra).

og_error_t og_get_shortest_paths_dijkstra(
    const og_t *graph,
    og_vector_int_list_t *vertices,
    og_vector_int_list_t *edges,
    og_int_t from,
    og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode,
    og_vector_int_t *parents,
    og_vector_int_t *inbound_edges
);

As get_shortest_paths, but always Dijkstra's algorithm: a negative weight is OG_EINVAL. An edge of weight +infinity is still followed, so a vertex reachable only through such edges gets a path of infinite length, as in python-igraph. weights NULL means a breadth-first search. Same outputs, tie-breaking, warning and early stop.

Parameters

• graph The input graph.
• vertices Integer-vector list (may be NULL), resized to |to|; item i receives the vertices of the path to the i-th target, the source first.
• edges Integer-vector list (may be NULL), resized to |to|; item i receives the edge ids of the path to the i-th target.
• from The source vertex.
• to Vertex selector of the targets, in the order the paths are wanted; repeats allowed.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• parents Integer vector or NULL. Resized to |V|: the previous vertex on each vertex's path, -1 for the source, -2 for a vertex not reached.
• inbound_edges Integer vector or NULL. Resized to |V|: the edge through which each vertex was reached, -1 for the source and for vertices not reached.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

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

Checked

Identical to python-igraph 1.0 get_shortest_paths(algorithm='dijkstra') on the tie-heavy weighted family; NULL weights equal the breadth-first form.

C name

og_get_shortest_paths_dijkstra

In notebooks

Og.GetShortestPathsDijkstra

igraph 1.0

igraph_get_shortest_paths_dijkstra

See also

get_shortest_paths, get_shortest_path_dijkstra, distances_dijkstra

A shortest route from a given source to a given target, non-negative weights (Dijkstra).

og_error_t og_get_shortest_path_dijkstra(
    const og_t *graph,
    og_vector_int_t *vertices,
    og_vector_int_t *edges,
    og_int_t from,
    og_int_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

The single-target form of get_shortest_paths_dijkstra. The search stops as soon as to is settled, which makes this the cheapest way to ask for one route. vertices and edges (either may be NULL) receive the path; an unreachable target gives empty vectors and a warning. A negative weight is OG_EINVAL; weights NULL means a breadth-first search.

Parameters

• graph The input graph.
• vertices Integer vector or NULL; receives the path's vertices from from to to.
• edges Integer vector or NULL; receives the path's edge ids in walking order.
• from The source vertex.
• to The target vertex.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O((|V| + |E|) log |V|) in the worst case; less when the target is near.

Checked

Tier 1. Identical to python-igraph 1.0 get_shortest_path(algorithm='dijkstra') on 240 fixture graphs (8 targets per source and mode on the larger ones) and on 400 more queries in graphs of 1,000-8,000 vertices; benchmark 0.25-0.30x python-igraph's time.

C name

og_get_shortest_path_dijkstra

In notebooks

Og.GetShortestPathDijkstra

igraph 1.0

igraph_get_shortest_path_dijkstra

See also

get_shortest_path, get_shortest_paths_dijkstra, get_shortest_path_astar

og_t g;
og_vector_t w;
og_vector_int_t vpath, epath;
og_small(&g, 4, OG_UNDIRECTED, 0, 1, 1, 2, 2, 3, 0, 3, -1);
og_vector_init_real(&w, 4, 1.0, 2.0, 1.0, 5.0);
og_vector_int_init(&vpath, 0);
og_vector_int_init(&epath, 0);
og_get_shortest_path_dijkstra(&g, &vpath, &epath, 0, 3, &w, OG_OUT);
/* vpath = 0 1 2 3, epath = 0 1 2 (length 4, not the direct edge of length 5) */
og_vector_int_destroy(&epath);
og_vector_int_destroy(&vpath);
og_vector_destroy(&w);
og_destroy(&g);

One shortest path from a source to each target, negative weights allowed (Bellman-Ford).

og_error_t og_get_shortest_paths_bellman_ford(
    const og_t *graph,
    og_vector_int_list_t *vertices,
    og_vector_int_list_t *edges,
    og_int_t from,
    og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode,
    og_vector_int_t *parents,
    og_vector_int_t *inbound_edges
);

As get_shortest_paths, but always the queue form of Bellman-Ford, so weights may be negative. Edges of weight +infinity are ignored. A negative cycle reachable from from, or weights of -infinity that close a loop of parent edges, is OG_ENEGCYCLE. weights NULL means a breadth-first search. The search does not stop early, so parents and inbound_edges always describe the whole tree.

Parameters

• graph The input graph.
• vertices Integer-vector list (may be NULL), resized to |to|; item i receives the vertices of the path to the i-th target, the source first.
• edges Integer-vector list (may be NULL), resized to |to|; item i receives the edge ids of the path to the i-th target.
• from The source vertex.
• to Vertex selector of the targets, in the order the paths are wanted; repeats allowed.
• weights Edge weights, one per edge, negative values allowed; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• parents Integer vector or NULL. Resized to |V|: the previous vertex on each vertex's path, -1 for the source, -2 for a vertex not reached.
• inbound_edges Integer vector or NULL. Resized to |V|: the edge through which each vertex was reached, -1 for the source and for vertices not reached.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN.
• OG_ENEGCYCLE A negative cycle can be reached from from, or weights of -infinity close a loop.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| |E|) in the worst case.

Checked

Identical to python-igraph 1.0 get_shortest_paths(algorithm='bellman_ford') on the tie-heavy and signed families.

C name

og_get_shortest_paths_bellman_ford

In notebooks

Og.GetShortestPathsBellmanFord

igraph 1.0

igraph_get_shortest_paths_bellman_ford

See also

get_shortest_paths, get_shortest_path_bellman_ford, distances_bellman_ford

A shortest route from a given source to a given target, negative weights allowed (Bellman-Ford).

og_error_t og_get_shortest_path_bellman_ford(
    const og_t *graph,
    og_vector_int_t *vertices,
    og_vector_int_t *edges,
    og_int_t from,
    og_int_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

The single-target form of get_shortest_paths_bellman_ford. vertices and edges (either may be NULL) receive the path; an unreachable target gives empty vectors and a warning.

Parameters

• graph The input graph.
• vertices Integer vector or NULL; receives the path's vertices from from to to.
• edges Integer vector or NULL; receives the path's edge ids in walking order.
• from The source vertex.
• to The target vertex.
• weights Edge weights, one per edge, negative values allowed; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN.
• OG_ENEGCYCLE A negative cycle can be reached from from, or weights of -infinity close a loop.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| |E|) in the worst case.

Checked

Identical to python-igraph 1.0 get_shortest_path(algorithm='bellman_ford') on single targets of the signed family.

C name

og_get_shortest_path_bellman_ford

In notebooks

Og.GetShortestPathBellmanFord

igraph 1.0

igraph_get_shortest_path_bellman_ford

See also

get_shortest_paths_bellman_ford, get_shortest_path

A shortest route from a given source to a given target by A* search, guided by an estimate of the remaining distance.

og_error_t og_get_shortest_path_astar(
    const og_t *graph,
    og_vector_int_t *vertices,
    og_vector_int_t *edges,
    og_int_t from,
    og_int_t to,
    const og_vector_t *weights,
    og_neimode_t mode,
    og_astar_heuristic_func_t *heuristic,
    void *extra
);

A* (Hart, Nilsson and Raphael, 1968) is Dijkstra's search ordered by g(v) + h(v): the length of the best path found to v plus the heuristic's estimate of the distance from v to to. The heuristic is called once per vertex, when the search first reaches it; NULL means the estimate 0, which is plain Dijkstra. Weights must be non-negative (NULL: length 1); edges of weight +infinity are skipped.

The path is a shortest one whenever the heuristic never overestimates. A vertex finished too early, which an admissible but inconsistent heuristic can cause, is reopened when a strictly shorter path to it turns up; with a consistent heuristic no vertex is reopened. If the heuristic returns an error code, the search stops and that code is returned. An unreachable target gives empty vectors and a warning.

Parameters

• graph The input graph.
• vertices Integer vector or NULL; receives the path's vertices from from to to.
• edges Integer vector or NULL; receives the path's edge ids in walking order.
• from The source vertex.
• to The target vertex.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• heuristic The distance estimate (astar_heuristic_func_t), or NULL for 0.
• extra Passed unchanged to every heuristic call.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• the heuristic's code: The heuristic returned something other than OG_SUCCESS; the search was abandoned.
• OG_ENOMEM Not enough memory.

Complexity

O((|V| + |E|) log |V|) plus one heuristic call per vertex reached, with a consistent heuristic; an inconsistent one may reopen vertices.

Checked

Vertex and edge paths identical to python-igraph 1.0 get_shortest_path_astar() on 220 graphs, 4 queries each, with the zero heuristic and an admissible one. An admissible but inconsistent heuristic is not compared with python-igraph 1.0; there Open Graph returns a shortest path (hand-worked test).

C name

og_get_shortest_path_astar

In notebooks

Og.GetShortestPathAstar

igraph 1.0

igraph_get_shortest_path_astar

See also

astar_heuristic_func_t, get_shortest_path_dijkstra

/* estimate: the gap between the vertices' x coordinates (never too large here) */
static og_error_t gap(og_real_t *result, og_int_t from, og_int_t to, void *extra) {
    const og_real_t *x = (const og_real_t *) extra;
    *result = x[to] > x[from] ? x[to] - x[from] : x[from] - x[to];
    return OG_SUCCESS;
}

og_t g;
og_vector_int_t vpath;
og_real_t x[4] = {0, 1, 2, 3};
og_small(&g, 4, OG_UNDIRECTED, 0, 1, 1, 2, 2, 3, -1);
og_vector_int_init(&vpath, 0);
og_get_shortest_path_astar(&g, &vpath, NULL, 0, 3, NULL, OG_ALL, gap, x);
/* vpath = 0 1 2 3 */
og_vector_int_destroy(&vpath);
og_destroy(&g);

Every shortest path from one source to the chosen targets, and the number of shortest paths to each vertex.

og_error_t og_get_all_shortest_paths(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_list_t *vertices,
    og_vector_int_list_t *edges,
    og_vector_int_t *nrgeo,
    og_int_t from,
    const og_vs_t to,
    og_neimode_t mode
);

Lists all shortest paths from from to the vertices of to (a target listed twice counts once). The paths are appended to vertices (vertex lists) and edges (edge lists), target by target in increasing vertex id; parallel edges give separate paths. The order of the paths for one target reproduces python-igraph 1.0's listing.

Without weights the search is breadth-first. With weights it is Dijkstra's and weights must be non-negative; lengths within a relative 1e-10 of each other count as equal, so ties survive rounding, and a zero-weight edge between two equally distant vertices is not another way in.

nrgeo[v] counts how many shortest paths lead from from to v. It is exact for the targets; when to does not cover every vertex the search may stop early and the counts of other vertices can be partial. The number of paths can grow exponentially; nrgeo alone (vertices and edges NULL) costs only the search.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• vertices Integer-vector list (may be NULL); cleared, then one vertex path appended per shortest path.
• edges Integer-vector list (may be NULL) for the matching edge paths.
• nrgeo Integer vector or NULL; resized to |V|, the number of shortest paths to each vertex.
• from The source vertex.
• to Vertex selector of the targets.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

The search, O(|V| + |E|) or O((|V| + |E|) log |V|), plus the total length of the paths listed.

Checked

Paths in python-igraph 1.0's listing order on 420 graphs of up to 40 vertices with many ties, every mode, target subsets with repeats; nrgeo checked against the listed paths. +infinity weights tested by hand (python-igraph aborts on them).

C name

og_get_all_shortest_paths

In notebooks

Og.GetAllShortestPaths

igraph 1.0

igraph_get_all_shortest_paths

See also

get_all_shortest_paths_dijkstra, get_shortest_paths, get_k_shortest_paths

Every shortest path from one source to the chosen targets, with non-negative weights.

og_error_t og_get_all_shortest_paths_dijkstra(
    const og_t *graph,
    og_vector_int_list_t *vertices,
    og_vector_int_list_t *edges,
    og_vector_int_t *nrgeo,
    og_int_t from,
    og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

Same as get_all_shortest_paths, with the weights later in the argument list. With weights the search is Dijkstra's, lengths within a relative 1e-10 count as equal; weights NULL means a breadth-first search.

Parameters

• graph The input graph.
• vertices Integer-vector list (may be NULL); one vertex path per shortest path.
• edges Integer-vector list (may be NULL) for the matching edge paths.
• nrgeo Integer vector or NULL; resized to |V|, the number of shortest paths to each vertex.
• from The source vertex.
• to Vertex selector of the targets.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O((|V| + |E|) log |V|) plus the total length of the paths listed.

Checked

Identical to python-igraph 1.0 get_all_shortest_paths(weights=...) on the weighted family of the same fixture, in its order.

C name

og_get_all_shortest_paths_dijkstra

In notebooks

Og.GetAllShortestPathsDijkstra

igraph 1.0

igraph_get_all_shortest_paths_dijkstra

See also

get_all_shortest_paths, get_shortest_paths_dijkstra

The k shortest paths without repeated vertices between two vertices, by Yen's algorithm.

og_error_t og_get_k_shortest_paths(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_list_t *vertex_paths,
    og_vector_int_list_t *edge_paths,
    og_int_t k,
    og_int_t from,
    og_int_t to,
    og_neimode_t mode
);

Returns up to k loopless paths from from to to in order of increasing length, as vertex lists in vertex_paths and edge lists in edge_paths (either may be NULL). Yen's algorithm (1971): the next path is the best candidate made of a prefix (root) of an accepted path plus a shortest spur path from the root's last vertex that avoids the root's other vertices and the edges the accepted paths with the same root take next. Fewer than k paths come back when fewer exist; parallel edges give distinct paths.

k = 0 gives no paths and a negative k only the shortest path; from equal to to gives the one-vertex path. Weights must be non-negative (NULL: length 1). A path through an edge of infinite weight is not reported, one whose finite weights only add up to +infinity is. Equally long candidates are taken in python-igraph 1.0's order.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• vertex_paths Integer-vector list (may be NULL); cleared, then one vertex path per result.
• edge_paths Integer-vector list (may be NULL) for the matching edge paths.
• k How many paths are wanted.
• from The source vertex.
• to The target vertex.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O(k |V| (|E| + |V| log |V|)): up to |V| spur searches per accepted path.

Checked

Vertex and edge paths in python-igraph 1.0's order on 450 graphs (up to 300 vertices), k from 1 to 8, every mode, weighted and not; overflowing path lengths handled as python-igraph handles them.

C name

og_get_k_shortest_paths

In notebooks

Og.GetKShortestPaths

igraph 1.0

igraph_get_k_shortest_paths

See also

get_all_shortest_paths, get_all_simple_paths, get_shortest_path

Every simple path (no vertex twice) from a source to the chosen targets.

og_error_t og_get_all_simple_paths(
    const og_t *graph,
    og_vector_int_list_t *res,
    og_int_t from,
    const og_vs_t to,
    og_neimode_t mode,
    og_int_t minlen,
    og_int_t maxlen,
    og_int_t max_results
);

A depth-first search from from lists in res each path that reaches a vertex of to, as the list of its vertices, the source first. Neighbours are visited in increasing id order; parallel edges count once and self-loops are ignored, so each vertex sequence appears once. A path is reported when the search enters a target, and the search goes on past it, so paths through one target to another are listed too. The source alone is never reported.

minlen and maxlen bound the number of edges: a negative minlen means 0, a negative maxlen no limit, maxlen 0 gives nothing. max_results stops the listing after that many paths (0 gives nothing, negative no limit); the paths kept are always the first ones of the full listing.

Parameters

• graph The input graph.
• res List of integer vectors; cleared, then one vertex path appended per path found.
• from The source vertex.
• to Vertex selector of the targets.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• minlen Fewest edges a reported path has; negative means 0.
• maxlen Most edges a reported path has; negative means no limit.
• max_results Stop after this many paths; negative means no limit.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ENOMEM Not enough memory.

Complexity

Proportional to the number of paths explored times their length: exponential in general. Use maxlen or max_results on anything but small graphs.

Checked

Identical to python-igraph 1.0 get_all_simple_paths(), in its order, on 210 graphs of up to 11 vertices with random target sets, minlen, maxlen and modes; max_results keeps the same prefix.

C name

og_get_all_simple_paths

In notebooks

Og.GetAllSimplePaths

igraph 1.0

igraph_get_all_simple_paths

See also

get_k_shortest_paths, get_all_shortest_paths

Mean shortest-path length over the ordered pairs of distinct vertices that are connected.

og_error_t og_average_path_length(
    const og_t *graph,
    const og_vector_t *weights,
    og_real_t *res,
    og_real_t *unconn_pairs,
    og_bool_t directed,
    og_bool_t unconn
);

Averages d(u, v) over the ordered pairs (u, v), u != v, with a path from u to v. With weights the lengths are weighted sums and must come from non-negative weights. directed false ignores edge directions.

Pairs without a path are counted in unconn_pairs (ordered pairs, so an undirected graph counts each one twice). With unconn true they are left out of the mean; with unconn false a single such pair makes the result +infinity. A graph without any connected pair (fewer than two vertices, or no edges) gives NaN.

Weighted lengths are added pair by pair in the reference's own order, so weighted results are bit-identical to python-igraph 1.0, not just close.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• res Receives the mean, or NULL.
• unconn_pairs Receives the number of ordered pairs without a path, or NULL.
• directed Respect edge directions (directed graphs only) when true, ignore them (false).
• unconn true: average over connected pairs only; false: +infinity as soon as one pair is not connected.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| (|V| + |E|)) unweighted; O(|V| (|V| + |E|) log |V|) weighted.

Checked

Tier 1. Identical to python-igraph 1.0 average_path_length() on 690 graphs of 0-300 vertices, directed or not, unconn both ways; bit for bit with weights on 400 of 400 weighted graphs. Benchmark 0.87x (unweighted) and 0.49x (weighted) python-igraph's time.

Threads

One search per source on the thread layer; the distances are added into the running totals in the one-thread order (an ordered stream), so the bits do not depend on the thread count.

C name

og_average_path_length

In notebooks

Og.AveragePathLength

igraph 1.0

igraph_average_path_length

See also

path_length_hist, global_efficiency, diameter, distances

og_t g;
og_real_t apl, unconn;
og_small(&g, 5, OG_UNDIRECTED, 0, 1, 1, 2, 3, 4, -1);   /* two pieces */
og_average_path_length(&g, NULL, &apl, &unconn, OG_UNDIRECTED, true);
/* apl = 1.25: (0,1) (1,2) (3,4) at 1 and (0,2) at 2, each both ways;
 * unconn = 12 ordered pairs without a path */
og_destroy(&g);

Histogram of the unweighted shortest-path lengths between connected pairs.

og_error_t og_path_length_hist(
    const og_t *graph,
    og_vector_t *res,
    og_real_t *unconnected,
    og_bool_t directed
);

res[i] counts the vertex pairs at distance i + 1, so res has as many entries as the longest such distance (none for a graph without connected pairs). With directed true in a directed graph pairs are ordered and directions are followed; otherwise directions are ignored and each unordered pair counts once. unconnected receives the number of pairs, counted the same way, with no path. Weights are not used.

Parameters

• graph The input graph.
• res Real vector; resized and filled with the counts.
• unconnected Receives the number of pairs without a path, or NULL.
• directed Respect edge directions (directed graphs only).

Returns

OG_SUCCESS, or the error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

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

Checked

Identical to python-igraph 1.0 path_length_hist() (bins and unconnected count) on the unweighted graphs of the path_stats fixture, 0-300 vertices, directed and not.

Threads

One breadth-first search per source on the thread layer; each task counts into its own integer histogram and the counts are summed exactly.

C name

og_path_length_hist

In notebooks

Og.PathLengthHist

igraph 1.0

igraph_path_length_hist

See also

average_path_length, diameter

The longest shortest-path length in the graph, with its end points and one path between them.

og_error_t og_diameter(
    const og_t *graph,
    const og_vector_t *weights,
    og_real_t *res,
    og_int_t *from,
    og_int_t *to,
    og_vector_int_t *vertex_path,
    og_vector_int_t *edge_path,
    og_bool_t directed,
    og_bool_t unconn
);

Runs one search per source and returns the largest distance found. from and to receive the pair that attains it (the first source, by id, reaching the largest distance, and its first vertex at that distance in settling order, as python-igraph reports), vertex_path and edge_path one shortest path between them. Any output may be NULL.

With unconn true the result is the largest distance over connected pairs. With unconn false a graph that is not connected (strongly, when directions count) gives +infinity, from and to -1 and empty paths. directed false ignores edge directions. Weights must be non-negative. The null graph gives NaN and -1.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• res Receives the diameter, or NULL.
• from Receives the first end point, or NULL.
• to Receives the second end point, or NULL.
• vertex_path Integer vector or NULL; receives the vertices of a longest shortest path.
• edge_path Integer vector or NULL; receives its edge ids.
• directed Respect edge directions (directed graphs only).
• unconn true: largest distance over connected pairs; false: +infinity for a disconnected graph.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| (|V| + |E|)) unweighted; O(|V| (|V| + |E|) log |V|) weighted.

Checked

Tier 1. Value, end points (farthest_points()) and path (get_diameter()) identical to python-igraph 1.0 on 690 graphs, directed or not, unconn both ways, weighted and not. Benchmark 0.84x unweighted, 0.28x weighted.

Threads

Per-source maxima on the thread layer; the winner is then picked in source order, as one thread picks it. Without unconn, the first source that misses a vertex settles the answer and the tasks stop.

C name

og_diameter

In notebooks

Og.Diameter

igraph 1.0

igraph_diameter

See also

pseudo_diameter, eccentricity, radius, average_path_length

og_t g;
og_real_t diam;
og_int_t from, to;
og_vector_int_t path;
og_ring(&g, 6, OG_UNDIRECTED, false, false);   /* the path 0-1-2-3-4-5 */
og_vector_int_init(&path, 0);
og_diameter(&g, NULL, &diam, &from, &to, &path, NULL, OG_UNDIRECTED, true);
/* diam = 5, from = 0, to = 5, path = 0 1 2 3 4 5 */
og_vector_int_destroy(&path);
og_destroy(&g);

Girth: how many edges the shortest cycle has, and one such cycle.

og_error_t og_girth(
    const og_t *graph,
    og_real_t *girth,
    og_vector_int_t *circle
);

Works on the simple undirected graph underneath: edge directions, self-loops and parallel edges are ignored, so the shortest possible cycle has 3 edges. A forest (recognised first, in linear time) gives +infinity and an empty circle.

Otherwise a breadth-first search from each vertex in turn (Itai and Rodeh, 1977) looks for the first edge that closes a cycle through the root; a search ends once nothing shorter can turn up, and the whole run ends at a triangle. circle lists the vertices of the cycle found; which one of several shortest cycles is returned matches python-igraph 1.0.

Parameters

• graph The input graph.
• girth Receives the girth, or NULL.
• circle Integer vector or NULL; receives the cycle's vertices in order.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) for a forest; O(|V| (|V| + |E|)) in the worst case.

Checked

Girth and circle identical to python-igraph 1.0 girth(True) on 356 graphs (random up to 300 vertices, sparse, bipartite, grids, named graphs).

C name

og_girth

In notebooks

Og.Girth

igraph 1.0

igraph_girth

See also

diameter

Eccentricity of the chosen vertices: the distance to the farthest vertex each one reaches.

og_error_t og_eccentricity(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    og_vs_t vids,
    og_neimode_t mode
);

For each vertex of vids, in selector order, the largest shortest-path length to any vertex it reaches along mode. Vertices it cannot reach are ignored, so an isolated vertex has eccentricity 0.

Weights must be non-negative (NULL: length 1); edges of weight +infinity are not followed, and a vertex whose path length overflows to +infinity (finite weights near 1e308) counts as unreachable, as in python-igraph 1.0. Weighted values are bit-identical to the reference's.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• res Real vector; resized to |vids| and filled.
• vids Vertex selector of the vertices whose values are returned, in selector order.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_EINVVID A vertex id is out of range.
• OG_ENOMEM Not enough memory.

Complexity

O(s (|V| + |E|)) unweighted, O(s (|V| + |E|) log |V|) weighted, for s chosen vertices.

Checked

Tier 1. Identical to python-igraph 1.0 eccentricity() on 690 graphs, every mode, weighted and not, plus 21,600 cases with overflowing weights. Benchmark 0.67x unweighted, 0.44x weighted.

Threads

One search per source on the thread layer; each source's result goes to its own place and the answer is bit-identical at any thread count.

C name

og_eccentricity

In notebooks

Og.Eccentricity

igraph 1.0

igraph_eccentricity

See also

radius, graph_center, diameter

og_t g;
og_vector_t ecc;
og_star(&g, 5, OG_STAR_UNDIRECTED, 0);
og_vector_init(&ecc, 0);
og_eccentricity(&g, NULL, &ecc, og_vss_all(), OG_ALL);
/* ecc = 1 2 2 2 2: the centre reaches everyone in one step */
og_vector_destroy(&ecc);
og_destroy(&g);

The smallest eccentricity in the graph.

og_error_t og_radius(
    const og_t *graph,
    const og_vector_t *weights,
    og_real_t *radius,
    og_neimode_t mode
);

The minimum of eccentricity over all vertices along mode, with the same rules for weights and unreachable vertices (so an isolated vertex makes the radius 0). The null graph gives NaN.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• radius Receives the radius, or NULL.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| (|V| + |E|)) unweighted; O(|V| (|V| + |E|) log |V|) weighted.

Checked

Identical to python-igraph 1.0 radius() on 690 graphs, every mode, and on 21,600 cases with overflowing weights.

Threads

One search per source on the thread layer; each source's result goes to its own place and the answer is bit-identical at any thread count.

C name

og_radius

In notebooks

Og.Radius

igraph 1.0

igraph_radius

See also

eccentricity, graph_center

The vertices of smallest eccentricity.

og_error_t og_graph_center(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_t *res,
    og_neimode_t mode
);

The ids of every vertex whose eccentricity (eccentricity along mode) equals the radius, in increasing order; empty for the null graph. The comparison is exact, so with real weights near-ties are not merged; integer weights give exact ties.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• res Integer vector; receives the centre's vertex ids.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| (|V| + |E|)) unweighted; O(|V| (|V| + |E|) log |V|) weighted.

Checked

python-igraph 1.0 does not expose graph_center: derived from its eccentricity() on 690 graphs, every mode, and on 21,600 cases with overflowing weights.

Threads

One search per source on the thread layer; each source's result goes to its own place and the answer is bit-identical at any thread count.

C name

og_graph_center

In notebooks

Og.GraphCenter

igraph 1.0

igraph_graph_center

See also

eccentricity, radius

A quick lower bound of the diameter from repeated farthest-vertex sweeps.

og_error_t og_pseudo_diameter(
    const og_t *graph,
    const og_vector_t *weights,
    og_real_t *diameter,
    og_int_t vid_start,
    og_int_t *from,
    og_int_t *to,
    og_bool_t directed,
    og_bool_t unconn
);

Starting at vid_start (a random vertex when negative, drawn from Open Graph's random generator), a search finds the farthest vertex; the search is repeated from there as long as the distance grows (George and Liu, 1979). Among equally far vertices the one of smallest degree is taken, then the first found. In a directed graph with directed true, forward sweeps from the current source alternate with backward sweeps into the current target. diameter is the distance between the final pair from, to, and never exceeds the true diameter.

With unconn false, a start that does not reach every vertex (in both directions for a directed graph) gives +infinity and -1 for both ends; with unconn true the answer stays within the start's component. Weights must be non-negative. The null graph gives NaN and -1.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• diameter Receives the estimate, or NULL.
• vid_start First vertex; negative picks one at random.
• from Receives one end of the final pair, or NULL.
• to Receives the other end, or NULL.
• directed Respect edge directions (directed graphs only).
• unconn false: +infinity when the start does not reach every vertex.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID vid_start is not below the number of vertices.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O(k (|V| + |E|)) for k sweeps (a log |V| factor with weights); k is usually small.

Checked

python-igraph 1.0 does not expose it. On 400 seeded graphs: the value equals the distance between from and to, never exceeds the diameter, equals the eccentricity of from (undirected) and stays in the start's component. Which vertex wins among equally far ones may differ from igraph's choice: NOT verified against igraph.

C name

og_pseudo_diameter

In notebooks

Og.PseudoDiameter

igraph 1.0

igraph_pseudo_diameter

See also

diameter, eccentricity

A path between two vertices whose narrowest edge is as wide as possible.

og_error_t og_get_widest_path(
    const og_t *graph,
    og_vector_int_t *vertices,
    og_vector_int_t *edges,
    og_int_t from,
    og_int_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

A path's width is the smallest weight among its edges. This finds a path from from to to of largest width (the bottleneck or maximum-capacity path, Pollack 1960) with Dijkstra's scheme, max-min taking the place of plus. The weights are the widths and are required; they may be negative, and an edge of width -infinity is never used. The search stops once to is finished.

vertices and edges (either may be NULL) receive the path; an unreachable target gives empty vectors and a warning.

Parameters

• graph The input graph.
• vertices Integer vector or NULL; receives the path's vertices from from to to.
• edges Integer vector or NULL; receives the path's edge ids in walking order.
• from The source vertex.
• to The target vertex.
• weights Edge widths, one per edge; required.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL weights is NULL, of the wrong length, or has a NaN.
• OG_ENOMEM Not enough memory.

Complexity

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

Checked

python-igraph 1.0 has no widest paths. On 240 seeded graphs with widths in [-4, 9] and +-infinity the path is a valid walk whose narrowest edge equals the widest width found independently. Which of several equally wide paths is returned is NOT verified against igraph.

C name

og_get_widest_path

In notebooks

Og.GetWidestPath

igraph 1.0

igraph_get_widest_path

See also

get_widest_paths, widest_path_widths_dijkstra

A widest path from a source to each target, with the tree of widest paths.

og_error_t og_get_widest_paths(
    const og_t *graph,
    og_vector_int_list_t *vertices,
    og_vector_int_list_t *edges,
    og_int_t from,
    og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode,
    og_vector_int_t *parents,
    og_vector_int_t *inbound_edges
);

The many-target form of get_widest_path: item i of vertices and edges receives a widest path to the i-th target of to (repeats allowed); an unreachable target gets empty lists and a warning. parents and inbound_edges describe the tree the search built, as in get_shortest_paths. The search stops once every target is finished.

Parameters

• graph The input graph.
• vertices Integer-vector list (may be NULL), resized to |to|; item i receives the vertices of the path to the i-th target, the source first.
• edges Integer-vector list (may be NULL), resized to |to|; item i receives the edge ids of the path to the i-th target.
• from The source vertex.
• to Vertex selector of the targets, in the order the paths are wanted; repeats allowed.
• weights Edge widths, one per edge; required.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• parents Integer vector or NULL. Resized to |V|: the previous vertex on each vertex's path, -1 for the source, -2 for a vertex not reached.
• inbound_edges Integer vector or NULL. Resized to |V|: the edge through which each vertex was reached, -1 for the source and for vertices not reached.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL weights is NULL, of the wrong length, or has a NaN.
• OG_ENOMEM Not enough memory.

Complexity

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

Checked

As get_widest_path, for every target from up to 4 sources; parents and inbound_edges checked to be consistent. Tie choice NOT verified against igraph.

C name

og_get_widest_paths

In notebooks

Og.GetWidestPaths

igraph 1.0

igraph_get_widest_paths

See also

get_widest_path, widest_path_widths_dijkstra

Widest-path widths from a set of sources to a set of targets.

og_error_t og_widest_path_widths_dijkstra(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t from,
    const og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

res becomes |from| x |to|: entry (i, j) is the largest width (narrowest edge) of any path from the i-th source to the j-th target, +infinity from a vertex to itself and -infinity when there is no path. Widths are required and may be negative; edges of width -infinity are not used. One Dijkstra-style search per source. A target listed twice is OG_EINVAL.

Parameters

• graph The input graph.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• weights Edge widths, one per edge; required.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL weights is NULL, of the wrong length, or has a NaN; or a target is listed twice.
• OG_ENOMEM Not enough memory.

Complexity

O(s (|V| + |E|) log |V|) for s sources.

Checked

No python-igraph counterpart: equal to an independent fixpoint computation of the definition on 240 seeded graphs, every mode, widths with negatives and +-infinity.

C name

og_widest_path_widths_dijkstra

In notebooks

Og.WidestPathWidthsDijkstra

igraph 1.0

igraph_widest_path_widths_dijkstra

See also

widest_path_widths_floyd_warshall, get_widest_paths

Widest-path widths between all pairs, by the bottleneck form of Floyd-Warshall.

og_error_t og_widest_path_widths_floyd_warshall(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t from,
    const og_vs_t to,
    const og_vector_t *weights,
    og_neimode_t mode
);

Same output as widest_path_widths_dijkstra, computed on a dense |V| x |V| table with the max-min form of the Floyd-Warshall recurrence; the requested rows and columns are copied out at the end. Self-loops and edges of width -infinity play no part. Suits dense graphs or cases where most pairs are wanted.

Parameters

• graph The input graph.
• res Initialised matrix; resized to |from| x |to| and filled.
• from Vertex selector of the sources; one row of the result per source, in selector order.
• to Vertex selector of the targets; one column per target, in selector order.
• weights Edge widths, one per edge; required.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL weights is NULL, of the wrong length, or has a NaN.
• OG_ENOMEM Not enough memory.

Complexity

O(|V|^3) time, O(|V|^2) memory.

Checked

Same 240 graphs and fixpoint as widest_path_widths_dijkstra.

C name

og_widest_path_widths_floyd_warshall

In notebooks

Og.WidestPathWidthsFloydWarshall

igraph 1.0

igraph_widest_path_widths_floyd_warshall

See also

widest_path_widths_dijkstra, distances_floyd_warshall

Mean inverse shortest-path length over all ordered pairs of distinct vertices.

og_error_t og_global_efficiency(
    const og_t *graph,
    const og_vector_t *weights,
    og_real_t *res,
    og_bool_t directed
);

Global efficiency (Latora and Marchiori, 2001): the average of 1/d(u, v) over the |V| (|V| - 1) ordered pairs of distinct vertices, where a pair without a path adds 0. Unlike the average path length it stays finite on disconnected graphs. Weights must be non-negative; directed false ignores edge directions. Fewer than two vertices give NaN.

It shares average_path_length's sweep, so the inverse distances are added in the same order.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• res Receives the efficiency, or NULL.
• directed Respect edge directions (directed graphs only).

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| (|V| + |E|)) unweighted; O(|V| (|V| + |E|) log |V|) weighted.

Checked

python-igraph 1.0 has no efficiency function: compared with values computed from its distances() on the path_stats graphs (0-300 vertices, no zero weights), directed and not. How the sum rounds with weights near 1e-12 is NOT verified against igraph.

Threads

One search per source on the thread layer; the distances are added into the running totals in the one-thread order (an ordered stream), so the bits do not depend on the thread count.

C name

og_global_efficiency

In notebooks

Og.GlobalEfficiency

igraph 1.0

igraph_global_efficiency

See also

local_efficiency, average_local_efficiency, average_path_length

For each chosen vertex, how well its neighbours reach one another when the vertex is taken out.

og_error_t og_local_efficiency(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    const og_vs_t vids,
    og_bool_t directed,
    og_neimode_t mode
);

Local efficiency of v (Latora and Marchiori 2001; Vragovic, Louis and Diaz-Guilera 2005): take v's distinct neighbours along mode (v itself left out), remove v, and average 1/d over the ordered pairs of distinct neighbours, where a pair without a path adds 0. Vertices with 0 or 1 neighbour score 0.

mode decides who counts as a neighbour; directed decides whether the paths between neighbours follow edge directions (directed graphs only). Weights must be non-negative.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• res Real vector; resized to |vids| and filled.
• vids Vertex selector of the vertices whose values are returned, in selector order.
• directed Follow edge directions on the paths between neighbours.
• mode Which neighbours count in a directed graph: OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_EINVVID A vertex id is out of range.
• OG_ENOMEM Not enough memory.

Complexity

For a vertex with k neighbours, k searches that stop once the other neighbours are finished: at most O(k (|V| + |E|)) per vertex, times log |V| with weights.

Checked

python-igraph 1.0 does not expose it: compared with the definition evaluated with python-igraph on 210 graphs of 0-300 vertices with loops and multi-edges, weighted and not, directed x every mode.

C name

og_local_efficiency

In notebooks

Og.LocalEfficiency

igraph 1.0

igraph_local_efficiency

See also

average_local_efficiency, global_efficiency

The mean local efficiency over all vertices.

og_error_t og_average_local_efficiency(
    const og_t *graph,
    const og_vector_t *weights,
    og_real_t *res,
    og_bool_t directed,
    og_neimode_t mode
);

The average of local_efficiency over every vertex, with the same directed, mode and weight rules. The null graph gives 0.

Parameters

• graph The input graph.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• res Receives the mean, or NULL.
• directed Follow edge directions on the paths between neighbours.
• mode Which neighbours count in a directed graph: OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
• OG_ENOMEM Not enough memory.

Complexity

The sum of local_efficiency's cost over all vertices.

Checked

The mean of the local efficiencies of the same fixture; null graph 0.

C name

og_average_local_efficiency

In notebooks

Og.AverageLocalEfficiency

igraph 1.0

igraph_average_local_efficiency

See also

local_efficiency, global_efficiency

How many vertices lie within a given number of steps of each chosen vertex.

og_error_t og_neighborhood_size(
    const og_t *graph,
    og_vector_int_t *res,
    og_vs_t vids,
    og_int_t order,
    og_neimode_t mode,
    og_int_t mindist
);

For each vertex v of vids, the number of vertices whose unweighted distance from v along mode is at least mindist and at most order; v itself counts when mindist is 0. A negative order means no limit.

Parameters

• graph The input graph.
• res Integer vector; resized to |vids| and filled.
• vids Vertex selector of the vertices whose values are returned, in selector order.
• order Largest number of steps; negative means no limit.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• mindist Smallest number of steps; 0 includes the vertex itself.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL mindist is negative, or larger than a non-negative order.
• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ENOMEM Not enough memory.

Complexity

One breadth-first search per vertex, limited to order steps: at most O(|V| + |E|) each.

Checked

Identical to python-igraph 1.0 neighborhood_size() on 220 graphs of 0-300 vertices, orders including no limit, mindist, every mode.

C name

og_neighborhood_size

In notebooks

Og.NeighborhoodSize

igraph 1.0

igraph_neighborhood_size

See also

neighborhood, neighborhood_graphs

The vertices within a given number of steps of each chosen vertex.

og_error_t og_neighborhood(
    const og_t *graph,
    og_vector_int_list_t *res,
    og_vs_t vids,
    og_int_t order,
    og_neimode_t mode,
    og_int_t mindist
);

For each vertex v of vids, item i of res lists the vertices whose unweighted distance from v along mode lies between mindist and order, in breadth-first order: v first (when mindist is 0), then its neighbours, and so on. A negative order means no limit.

Parameters

• graph The input graph.
• res List of integer vectors; resized to |vids|.
• vids Vertex selector of the vertices whose values are returned, in selector order.
• order Largest number of steps; negative means no limit.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• mindist Smallest number of steps; 0 includes the vertex itself.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL mindist is negative, or larger than a non-negative order.
• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ENOMEM Not enough memory.

Complexity

One breadth-first search per vertex, limited to order steps.

Checked

Identical to python-igraph 1.0 neighborhood(), lists in its breadth-first order, on the same 220 graphs.

C name

og_neighborhood

In notebooks

Og.Neighborhood

igraph 1.0

igraph_neighborhood

See also

neighborhood_size, neighborhood_graphs

The subgraph induced by each chosen vertex's neighbourhood.

og_error_t og_neighborhood_graphs(
    const og_t *graph,
    og_graph_list_t *res,
    og_vs_t vids,
    og_int_t order,
    og_neimode_t mode,
    og_int_t mindist
);

For each vertex of vids, the subgraph induced by its neighborhood set (same order, mode and mindist rules) is appended to res, which is cleared first and owns the graphs. Each graph keeps the original vertices in increasing id order and the edges in the input's edge-id order; directedness is kept, attributes are not copied.

Parameters

• graph The input graph.
• res List of graphs (og_graph_list_t); cleared, then one graph appended per vertex of vids.
• vids Vertex selector of the vertices whose values are returned, in selector order.
• order Largest number of steps; negative means no limit.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• mindist Smallest number of steps; 0 includes the vertex itself.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVAL mindist is negative, or larger than a non-negative order.
• OG_EINVVID A vertex id is out of range.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ENOMEM Not enough memory.

Complexity

Per vertex, the bounded search plus the edges of its neighbourhood (and a sort of them).

Checked

python-igraph 1.0 does not expose it: every graph checked to be the subgraph induced by the neighborhood set of the same fixture. The edge order inside each graph is NOT verified against igraph.

C name

og_neighborhood_graphs

In notebooks

Og.NeighborhoodGraphs

igraph 1.0

igraph_neighborhood_graphs

See also

neighborhood, neighborhood_size

Assigns each vertex to its nearest generator vertex (a graph Voronoi partition).

og_error_t og_voronoi(
    const og_t *graph,
    og_vector_int_t *membership,
    og_vector_t *distances,
    const og_vector_int_t *generators,
    const og_vector_t *weights,
    og_neimode_t mode,
    og_voronoi_tiebreaker_t tiebreaker
);

Each vertex goes to the generator closest to it, with distances measured from the generator along mode (Erwig, 2000). membership[v] is the position of that generator in generators (-1 when no generator reaches v) and distances[v] the distance (+infinity when unreached); either output may be NULL. Weights must be non-negative (NULL: length 1); edges of weight +infinity are not used. Weighted distances whose difference is below 1e-10 of their sum count as equal, as in igraph.

tiebreaker settles a vertex equally close to several generators: OG_VORONOI_FIRST takes the one listed first, OG_VORONOI_LAST the one listed last (both one search from all generators at once), OG_VORONOI_RANDOM one of them uniformly at random, independently for each vertex (one pruned search per generator, using Open Graph's random generator).

Parameters

• graph The input graph.
• membership Integer vector or NULL; resized to |V|: index into generators, or -1.
• distances Real vector or NULL; resized to |V|: distance to the assigned generator.
• generators The generator vertices.
• weights Non-negative edge weights, one per edge; NULL means length 1.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• tiebreaker OG_VORONOI_FIRST, OG_VORONOI_LAST or OG_VORONOI_RANDOM.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL Unknown tiebreaker, or the weights are of the wrong length, NaN or negative.
• OG_EINVVID A generator is not a vertex of the graph.
• OG_ENOMEM Not enough memory.

Complexity

FIRST and LAST: O((|V| + |E|) log |V|). RANDOM: about the same when ties are rare; up to about |S| |E| for |S| generators when many of them tie over a large region.

Checked

python-igraph 1.0 has no voronoi(): FIRST and LAST derived from its distances() on 220 graphs, every mode; checked against igraph itself through python-igraph's community_voronoi() on 300 graphs (every vertex with one nearest generator got igraph's generator). RANDOM checked statistically (uniform among tied generators, independent per vertex).

C name

og_voronoi

In notebooks

Og.Voronoi

igraph 1.0

igraph_voronoi

See also

distances, neighborhood

Converts a walk given as edge ids into the sequence of vertices it visits.

og_error_t og_vertex_path_from_edge_path(
    const og_t *graph,
    og_int_t start,
    const og_vector_int_t *edge_path,
    og_vector_int_t *vertex_path,
    og_neimode_t mode
);

Follows edge_path from start and writes the |edge_path| + 1 vertices visited into vertex_path. In a directed graph with OG_OUT each edge must leave the current vertex, with OG_IN enter it; OG_ALL, or an undirected graph, accepts either end.

A negative start is inferred from the first edge: its tail (OG_OUT) or head (OG_IN); undirected, the end the second edge does not touch, trying both ends when the second edge touches both (the same edge walked back, or a parallel edge). An empty walk needs a start and gives the one-vertex path.

Parameters

• graph The input graph.
• start First vertex of the walk; negative to infer it.
• edge_path The edge ids of the walk, in order.
• vertex_path Integer vector; receives the vertices visited.
• mode Walking direction for directed edges: OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVEID An edge id is out of range.
• OG_EINVVID start is not a vertex of the graph.
• OG_EINVAL An edge does not continue the walk, or the walk is empty and start is negative.
• OG_ENOMEM Not enough memory.

Complexity

O(|edge_path|).

Checked

Turns every edge path of the all-paths fixture back into python-igraph 1.0's vertex path; 3,000 random walks checked (given starts exact, inferred starts valid, broken walks OG_EINVAL).

C name

og_vertex_path_from_edge_path

In notebooks

Og.VertexPathFromEdgePath

igraph 1.0

igraph_vertex_path_from_edge_path

See also

get_shortest_path, get_k_shortest_paths

Unfolds a graph into a forest by a breadth-first walk from given roots, copying vertices that are reached more than once.

og_error_t og_unfold_tree(
    const og_t *graph,
    og_t *tree,
    og_neimode_t mode,
    const og_vector_int_t *roots,
    og_vector_int_t *vertex_index
);

A breadth-first search from each vertex of roots in turn (a root already reached is skipped) walks every edge it meets once, along mode, in the order incident() lists them. An edge to a vertex not seen yet becomes a tree edge; an edge to a vertex already seen gets a fresh copy of that vertex (ids |V|, |V| + 1, ... in the order made) as its far end. The result is a forest.

tree (uninitialised on entry) receives it: |V| plus the number of copies vertices, the same directedness, every walked edge keeping its orientation. vertex_index[i] (may be NULL) gives the original vertex of tree vertex i. Vertices the walk never reaches stay as isolated vertices; edges it never walks are left out.

Parameters

• graph The input graph.
• tree Uninitialised graph; receives the forest.
• mode Which way edges are followed in a directed graph: OG_OUT (from source to target), OG_IN (against the edge direction) or OG_ALL (either way). Ignored for undirected graphs.
• roots Start vertices, in the order they are used.
• vertex_index Integer vector or NULL; receives the original id of every vertex of the forest.

Returns

OG_SUCCESS, or the error code.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVVID A root is not a vertex of the graph.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

Vertex count, edge list and vertex_index identical to python-igraph 1.0 unfold_tree() on 220 graphs of 0-300 vertices, random roots, every mode.

C name

og_unfold_tree

In notebooks

Og.UnfoldTree

igraph 1.0

igraph_unfold_tree

See also

neighborhood