petgraph

petgraph is a Rust library for representing and analyzing graphs. It ships several concrete graph types — Graph, StableGraph, GraphMap, MatrixGraph, and Csr — each trading off memory layout, index stability, and lookup speed differently, so you can pick the representation that matches your workload instead of building one from scratch.

On top of those types, petgraph includes a broad algorithms module covering shortest paths (Dijkstra, A*, Bellman-Ford), minimum spanning trees, strongly connected components, topological sort, max-flow, isomorphism checks, and more, plus DOT/Graphviz export for visualizing graphs. Both nodes and edges can carry arbitrary associated data, and graphs can be directed or undirected.

What You Get

• Five graph types (Graph, StableGraph, GraphMap, MatrixGraph, Csr) covering different index-stability and performance trade-offs
• A large algorithms module: Dijkstra, A*, Bellman-Ford, SPFA, Floyd-Warshall, min spanning tree, max flow (Ford-Fulkerson, Dinic’s), SCC, topological sort, isomorphism, k-shortest paths, PageRank, graph coloring, and more
• A composable visit module of traits (IntoNeighbors, Visitable, IntoEdgeReferences, etc.) so custom graph algorithms can be written generically over any graph type, including user-defined ones
• DOT/Graphviz export via the dot module, and optional DOT parsing via the dot_parser feature
• Optional Serde support (serde-1 feature), Rayon-powered parallel iterators for GraphMap (rayon feature), and no_std compatibility when the std feature is disabled

Common Use Cases

• Modeling dependency graphs (build systems, package resolvers, task schedulers) and running topological sort or cycle detection over them
• Shortest-path and routing computations, such as pathfinding over a road or logistics network with Dijkstra or A*
• Network/flow analysis — computing max flow, min-cut, or connectivity (SCC, articulation points, bridges) in infrastructure or social-graph modeling
• Exporting internal graph structures (compiler IR, state machines, data pipelines) to DOT for Graphviz visualization during debugging

Under The Hood

Architecture petgraph is organized as a Cargo workspace (crates/core plus the main crates/petgraph crate) built around a small set of interchangeable graph representations defined in src/graph_impl (Graph/StableGraph, adjacency-list based with u32-sized indices by default via the IndexType trait), src/graphmap.rs (hash-map-keyed graph for when node identity is data rather than an index), src/matrix_graph.rs (dense adjacency matrix), and src/csr.rs (compressed sparse row, index-only). All of these are unified by the visit module’s traits (GraphBase, IntoNeighbors, Visitable, IntoEdgeReferences, etc. in src/visit/mod.rs), which is what lets the ~25 algorithms in src/algo/ (dijkstra.rs, astar.rs, bellman_ford.rs, min_spanning_tree.rs, ford_fulkerson.rs, isomorphism.rs, page_rank.rs, and others) operate generically over any conforming graph, including user-defined ones, rather than being hard-coded to one internal type. Tech Stack Core dependencies are minimal and mostly optional: fixedbitset and hashbrown are required, while indexmap, serde/serde_derive (behind serde-1), rayon (behind rayon), and dot-parser/dot-parser-macros (behind dot_parser) are opt-in via Cargo features, keeping the default build lean and no_std-capable when the std feature is dropped. The crate targets Rust 1.91 (edition 2024) per rust-toolchain.toml, uses a workspace-level lint configuration enabling Clippy’s nursery/pedantic/all groups, and is developed with just as the task runner (justfile). Code Quality Testing is extensive and split between inline unit tests (13 files under src/ use #[test]) and a large tests/ directory with per-algorithm integration test files (graph.rs, graphmap.rs, dinics.rs, iso.rs, min_spanning_tree.rs, page_rank.rs, articulation_points.rs, and many more — roughly 20 files), plus a dedicated serialization-tests workspace member for the Serde feature and doctested examples embedded directly in lib.rs and module docs. Code is organized into focused single-responsibility modules rather than one monolithic file, with unsafe usage scoped narrowly to the IndexType trait (documented with a safety contract) rather than spread through the codebase. API Design The library favors a small number of composable traits over ad hoc per-type methods: algorithms accept &impl IntoNeighbors or similar bounds instead of a concrete Graph, so the same dijkstra() call works across Graph, StableGraph, and user types. Shorthand type aliases (DiGraph<N,E>, UnGraph<N,E>) reduce boilerplate for the common directed/undirected cases, and the crate-level docs in lib.rs walk through construction, indexing, algorithms, and DOT export with runnable examples, giving new users a working mental model without reading the source.