English | 中文

rust-igraph

Pure-Rust, high-performance graph and network analysis library. A faithful port of igraph with 1,297 public APIs, zero unsafe, and no C/C++ FFI.

Built for researchers, data scientists, and systems engineers who need production-grade graph algorithms without leaving the Rust ecosystem.

Why rust-igraph?

	rust-igraph	petgraph	igraph (C/Python)
Algorithm coverage	1,297 APIs (BFS, DFS, shortest paths, community detection, centrality, isomorphism, flows, layouts, graph generators, 60+ graph class recognizers...)	~50 (composable)	~850 APIs (reference)
Safety	Zero unsafe, zero unwrap in library code	Minimal unsafe	C core + bindings
Correctness	Cross-validated against igraph C, python-igraph, and R-igraph test suites	Independent	Reference implementation
Dependencies	Minimal (1 runtime dep: thiserror)	Minimal	Large C/C++ toolchain
WASM	Designed for wasm32-unknown-unknown	Yes	No

Features

• Traversal: BFS, DFS, topological sort, random walks
• Shortest paths: Dijkstra, Bellman-Ford, A*, all-pairs, widest paths
• Centrality: betweenness, closeness, eigenvector, PageRank, HITS, Katz, harmonic, constraint
• Community detection: Louvain, Leiden, Infomap, Spinglass, label propagation, Walktrap, edge betweenness, fast greedy, leading eigenvector, fluid communities, Voronoi
• Connectivity: connected/biconnected components, articulation points, bridges, separators, cohesive blocks, SCC
• Network flow: max-flow (push-relabel), min-cut, Gomory-Hu tree, edge/vertex connectivity, disjoint paths
• Isomorphism: VF2 (graph/subgraph), LAD subgraph, BLISS canonical labeling, automorphism groups
• Graph generators: Erdos-Renyi, Barabasi-Albert, Watts-Strogatz, SBM, forest fire, geometric random, degree sequence, lattices, famous graphs, and 30+ more
• Graph properties: 60+ structural recognizers (is_bipartite, is_chordal, is_planar, is_perfect, is_cograph, is_series_parallel, ...)
• Eigenvalue solvers: Lanczos (symmetric), Arnoldi (general), graph adjacency
• Layout: Fruchterman-Reingold, Kamada-Kawai, DrL, Sugiyama, GEM, Davidson-Harel, GraphOpt, MDS, LGL, UMAP, Reingold-Tilford, circle, star, grid, bipartite (16 engines, 2D+3D)
• Spatial: Delaunay triangulation, Gabriel graph, beta-skeleton, nearest-neighbor graph
• I/O: GML, GraphML, Pajek, DOT/Graphviz, LEDA, UCINET DL, DIMACS, edge list, NCOL, LGL, GraphDB (15 read/write functions)

Quick start

Add to your Cargo.toml:

[dependencies]
rust-igraph = "0.7"

use rust_igraph::{Graph, bfs};

fn main() {
    // Build a small social network
    let mut g = Graph::with_vertices(6);
    g.add_edge(0, 1).unwrap(); // Alice - Bob
    g.add_edge(0, 2).unwrap(); // Alice - Carol
    g.add_edge(1, 3).unwrap(); // Bob - Dave
    g.add_edge(2, 4).unwrap(); // Carol - Eve
    g.add_edge(3, 5).unwrap(); // Dave - Frank

    // BFS from Alice
    let order = bfs(&g, 0).unwrap();
    println!("Visit order: {:?}", order);
}

Graph construction

use rust_igraph::{Graph, GraphBuilder};

// Fluent builder pattern
let g = GraphBuilder::undirected()
    .vertices(5)
    .edges(&[(0,1), (1,2), (2,3), (3,4)])
    .cycle(&[0, 1, 2, 3, 4])
    .build()
    .unwrap();

// From an edge list (auto-infers vertex count)
let g = Graph::from_edges(&[(0,1), (1,2), (2,0)], false, None).unwrap();

// From a slice via TryFrom
let g = Graph::try_from(vec![(0u32, 1), (1, 2), (2, 0)].as_slice()).unwrap();

// From a string (great for tests)
let g = Graph::from_edge_list_str("0 1\n1 2\n2 0").unwrap();

// Classic generators
let k5 = rust_igraph::full_graph(5, false, false).unwrap();
let ring = rust_igraph::cycle_graph(10, false, false).unwrap();

Graph algebra (operator overloading)

use rust_igraph::Graph;

let a = Graph::from_edges(&[(0,1), (1,2)], false, None).unwrap();
let b = Graph::from_edges(&[(1,2), (2,0)], false, None).unwrap();

let union = &a | &b;          // edges in either graph
let intersection = &a & &b;   // edges in both graphs
let difference = &a - &b;     // edges in a but not b
let complement = !&a;          // all missing edges
let disjoint = &a + &b;       // concatenated (6 vertices)

Community detection

use rust_igraph::{Graph, louvain};

let mut g = Graph::with_vertices(10);
// ... add edges forming two clusters ...
let result = louvain(&g).unwrap();
println!("Communities: {:?}", result.membership);
println!("Modularity: {:.4}", result.modularity);

Centrality analysis

use rust_igraph::{Graph, pagerank, betweenness, katz_centrality};

let g = Graph::from_edges(
    &[(0,1), (1,2), (2,3), (3,4)], false, None
).unwrap();

let pr = pagerank(&g).unwrap();
let bc = betweenness(&g).unwrap();
let katz = katz_centrality(&g, 0.1, 1.0, None, None).unwrap();
println!("PageRank: {:?}", pr);
println!("Betweenness: {:?}", bc);
println!("Katz: {:?}", katz);

Method-style API

The most common operations are available directly on Graph:

use rust_igraph::Graph;

let g = Graph::from_edges(
    &[(0,1), (1,2), (2,0), (2,3), (3,4), (4,5), (5,3)],
    false, None
).unwrap();

// Structural queries
assert!(g.is_connected().unwrap());
println!("Diameter: {:?}", g.diameter().unwrap());
println!("Girth: {:?}", g.girth().unwrap());
println!("Triangles: {}", g.count_triangles().unwrap());

// Centrality
let pr = g.pagerank().unwrap();
let bc = g.betweenness().unwrap();
let hc = g.harmonic_centrality().unwrap();

// Community detection
let communities = g.louvain().unwrap();
println!("Modularity: {:.4}", communities.modularity);

// Graph construction
let er = Graph::erdos_renyi(1000, 0.01, 42).unwrap();
let ws = Graph::watts_strogatz(1000, 6, 0.1, 42).unwrap();
let ba = Graph::barabasi_albert(1000, 3, 42).unwrap();

Performance

All algorithms are implemented in idiomatic Rust with careful attention to cache locality and allocation patterns. Benchmarks (via criterion) are included for every major algorithm:

cargo bench --bench bench_louvain     # community detection
cargo bench --bench bench_bfs         # traversal
cargo bench --bench bench_max_flow    # network flow
cargo bench --bench bench_vf2         # isomorphism

Project status

v0.7.0 — 315 algorithm work units complete, 1,297 public functions, 1,100 tests, 1,850 conformance fixtures. API stabilizing toward v1.0.0.

Category	Status
Core data structures	Stable
Traversal (BFS, DFS)	Stable
Shortest paths	Stable
Centrality	Stable
Community detection	Stable
Connectivity	Stable
Network flow	Stable
Isomorphism	Stable
Graph generators	Stable
Layout algorithms	Stable (16 engines)
I/O formats	Stable (15 functions)
Spatial algorithms	Stable

Releases

This repository produces two independent release artifacts:

Package	Registry	Tag pattern	Trigger
rust-igraph	crates.io	v* (e.g. v0.6.0)	Rust library release
@graphrs/igraph-wasm	npm	wasm-v* (e.g. wasm-v0.1.4)	WASM binary release

They follow independent version schedules. WASM builds are published via npm Trusted Publishing (OIDC) — zero static tokens, cryptographically signed provenance.

Documentation

• Tutorial & Guide — mdBook with getting started, cookbook, and architecture overview
• API Reference — full rustdoc for all 1,297 public items
• docs.rs — auto-published on every crates.io release

Development

cargo build                          # build
cargo test                           # fast test suite (8,494 tests)
cargo test --all-features            # full suite with oracle + proptests
cargo clippy -- -D warnings          # lint
cargo doc --no-deps --open           # browse API docs locally

Each algorithm follows a 9-step AWU (Algorithm Work Unit) process tracked in .codefuse/tracking/ALGORITHMS.md. The engineering plan is in docs/plans/MASTER_PLAN.md.

Contributing

Contributions are welcome! See CONTRIBUTING.md for guidelines.

Whether you want to fix a bug, add an algorithm, improve docs, or optimize performance — we'd love your help. Open an issue to discuss larger changes before starting.

License

GPL-2.0-or-later. Same as upstream igraph C, which permits direct reference-translation of the C source. See LICENSE.

Acknowledgements

• igraph by the igraph team (C core)
• python-igraph and rigraph (reference test suites)