# Objective

- Alternative to #238
- Alternative to #370
- Implements Item 6 from #551

## Solution

- Promoted `hashbrown` to a direct dependency (currently transient
through `indexmap`)
- Added a new `std` feature, and included it in all features which rely
on `std` for documentation purposes.
- Added new CI task to ensure `no_std` support works (using
`wasm32v1-none` as an example `no_std` target)
- Added several lints which help minimise `std` usage
- Adjusted certain public APIs to allow passing a `S: BuildHasher`
instead of implicitly relying on `std::hash::RandomState` when the `std`
feature is disabled

---

## Notes

I know this has been attempted several times before and delayed due to a
desire to refactor the crate _first_ before adding this functionality.
Delays in adding `no_std` support forced Bevy to drop `petgraph` from
its core crates, relying on a specialised alternative. We'd love to keep
using `petgraph`, but `no_std` support is now a requirement going
forward. This will also come up with `wgpu` which is _also_ pursuing
`no_std` support [here](gfx-rs/wgpu#6826).

---

BREAKING CHANGE:

Petgraph previously assumed the usage of `std::hash::RandomState` as the
hashing implementation across its codebase. In `no_std`, this is not
possible. To minimise friction for libraries supporting both `std` and
`no_std` with Petgraph, I have made the following changes to the public
API:

### `petgraph::algo::simple_paths::all_simple_paths`

This function now has a 3rd generic parameter `S` which controls the
hashing implementation used. Because `all_simple_paths` is a function it
cannot have default generic parameters, so users must specify the hasher
themselves.

```rust
// Before
let foo = all_simple_paths(/* ... */);

// After
let foo = all_simple_paths::<_, _, std::hash::RandomState>(/* ... */);
```

### Switched from `std::collections::{HashMap, HashSet}` to
`hashbrown::{HashMap, HashSet}`

To support `no_std`, we cannot use the standard library's
implementations of `HashMap` or `HashSet`. Methods and types previously
referencing those collections from `std` will now reference them from
`hashbrown`. Note that `hashbrown` was already a dependency of Petgraph,
so no change in audit requirements.

### Added Hashing Parameter

The following types have had a new generic parameter `S` added to
specify the hashing implementation. Note that when `std` is enabled,
these will all default to `std::hash::RandomState`, as before.

- `UnGraphMap`
- `DiGraphMap`
- `MatrixGraph`
- `DiMatrix`
- `UnMatrix`
- `NodeIdentifiers`
- `NodeReferences`

Note that for `MatrixGraph`, `DiMatrix`, `UnMatrix` the new `S`
parameter is in the 3rd position (all others have `S` in the last
position). The reason is `S` has a default parameter with `std` enabled,
but is required with `std` disabled. This means it must be the last
_required_ parameter.

```rust
// Before
let foo: MatrixGraph<Foo, Bar, Directed, Option<Bar>, DefaultIx>;

// After
let foo: MatrixGraph<Foo, Bar, std::hash::RandomState, Directed, Option<Bar>, DefaultIx>;
```

Also note that because `Default` can now be implemented for multiple
versions of the above types (generic over the hasher), you may need to
either specify the hasher, or explicitly declare it as default (with the
`std` feature enabled):

```rust
// Note that N and E are inferred by code below.
// Before
let foo = UnMatrix::default();

// After (Explicitly infer N and E, but use defaults otherwise)
let foo = UnMatrix::<_, _>::default();
```

### `default-features = false` MSRV is 1.81

If you don't enable the `std` feature, the MSRV increases to 1.81, when
`core::error::Error` was stabilised. To preserve the original MSRV of
1.64, just enable the `std` feature.