// the find
petgraph/petgraph
Graph data structure library for Rust.
petgraph is the standard graph data structure and algorithms library for Rust — adjacency lists, stable graphs, matrix graphs, and a solid set of algorithms covering shortest paths, MST, SCC, max flow, and more. It's what you reach for when you need graphs in Rust and don't want to roll your own. The trunk is currently mid-refactor into a multi-crate layout, so there's a gap between what's released (0.8) and what's in main.
The algorithm coverage is genuinely broad: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, A*, Kosaraju/Tarjan SCC, Dinic's max flow, graph isomorphism, page rank, and more — most with benchmarks in-tree so you can see what you're getting. Four distinct graph types (Graph, StableGraph, GraphMap, MatrixGraph) with different performance characteristics mean you can pick the right representation instead of forcing one abstraction everywhere. The visitor trait system is well-designed — algorithms are generic over graph types via trait bounds, so custom graph wrappers can plug into existing algorithms without forking. `no_std` support with the `std` feature gate is a real differentiator for embedded or WASM targets.
The trunk-vs-release split is a real problem right now: the README warns that main is mid-architecture transition, the 0.8 branch is the stable release, and it's not obvious when the new multi-crate layout will stabilize. If you pin to 0.8 today you're locked out of whatever improvements land in the restructure. The visit trait abstraction is powerful but notoriously hard to understand — the trait tower (IntoNeighbors, Visitable, NodeIndexable, etc.) creates a steep learning curve and error messages when you get it wrong are brutal. There's no built-in support for hypergraphs or multigraphs beyond edge weights, which matters for certain domains. Dynamic graph mutation (adding/removing nodes mid-algorithm) is awkward; StableGraph handles removal better than Graph but at a memory cost, and neither gives you a clean story for concurrent read/write.