Skip to content

Conversation

@Jhuni0123
Copy link
Contributor

@Jhuni0123 Jhuni0123 commented Sep 28, 2025

fixes #862

The stack-based implementation of SPFA produces false negatives when detecting negative cycles. When benchmarking without a negative cycle, it actually runs faster than Bellman-Ford.

Since the SPFA implementation uses a fixed-size(capacity) queue, no reallocation occurs in VecDeque, so it is expected to be sufficiently fast.

Before: 46082d6

test bellman_ford_bench        ... bench:       1,813.35 ns/iter (+/- 81.06)
test spfa_bench                ... bench:      21,197.04 ns/iter (+/- 1,145.72)

After: 10051b2

test bellman_ford_bench        ... bench:       1,826.56 ns/iter (+/- 155.06)
test spfa_bench                ... bench:       1,371.46 ns/iter (+/- 110.51)

@RaoulLuque
Copy link
Member

Looks great, thank you so much 👍 Would you mind rebasing and moving the test into tests/spfa.rs?

@RaoulLuque RaoulLuque added this pull request to the merge queue Sep 28, 2025
Merged via the queue into petgraph:master with commit 29f4c92 Sep 28, 2025
11 checks passed
@github-actions github-actions bot mentioned this pull request Sep 28, 2025
@starovoid
Copy link
Collaborator

Thanks for the PR! I forgot that the benchmark creates a negative cycle, that explains everything :)

github-merge-queue bot pushed a commit that referenced this pull request Sep 30, 2025
## 🤖 New release

* `petgraph`: 0.8.2 -> 0.8.3 (✓ API compatible changes)

<details><summary><i><b>Changelog</b></i></summary><p>

<blockquote>

##
[0.8.3](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.2...petgraph@v0.8.3)
- 2025-09-28

### Bug Fixes

- Infinite `subgraph_isomorphisms_iter` for empty isomorphisms
([#780](#780))
- Algos don't work on `UndirectedAdaptor`
([#870](#870))
([#871](#871))
- use a queue for SPFA
([#893](#893))
- `StableGraph::reverse` breaks free lists
([#890](#890))

### Documentation

- Fix examples link in README and unify typesetting of one word
([#823](#823))
- Add link to multigraph definition to isomorphism algos
([#824](#824))
- Fix auxiliary space (and time) complexity of bron-kerbosch
([#825](#825))
- Fix Typo in Operator Module Documentation
([#831](#831))
- Sync the crate feature flags in the README and docs
([#832](#832))
- Remove all \[Generic\] tags from algo docstrings
([#835](#835))
- Fix typos in comments
([#836](#836))
- Revamp CONTRIBUTING.md
([#833](#833))
- Update `GraphMap` link in README
([#857](#857))
- Add doc comment for `Dot::with_attr_getters`
([#850](#850))
- Specify iteration order for neighbors and edges and their variants
([#790](#790))
- Collection of Doc fixes
([#856](#856))

### New Features

- Add `into_nodes_edges_iters` to `StableGraph`
([#841](#841))
- Add methods to reserve & shrink `StableGraph` capacity
([#846](#846))
- Add Dinic's Maximum Flow Algorithm
([#739](#739))
- make Csr::from_sorted_edges generic over edge type and properly
increase edge_count in Csr::from_sorted_edges
([#861](#861))
- Add `map_owned` and `filter_map_owned` for `Graph` and `StableGraph`
([#863](#863))
- Add dijkstra::with_dynamic_goal
([#855](#855))
- Fix self-loop bug in all_simple_paths and enable multiple targets
([#865](#865))
- mark petgraph::dot::Dot::graph_fmt as public
([#866](#866))
- Add bidirectional Dijkstra algorithm
([#782](#782))

### Performance

- Make A* tie break on lower h-values
([#882](#882))

### Refactor

- add examples for scc algorithms and reorganize into dedicated module
([#830](#830))
- Remove unnecessary trait bounds from impls/methods
([#828](#828))
- replace uses of 'crate::util::zip' with 'core::iter::zip'
([#849](#849))
- Fix clippy (and other) lints
([#851](#851))
- Cleanup repo ([#854](#854))
- replace crate::util::enumerate with Iterator::enumerate
([#881](#881))

### Testing

- Add dependency list for 'quickcheck' feature
([#822](#822))
- Fix feature cfg capitalization in doctest
([#852](#852))
</blockquote>


</p></details>

---
This PR was generated with
[release-plz](https://github.com/release-plz/release-plz/).

---------

Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
Co-authored-by: Egor Starovoitov <52821033+starovoid@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Flaky Quickcheck 'test_spfa_undir'

3 participants