petgraph · starovoid · Mar 21, 2025 · Mar 11, 2025 · Mar 11, 2025 · Mar 19, 2025
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
@@ -22,6 +22,8 @@ jobs:
       matrix:
         include:
           - rust: 1.64.0  # MSRV
+            required_features: std
+          - rust: 1.81.0  # no_std MSRV
           - rust: stable
             features: unstable quickcheck rayon
             test_all: --all
@@ -51,14 +53,14 @@ jobs:
           cargo update -p once_cell --precise 1.20.3
 
       - name: Build with no features
-        run: cargo build --verbose --no-default-features
+        run: cargo build --verbose --no-default-features --features "${{ matrix.required_features }}"
       - name: Test with no features
-        run: cargo test --verbose --no-default-features
+        run: cargo test --verbose --no-default-features --features "${{ matrix.required_features }}"
 
       - name: Build with features "${{ matrix.features }}"
-        run: cargo build --verbose --features "${{ matrix.features }}"
+        run: cargo build --verbose --features "${{ matrix.features }}" --features "${{ matrix.required_features }}"
       - name: Test with features "${{ matrix.features }}"
-        run: cargo test ${{ matrix.test_all }} --verbose --features "${{ matrix.features }}"
+        run: cargo test ${{ matrix.test_all }} --verbose --features "${{ matrix.features }}" --features "${{ matrix.required_features }}"
 
       - name: Build benchmarks
         if: ${{ matrix.bench }}
@@ -93,6 +95,21 @@ jobs:
         env:
           RUSTDOCFLAGS: "-Dwarnings"
 
+  check-no-std:
+    name: Check no_std
+    runs-on: ubuntu-latest
+    steps:
+      - uses: actions/checkout@v4
+      - uses: mozilla-actions/[email protected]
+      - name: Install stable toolchain
+        uses: dtolnay/rust-toolchain@stable
+        with:
+          components: rustfmt, clippy
+          targets: wasm32v1-none
+
+      - name: Check
+        run: cargo check --no-default-features -p petgraph --target wasm32v1-none --features graphmap,serde-1,stable_graph,matrix_graph,generate,unstable
+
   miri:
     name: Unsoundness check
     if: github.event_name != 'merge_group'

diff --git a/Cargo.toml b/Cargo.toml
@@ -42,10 +42,11 @@ debug = true
 
 [dependencies]
 fixedbitset = { version = "0.5.7", default-features = false }
-indexmap = "2.5.0"
+indexmap = { version = "2.5.0", default-features = false }
+hashbrown = { version = "^0.15.0" }
 quickcheck = { optional = true, version = "0.8", default-features = false }
-serde = { version = "1.0", optional = true }
-serde_derive = { version = "1.0", optional = true }
+serde = { version = "1.0", default-features = false, optional = true }
+serde_derive = { version = "1.0", default-features = false, optional = true }
 rayon = { version = "1.5.3", optional = true }
 
 [dev-dependencies]
@@ -58,7 +59,7 @@ ahash = "0.7.2"
 fxhash = "0.2.1"
 
 [features]
-rayon = ["dep:rayon", "indexmap/rayon"]
+rayon = ["std", "dep:rayon", "indexmap/rayon"]
 
 # feature flags for testing use only
 all = [
@@ -69,12 +70,19 @@ all = [
     "graphmap",
     "rayon",
 ]
-default = ["graphmap", "stable_graph", "matrix_graph"]
+default = ["std", "graphmap", "stable_graph", "matrix_graph"]
 
 generate = [] # For unstable features
 
 graphmap = []
 matrix_graph = []
 serde-1 = ["serde", "serde_derive"]
-stable_graph = []
+stable_graph = ["serde?/alloc"]
 unstable = ["generate"]
+
+std = ["indexmap/std"]
+
+[lints.clippy]
+alloc_instead_of_core = "warn"
+std_instead_of_alloc = "warn"
+std_instead_of_core = "warn"
diff --git a/benches/graphmap.rs b/benches/graphmap.rs
@@ -67,14 +67,17 @@ macro_rules! test_case_with_hasher {
     };
 }
 
-test_case_with_hasher!(graphmap_serial_bench, std::hash::RandomState);
+test_case_with_hasher!(
+    graphmap_serial_bench,
+    std::collections::hash_map::RandomState
+);
 test_case_with_hasher!(graphmap_serial_bench_fxhash, fxhash::FxBuildHasher);
 test_case_with_hasher!(graphmap_serial_bench_ahash, ahash::RandomState);
 
 #[bench]
 fn graphmap_parallel_bench(bench: &mut Bencher) {
     let data = test_nodes();
-    let gr = test_graph::<std::hash::RandomState>(&data);
+    let gr = test_graph::<std::collections::hash_map::RandomState>(&data);
     bench.iter(|| {
         let _sources: Vec<MyStruct> = gr
             .par_nodes()

diff --git a/benches/matrix_graph.rs b/benches/matrix_graph.rs
@@ -66,7 +66,7 @@ fn add_5_edges_for_each_of_100_nodes(b: &mut test::Bencher) {
 #[bench]
 fn add_edges_from_root(bench: &mut test::Bencher) {
     bench.iter(|| {
-        let mut gr = MatrixGraph::new();
+        let mut gr = MatrixGraph::<_, _>::new();
         let a = gr.add_node(());
 
         for _ in 0..100 {
@@ -79,7 +79,7 @@ fn add_edges_from_root(bench: &mut test::Bencher) {
 #[bench]
 fn add_adjacent_edges(bench: &mut test::Bencher) {
     bench.iter(|| {
-        let mut gr = MatrixGraph::new();
+        let mut gr = MatrixGraph::<_, _>::new();
         let mut prev = None;
         for _ in 0..100 {
             let b = gr.add_node(());
@@ -151,7 +151,7 @@ const BIGGER: &str = "
 ";
 
 /// Parse a text adjacency matrix format into a directed graph
-fn parse_matrix<Ty: EdgeType>(s: &str) -> MatrixGraph<(), (), Ty> {
+fn parse_matrix<Ty: EdgeType>(s: &str) -> MatrixGraph<(), (), std::hash::RandomState, Ty> {
     let mut gr = MatrixGraph::default();
     let s = s.trim();
     let lines = s.lines().filter(|l| !l.is_empty());

diff --git a/src/acyclic.rs b/src/acyclic.rs
@@ -1,9 +1,9 @@
 //! A wrapper around graph types that enforces an acyclicity invariant.
 
-use std::{
+use alloc::collections::{BTreeMap, BTreeSet};
+use core::{
     cell::RefCell,
     cmp::Ordering,
-    collections::{BTreeMap, BTreeSet},
     convert::TryFrom,
     ops::{Deref, RangeBounds},
 };
@@ -759,11 +759,14 @@ impl_graph_traits!(StableDiGraph);
 
 #[cfg(test)]
 mod tests {
+    use alloc::vec::Vec;
+
     use super::*;
     use crate::prelude::DiGraph;
+    use crate::visit::IntoNodeReferences;
+
     #[cfg(feature = "stable_graph")]
     use crate::prelude::StableDiGraph;
-    use crate::visit::IntoNodeReferences;
 
     #[test]
     fn test_acyclic_graph() {
@@ -841,7 +844,7 @@ mod tests {
             + IntoNodeReferences
             + IntoNeighborsDirected
             + GraphBase<NodeId = G::NodeId>,
-        G::NodeId: std::fmt::Debug,
+        G::NodeId: core::fmt::Debug,
     {
         let ordered_nodes: Vec<_> = acyclic.nodes_iter().collect();
         assert_eq!(ordered_nodes.len(), acyclic.node_count());

diff --git a/src/acyclic/order_map.rs b/src/acyclic/order_map.rs
@@ -3,7 +3,8 @@
 //!
 //! This data structure is an implementation detail and is not exposed in the
 //! public API.
-use std::{collections::BTreeMap, fmt, ops::RangeBounds};
+use alloc::{collections::BTreeMap, vec, vec::Vec};
+use core::{fmt, ops::RangeBounds};
 
 use crate::{
     algo::{toposort, Cycle},

diff --git a/src/adj.rs b/src/adj.rs
@@ -1,12 +1,14 @@
 //! Simple adjacency list.
+use alloc::{boxed::Box, vec::Vec};
+use core::{fmt, ops::Range};
+
+use fixedbitset::FixedBitSet;
+
 use crate::data::{Build, DataMap, DataMapMut};
 use crate::iter_format::NoPretty;
 use crate::visit::{
     self, EdgeCount, EdgeRef, GetAdjacencyMatrix, IntoEdgeReferences, IntoNeighbors, NodeCount,
 };
-use fixedbitset::FixedBitSet;
-use std::fmt;
-use std::ops::Range;
 
 #[doc(no_inline)]
 pub use crate::graph::{DefaultIx, IndexType};
@@ -34,7 +36,7 @@ impl (Iterator) for
 #[derive(Debug, Clone)]
 struct OutgoingEdgeIndices <Ix> where { Ix: IndexType }
 item: EdgeIndex<Ix>,
-iter: std::iter::Map<std::iter::Zip<Range<usize>, std::iter::Repeat<NodeIndex<Ix>>>, fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix>>,
+iter: core::iter::Map<core::iter::Zip<Range<usize>, core::iter::Repeat<NodeIndex<Ix>>>, fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix>>,
 }
 
 /// Weighted sucessor
@@ -48,15 +50,15 @@ struct WSuc<E, Ix: IndexType> {
 
 /// One row of the adjacency list.
 type Row<E, Ix> = Vec<WSuc<E, Ix>>;
-type RowIter<'a, E, Ix> = std::slice::Iter<'a, WSuc<E, Ix>>;
+type RowIter<'a, E, Ix> = core::slice::Iter<'a, WSuc<E, Ix>>;
 
 iterator_wrap! {
 impl (Iterator DoubleEndedIterator ExactSizeIterator) for
 /// An iterator over the indices of the neighbors of a node.
 #[derive(Debug, Clone)]
 struct Neighbors<'a, E, Ix> where { Ix: IndexType }
 item: NodeIndex<Ix>,
-iter: std::iter::Map<RowIter<'a, E, Ix>, fn(&WSuc<E, Ix>) -> NodeIndex<Ix>>,
+iter: core::iter::Map<RowIter<'a, E, Ix>, fn(&WSuc<E, Ix>) -> NodeIndex<Ix>>,
 }
 
 /// A reference to an edge of the graph.
@@ -95,7 +97,7 @@ impl<E, Ix: IndexType> visit::EdgeRef for EdgeReference<'_, E, Ix> {
 
 #[derive(Debug, Clone)]
 pub struct EdgeIndices<'a, E, Ix: IndexType> {
-    rows: std::iter::Enumerate<std::slice::Iter<'a, Row<E, Ix>>>,
+    rows: core::iter::Enumerate<core::slice::Iter<'a, Row<E, Ix>>>,
     row_index: usize,
     row_len: usize,
     cur: usize,
@@ -132,7 +134,7 @@ iterator_wrap! {
     #[derive(Debug, Clone)]
     struct NodeIndices <Ix> where {}
     item: Ix,
-    iter: std::iter::Map<Range<usize>, fn(usize) -> Ix>,
+    iter: core::iter::Map<Range<usize>, fn(usize) -> Ix>,
 }
 
 /// An adjacency list with labeled edges.
@@ -266,7 +268,7 @@ impl<E, Ix: IndexType> List<E, Ix> {
                 successor_index,
             };
         let iter = (0..(self.suc[a.index()].len()))
-            .zip(std::iter::repeat(a))
+            .zip(core::iter::repeat(a))
             .map(proj);
         OutgoingEdgeIndices { iter }
     }
@@ -380,7 +382,7 @@ where
         let mut edge_list = f.debug_list();
         let iter: Self = self.clone();
         for e in iter {
-            if std::mem::size_of::<E>() != 0 {
+            if core::mem::size_of::<E>() != 0 {
                 edge_list.entry(&(
                     NoPretty((e.source().index(), e.target().index())),
                     e.weight(),
@@ -475,8 +477,8 @@ impl<'a, E, Ix: IndexType> IntoNeighbors for &'a List<E, Ix> {
     }
 }
 
-type SomeIter<'a, E, Ix> = std::iter::Map<
-    std::iter::Zip<std::iter::Enumerate<RowIter<'a, E, Ix>>, std::iter::Repeat<Ix>>,
+type SomeIter<'a, E, Ix> = core::iter::Map<
+    core::iter::Zip<core::iter::Enumerate<RowIter<'a, E, Ix>>, core::iter::Repeat<Ix>>,
     fn(((usize, &'a WSuc<E, Ix>), Ix)) -> EdgeReference<'a, E, Ix>,
 >;
 
@@ -485,9 +487,9 @@ impl (Iterator) for
 /// An iterator over the [`EdgeReference`] of all the edges of the graph.
 struct EdgeReferences<'a, E, Ix> where { Ix: IndexType }
 item: EdgeReference<'a, E, Ix>,
-iter: std::iter::FlatMap<
-    std::iter::Enumerate<
-        std::slice::Iter<'a, Row<E, Ix>>
+iter: core::iter::FlatMap<
+    core::iter::Enumerate<
+        core::slice::Iter<'a, Row<E, Ix>>
     >,
     SomeIter<'a, E, Ix>,
     fn(
@@ -516,7 +518,7 @@ fn proj1<E, Ix: IndexType>(
 fn proj2<E, Ix: IndexType>((row_index, row): (usize, &Vec<WSuc<E, Ix>>)) -> SomeIter<E, Ix> {
     row.iter()
         .enumerate()
-        .zip(std::iter::repeat(Ix::new(row_index)))
+        .zip(core::iter::repeat(Ix::new(row_index)))
         .map(proj1 as _)
 }
 
@@ -544,7 +546,7 @@ impl<'a, Ix: IndexType, E> visit::IntoEdges for &'a List<E, Ix> {
         let iter = self.suc[a.index()]
             .iter()
             .enumerate()
-            .zip(std::iter::repeat(a))
+            .zip(core::iter::repeat(a))
             .map(proj1 as _);
         OutgoingEdgeReferences { iter }
     }

diff --git a/src/algo/articulation_points.rs b/src/algo/articulation_points.rs
@@ -1,9 +1,11 @@
+use alloc::{vec, vec::Vec};
+use core::{cmp::min, hash::Hash};
+
+use fixedbitset::FixedBitSet;
+use hashbrown::{HashMap, HashSet};
+
 use crate::visit;
 use crate::visit::{EdgeRef, IntoEdges, IntoNodeReferences, NodeIndexable, NodeRef};
-use fixedbitset::FixedBitSet;
-use std::cmp::min;
-use std::collections::{HashMap, HashSet};
-use std::hash::Hash;
 
 /// \[Generic\] Find articulation points in a graph using [Tarjan's algorithm](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm).
 ///

diff --git a/src/algo/astar.rs b/src/algo/astar.rs
@@ -1,13 +1,15 @@
-use std::collections::hash_map::Entry::{Occupied, Vacant};
-use std::collections::{BinaryHeap, HashMap};
+use alloc::{collections::BinaryHeap, vec, vec::Vec};
+use core::hash::Hash;
 
-use std::hash::Hash;
+use hashbrown::hash_map::{
+    Entry::{Occupied, Vacant},
+    HashMap,
+};
 
+use crate::algo::Measure;
 use crate::scored::MinScored;
 use crate::visit::{EdgeRef, GraphBase, IntoEdges, Visitable};
 
-use crate::algo::Measure;
-
 /// \[Generic\] A* shortest path algorithm.
 ///
 /// Computes the shortest path from `start` to `finish`, including the total path cost.

diff --git a/src/algo/bellman_ford.rs b/src/algo/bellman_ford.rs
@@ -1,5 +1,7 @@
 //! Bellman-Ford algorithms.
 
+use alloc::{vec, vec::Vec};
+
 use crate::prelude::*;
 
 use crate::visit::{IntoEdges, IntoNodeIdentifiers, NodeCount, NodeIndexable, VisitMap, Visitable};

diff --git a/src/algo/coloring.rs b/src/algo/coloring.rs
@@ -1,5 +1,7 @@
-use std::collections::{BinaryHeap, HashMap, HashSet};
-use std::hash::Hash;
+use alloc::{collections::BinaryHeap, vec};
+use core::hash::Hash;
+
+use hashbrown::{HashMap, HashSet};
 
 use crate::scored::MaxScored;
 use crate::visit::{IntoEdges, IntoNodeIdentifiers, NodeIndexable, VisitMap, Visitable};

diff --git a/src/algo/dijkstra.rs b/src/algo/dijkstra.rs
@@ -1,9 +1,14 @@
+use alloc::collections::BinaryHeap;
+use core::hash::Hash;
+
+use hashbrown::hash_map::{
+    Entry::{Occupied, Vacant},
+    HashMap,
+};
+
 use crate::algo::Measure;
 use crate::scored::MinScored;
 use crate::visit::{EdgeRef, IntoEdges, VisitMap, Visitable};
-use std::collections::hash_map::Entry::{Occupied, Vacant};
-use std::collections::{BinaryHeap, HashMap};
-use std::hash::Hash;
 
 /// \[Generic\] Dijkstra's shortest path algorithm.
 ///
@@ -23,7 +28,7 @@ use std::hash::Hash;
 /// use petgraph::Graph;
 /// use petgraph::algo::dijkstra;
 /// use petgraph::prelude::*;
-/// use std::collections::HashMap;
+/// use hashbrown::HashMap;
 ///
 /// let mut graph: Graph<(), (), Directed> = Graph::new();
 /// let a = graph.add_node(()); // node with no weight