Module paths 

Path-related algorithms. Phase 1 entries: ALGO-SP-006 (unweighted single-source distances), ALGO-CC-040 (Eulerian path / cycle existence), ALGO-CC-041 (Eulerian path/cycle construction, undirected), ALGO-SP-020 (eccentricity / radius / diameter).

Structs

AllShortestPaths

Result of get_all_shortest_paths / get_all_shortest_paths_with_mode.

AllShortestPathsDijkstra

Result of get_all_shortest_paths_dijkstra.

DijkstraAllPaths

Output of dijkstra_all_shortest_paths.

DijkstraPaths

Output of dijkstra_paths. parents[v] is the predecessor of v along the shortest-path tree from the single source (or None for the source itself and for unreachable vertices — the caller can disambiguate via distances[v]). inbound_edges[v] is the edge id v was reached through; None for the source and unreachable vertices.

EulerianClassification

Whether an Eulerian path or cycle exists in a graph.

KShortestPath

Result of k_shortest_paths.

PathLengthHistResult

Result of path_length_hist.

PseudoDiameterResult

Result of the pseudo-diameter computation.

ShortestPath

A single shortest path: the vertex sequence (including from and to) and the edge sequence along it. For a path of k vertices the edge vector has k - 1 entries.

ShortestPathsDijkstra

Result of get_shortest_paths_dijkstra: vertex and edge paths from a single source to all vertices.

VoronoiPartition

Result of voronoi: the Voronoi cell each vertex belongs to plus the distance to its assigned generator.

Enums

AllShortestPathsMode

Direction mode for get_all_shortest_paths and get_all_shortest_paths_with_mode.

DijkstraMode

Direction selector for the mode-aware Dijkstra entry points (SP-001c). Counterpart of igraph_neimode_t restricted to the three values igraph_distances_dijkstra accepts. For undirected graphs every variant collapses to DijkstraMode::All (every edge is bidirectional).

DistancesCutoffMode

Direction mode for cutoff-aware unweighted distance functions.

DistancesFromMode

Direction mode for distances_from_with_mode.

DistancesMode

Direction mode for distances_all_with_mode.

ShortestPathMode

Direction mode for get_shortest_paths_with_mode.

SimplePathMode

Mode for traversing neighbors in directed graphs.

VoronoiTiebreaker

Tie-breaking rule used when two or more generators reach a vertex at the same distance.

WalkMode

Direction mode for edge-path traversal.

Functions

a_star_path

Single-source single-target shortest path using A*.

all_simple_paths

Enumerate all simple paths from from to vertices in to.

diameter

Diameter of graph — the maximum vertex eccentricity. None for a graph with no vertices.

diameter_weighted

OUT-mode default for diameter_weighted_with_mode.

diameter_weighted_with_mode

Mode-aware weighted diameter. None for vcount == 0.

dijkstra_all_shortest_paths

All shortest weighted paths from source to every vertex, preserving every tie. Counterpart of igraph_get_all_shortest_paths_dijkstra(_, _, _, _, source, vss_all(), weights, mode).

dijkstra_distances

Single-source Dijkstra distances.

dijkstra_distances_cutoff

Single-source Dijkstra distances with an optional cutoff. When cutoff = Some(c), vertices whose shortest-path distance exceeds c are returned as None (unreachable-within-cutoff); the search stops relaxing edges out of any vertex whose mindist > c.

dijkstra_distances_cutoff_with_mode

Mode-aware dijkstra_distances_cutoff. Counterpart of igraph_distances_dijkstra_cutoff(_, _, source, vss_all(), weights, mode, cutoff).

dijkstra_distances_multi

Multi-source Dijkstra distances. result[i][v] is the shortest distance from sources[i] to v (or None if unreachable / past the cutoff).

dijkstra_distances_multi_with_mode

Mode-aware dijkstra_distances_multi.

dijkstra_distances_with_mode

Mode-aware Dijkstra distances. Counterpart of igraph_distances_dijkstra(_, _, source, vss_all(), weights, mode).

dijkstra_path_to

Reconstruct a single source-to-target path returning vertex and edge sequences. Ok(None) if target is unreachable; the source vertex appears as the first element when reachable.

dijkstra_path_to_with_mode

Mode-aware dijkstra_path_to. Counterpart of igraph_get_shortest_path_dijkstra(_, _, _, source, target, weights, mode).

dijkstra_paths

Single-source Dijkstra returning distances + parents + inbound edges over every vertex.

dijkstra_paths_with_mode

Mode-aware dijkstra_paths. Counterpart of igraph_get_shortest_paths_dijkstra(_, _, _, source, vss_all(), weights, mode, parents, inbound_edges).

distances

Unweighted shortest-path lengths from source to every vertex.

distances_all

All-pairs unweighted shortest distances.

distances_all_with_mode

All-pairs shortest distances with direction control.

distances_cutoff

Unweighted shortest-path lengths from source to every vertex, ignoring paths longer than cutoff.

distances_cutoff_multi

Multi-source unweighted distances with cutoff, direction-aware.

distances_cutoff_with_mode

Mode-aware distances_cutoff. For undirected graphs mode is ignored.

distances_from

Compute shortest-path distances from multiple sources to all vertices.

distances_from_with_mode

Compute shortest-path distances from multiple sources with direction control.

eccentricity

Eccentricity of every vertex (length vcount). Result r[v] is the maximum shortest-path distance from v to any reachable vertex. Isolated vertices have eccentricity 0.

eccentricity_weighted

OUT-mode default for eccentricity_weighted_with_mode. Counterpart of igraph_eccentricity(_, weights, _, igraph_vss_all(), IGRAPH_OUT).

eccentricity_weighted_with_mode

Mode-aware weighted eccentricity. For each vertex v, returns max_{u reachable from v} dist(v, u), where distances are weighted shortest-path lengths (Dijkstra). Unreachable vertex pairs are ignored (matches upstream’s unconn=true); isolated vertices have eccentricity 0.0.

eulerian_cycle

Build an Eulerian cycle if one exists, or return an error.

eulerian_path

Build an Eulerian path or cycle for graph if one exists. Returns Some(edge_ids) (the walk visits each edge exactly once) or None if no Eulerian walk exists.

floyd_warshall_distances

All-pairs shortest distances via Floyd-Warshall.

get_all_shortest_paths

Find all shortest paths from source to every reachable vertex.

get_all_shortest_paths_dijkstra

Find all shortest paths from source to every reachable vertex using Dijkstra’s algorithm with non-negative edge weights.

get_all_shortest_paths_dijkstra_with_mode

Find all shortest paths from source with direction control.

get_all_shortest_paths_with_mode

Find all shortest paths from source with direction control.

get_shortest_path

Calculate a single shortest path from from to to.

get_shortest_path_astar

Calculate a single shortest path from from to to using A*.

get_shortest_paths

Returns one shortest path from source to every vertex in the graph.

get_shortest_paths_dijkstra

Returns one shortest path from source to every vertex in the graph, using weighted edges (Dijkstra’s algorithm).

get_shortest_paths_dijkstra_with_mode

Mode-aware get_shortest_paths_dijkstra.

get_shortest_paths_with_mode

Returns one shortest path from source to every vertex, with direction control for directed graphs.

graph_center

Return the central vertices of a graph — those with minimum eccentricity.

is_eulerian

Decide whether graph has an Eulerian path and/or cycle.

k_shortest_paths

Finds the k shortest loopless paths between source and target.

path_length_hist

Compute a histogram of all shortest-path lengths.

pseudo_diameter

Approximate the diameter of a graph using pseudo-peripheral vertex search.

radius

Radius of graph — the minimum vertex eccentricity. None for a graph with no vertices (matches upstream’s IGRAPH_NAN for the null graph).

radius_weighted

OUT-mode default for radius_weighted_with_mode.

radius_weighted_with_mode

Mode-aware weighted radius. None for vcount == 0.

random_walk

Random walk on graph starting at start, taking up to steps transitions.

random_walk_node2vec

Performs a second-order biased random walk (Node2Vec) starting at start for up to steps transitions.

random_walks

Generate multiple random walks from every vertex in the graph.

random_walks_from

Generate random walks from a specific set of starting vertices.

random_walks_node2vec

Generate multiple Node2Vec random walks from every vertex.

spanner

Compute a t-spanner of the graph.

vertex_path_from_edge_path

Convert an edge path to a vertex path.

voronoi

Voronoi partitioning of a graph from a set of generator vertices.

Type Aliases

AstarHeuristic

A heuristic estimating the distance from a candidate vertex (first argument) to the target vertex (second argument). Must be admissible (never overestimate the true remaining distance) for the result to be a true shortest path.

Node2VecWalkResult

Result of a Node2Vec random walk: the vertex chain and the edge chain.