Crate rust_igraph

Expand description

§rust-igraph

Pure-Rust port of the igraph network analysis library. Targets full API parity with igraph C v1.0.x (~850 public functions), validated continuously against the three official implementations (igraph C, python-igraph, R-igraph).

Status: alpha — only the Phase 0 walking-skeleton API is shipped (Graph, read_edgelist, bfs). The catalog grows algorithm-by-algorithm through Phase 1-10. See the project’s master plan.

§Quick start

use rust_igraph::{Graph, bfs};

let mut g = Graph::with_vertices(4);
g.add_edge(0, 1).unwrap();
g.add_edge(0, 2).unwrap();
g.add_edge(1, 3).unwrap();

let order = bfs(&g, 0).unwrap();
assert_eq!(order, vec![0, 1, 2, 3]);

§License

GPL-2.0-or-later, matching upstream igraph.

Re-exports§

pub use crate::core::error::IgraphError;
pub use crate::core::error::IgraphResult;
pub use crate::core::graph::Graph;
pub use crate::core::graph::VertexId;

Modules§

algorithms: Algorithm implementations for rust-igraph.
core: Core data structures for rust-igraph.

Structs§

BfsTree: Result of a multi-output BFS scan from a single root. Returned by bfs_tree.
BiconnectedComponents: Output of biconnected_components.
ConnectedComponents: Result of a weak connected-components scan.
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.
EdgelistPercolation: Outputs of edgelist_percolation. Same length as the input edge slice. giant_size[i] is the size of the largest component after edge i is added; vertex_count[i] is the number of distinct vertices touched by edges 0..=i.
EulerianClassification: Whether an Eulerian path or cycle exists in a graph.
SitePercolation: Outputs of site_percolation. Same length as vertex_order. giant_size[i] is the size of the largest connected component after vertex vertex_order[i] is activated; edge_count[i] is the cumulative number of edges added through step i (an edge is “added” the moment both its endpoints become active).
WidestPaths: Sidecar outputs from a single-source widest-paths run. Carries the widths vector plus the parent-pointer SPT (vertex-side and edge-side). Counterpart of the parents and inbound_edges outputs of igraph_get_widest_paths. Source itself has parents[source] == None and inbound_edges[source] == None; unreachable vertices also have both None. To disambiguate the source from unreachable targets, consult widths: source has Some(f64::INFINITY), unreachable has None.

Enums§

CorenessMode: Direction-handling for coreness_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).
EccMode: Mode for direction-aware eccentricity / radius / diameter on directed graphs. For undirected graphs every mode reduces to EccMode::All.
NeighborhoodMode: Direction mode for neighborhood_size_with_mode on directed graphs. Ignored on undirected graphs — every mode reduces to NeighborhoodMode::All.
ReciprocityMode: Reciprocity formula choice. Counterpart of upstream’s igraph_reciprocity_t (IGRAPH_RECIPROCITY_DEFAULT / IGRAPH_RECIPROCITY_RATIO).
SimpleMode: Direction-handling for is_simple_with_mode. Counterpart of upstream’s directed boolean parameter.

Functions§

a_star_path: Single-source single-target shortest path using A*.
articulation_points: Articulation points of graph (returns vertices in upstream’s DFS-discovery order).
assortativity_degree: Degree assortativity coefficient of graph (undirected, unweighted). Returns None for graphs with no edges or for regular graphs (all vertices same degree — the variance denominator vanishes, matching upstream’s IGRAPH_NAN).
assortativity_degree_directed: Directed degree assortativity coefficient (ALGO-PR-006c).
assortativity_degree_directed_weighted: Directed weighted degree assortativity (PR-006d).
assortativity_degree_weighted: Weighted degree assortativity coefficient.
average_local_efficiency: Average of local_efficiency over all N vertices. By upstream convention, returns 0.0 when vcount < 3 (no vertex can have two distinct neighbours, so every per-vertex value is trivially 0).
avg_nearest_neighbor_degree: Average nearest-neighbour degree, per vertex.
avg_nearest_neighbor_degree_weighted: Weighted average nearest-neighbour degree (Barrat formula).
bellman_ford_distances: Single-source Bellman-Ford shortest distances on graph from source, following out-edges on directed graphs.
bellman_ford_distances_with_mode: Single-source Bellman-Ford with directed-mode selection.
betweenness: Per-vertex (unweighted) betweenness centrality.
betweenness_weighted: Per-vertex weighted betweenness centrality.
bfs: Visit order of vertices reachable from root, in BFS order.
bfs_tree: Multi-output BFS from root. Returns visit order, per-vertex distances, and per-vertex BFS-tree parent in a single pass.
biconnected_components: Compute the biconnected components of graph.
bond_percolation: Bond percolation: the size of the largest component as edges of graph are added in the order specified by edge_order.
bridges: Bridges of graph — edges whose removal would increase the number of (weakly) connected components.
closeness: Per-vertex closeness centrality (Vec<Option<f64>>).
closeness_weighted: Per-vertex weighted closeness centrality.
complementer: Returns the complementer of graph.
connected_components: Compute the weak connected components of graph.
convergence_degree: Per-edge convergence degree.
convergence_degree_full: Convergence degree along with the per-edge In(e) / Out(e) counts.
coreness: Per-vertex coreness number.
coreness_with_mode: Coreness with explicit CorenessMode (ALGO-PR-015b).
count_adjacent_triangles: Per-vertex adjacent-triangle count. Entry i is the number of triangles vertex i participates in. Parallel edges and self-loops are ignored — the simple graph induced by the OUT-neighbour view is used (consistent with count_triangles). For directed graphs that is not yet the underlying-undirected projection that upstream uses; see ALGO-PR-002 for the deferred fix.
count_loops: Counts self-loop edges in graph.
count_multiple: Per-edge multiplicity: how many edges share each edge’s endpoint pair.
count_reachable: Per-vertex count of reachable vertices (including the vertex itself).
count_triangles: Count the number of triangles in graph. Edge directions, parallel edges, and self-loops are ignored.
decompose: Decompose graph into its weakly connected components.
density: Edge density of graph. Counterpart of igraph_density(_, NULL_weights, _, /*loops=*/false).
dfs: Pre-order visit of vertices reachable from root, in DFS order.
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.
diameter_with_mode: Diameter of graph under the given mode. None for vcount == 0.
difference: Returns orig \ sub: the multiset difference of the edges.
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).
disjoint_union: Returns the disjoint union of left and right.
disjoint_union_many: Disjoint union of any number of graphs (ALGO-OP-002b).
distances: Unweighted shortest-path lengths from source to every vertex.
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.
eccentricity_with_mode: Eccentricity of every vertex following mode-direction edges.
edge_betweenness: Per-edge unweighted betweenness centrality.
edge_betweenness_weighted: Per-edge weighted betweenness centrality (Vec<f64>).
edgelist_percolation: Percolation curve as a sequence of vertex-pair edges is added.
eigenvector_centrality: Eigenvector centrality scores normalized so max == 1.
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.
girth: Shortest cycle length in graph. Returns None for acyclic graphs.
global_efficiency: Global efficiency of graph — average inverse pairwise shortest distance over all N*(N-1) ordered vertex pairs. Pairs that are unreachable contribute 0.
harmonic_centrality: Per-vertex harmonic centrality.
harmonic_centrality_weighted: Per-vertex weighted harmonic centrality.
has_loop: Returns true iff graph has at least one self-loop edge.
has_multiple: Returns true iff graph has at least one parallel edge.
intersection: Returns the intersection of left and right.
is_acyclic: Returns true iff graph contains no cycle.
is_biconnected: Check whether graph is biconnected.
is_complete: Returns true iff every pair of distinct vertices is adjacent.
is_dag: Returns true iff graph is a directed acyclic graph.
is_eulerian: Decide whether graph has an Eulerian path and/or cycle.
is_forest: Returns Some(roots) iff graph is a forest under mode, otherwise None. The null graph is a forest with empty roots.
is_loop: Returns a per-edge boolean vector marking self-loops.
is_multiple: Returns a per-edge boolean vector marking multiple (parallel) edges.
is_same_graph: Returns true iff g1 and g2 are identical as labelled graphs: same vertex count, same directedness, same edge multiset. Edges differing only in storage order (or, for undirected, in endpoint orientation) are treated as identical.
is_simple: Returns true if graph has neither self-loops nor parallel edges.
is_simple_with_mode: is_simple with explicit SimpleMode (ALGO-PR-013b).
is_tree: Returns Some(root) iff graph is a tree under mode, otherwise None. The null graph (vcount == 0) is not a tree by convention.
johnson_distances: All-pairs shortest-path distances via Johnson’s algorithm.
knnk: Per-degree average nearest-neighbour degree, k_nn(k).
knnk_weighted: Per-degree weighted average nearest-neighbour degree.
local_efficiency: Per-vertex local efficiency. For each vertex v, computes the average inverse distance between every ordered pair of distinct vertices in N(v) (the unique non-self neighbours of v), measured in the subgraph obtained by removing v — paths must not pass through v. Pairs unreachable in G \ {v} contribute 0.
mean_distance: Mean unweighted shortest-path length over all reachable ordered pairs. Counterpart of igraph_average_path_length(_, NULL_weights, _, _, /*directed=*/true, /*unconn=*/true).
modularity: Modularity of graph with respect to community assignment membership.
modularity_directed: Directed modularity (Leicht-Newman, ALGO-CO-001b).
modularity_weighted: Weighted modularity (ALGO-CO-001c).
neighborhood: k-hop neighbourhood vertex list for every vertex (mode = All, mindist = 0).
neighborhood_size: k-hop neighbourhood size for every vertex (mode = All, mindist = 0).
neighborhood_size_with_mode: Full mode-aware k-hop neighbourhood size with mindist filter.
neighborhood_with_mode: Full mode-aware k-hop neighbourhood vertex list with mindist filter.
pagerank: PageRank scores via power iteration with damping 0.85.
pagerank_weighted: Weighted PageRank scores via power iteration with damping 0.85.
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.
radius_with_mode: Radius of graph under the given mode. None for vcount == 0.
random_walk: Random walk on graph starting at start, taking up to steps transitions.
reachability_matrix: Dense reachability matrix of graph. result[i][j] is true iff vertex j is reachable from i in zero or more steps.
read_edgelist: Read an edge list from any Read into a fresh Graph.
reciprocity: Reciprocity of graph. Returns None for graphs with no edges (matches upstream’s IGRAPH_NAN).
reciprocity_with_mode: Reciprocity with explicit mode + ignore_loops (ALGO-PR-004b).
simplify: Return a copy of graph with self-loops and/or parallel edges removed.
site_percolation: Site percolation: the size of the largest component as vertices (sites) of graph are activated in the order specified by vertex_order.
strongly_connected_components: Compute the strongly connected components of graph.
topological_sorting: Returns a topological ordering of graph’s vertices.
transitive_closure: Transitive closure of graph. The returned graph shares the same vertex count and direction as the input.
transitivity_barrat: Barrat’s weighted local transitivity, per vertex.
transitivity_local_undirected: Local transitivity (clustering coefficient) per vertex.
transitivity_undirected: Global transitivity (clustering coefficient) of graph — 3 * triangles / connected_triples. Returns None when there are no connected triples (matches upstream’s IGRAPH_TRANSITIVITY_NAN mode); use .unwrap_or(0.0) for the IGRAPH_TRANSITIVITY_ZERO behaviour.
union: Returns the union of left and right.
widest_path: Widest path from from to to: returns the vertex sequence and the edge sequence along the widest (maximum-bottleneck) path.
widest_path_widths: Single-source widest-path widths on graph from source, following out-edges on directed graphs.
widest_path_widths_floyd_warshall: All-pairs widest-path widths via the Floyd-Warshall recurrence.
widest_path_widths_floyd_warshall_with_mode: Mode-aware variant of widest_path_widths_floyd_warshall. Mode selects how directed edges contribute to the adjacency matrix:
widest_path_widths_with_mode: Widest-path widths with directed-mode selection. Mirrors widest_path_widths but lets you choose OUT/IN/ALL traversal for directed graphs (ignored on undirected).
widest_path_with_mode: Widest path with mode selection. Mirrors widest_path but lets you pick OUT/IN/ALL traversal on directed graphs.
widest_paths: Single-source widest-paths sidecar: widths plus the parent-pointer SPT. Convenient when you want all of widths, parent vertices, and inbound edge ids in one call without re-running the SPT.
widest_paths_to: Widest paths from a single source to multiple targets. Returns one WidestPathResult per element of targets, in the same order; None means the target is unreachable from from.
widest_paths_to_with_mode: Mode-aware variant of widest_paths_to.
widest_paths_with_mode: Mode-aware variant of widest_paths.

Type Aliases§

WidestPathResult: One entry of widest_paths_to’s output: Some((vertices, edges)) for a reachable target, None for unreachable. Each vertex chain begins with the source and ends with the target; each edge chain has length one less.

Crate rust_igraph

Crate rust_igraph Copy item path

§rust-igraph

§Quick start

§License

Re-exports§

Modules§

Structs§

Enums§

Functions§

Type Aliases§

Crate rust_igraph