Skip to content

Conversation

@skius
Copy link
Contributor

@skius skius commented Apr 25, 2025

The newly added test fails with the old code, since initial state is always complete and hence the iterator's return value will always be Some(_).

I fixed this by making GraphMatcher the only entrypoint to isomorphisms, and moving that edge case logic into its Iterator implementation. This is a bit awkward, but I am unsure how to adapt isomorphisms itself, since it currently assumes having at least one mapped node pair before returning a result.

Benchmark comparisons for the changed code:

Details

Command: `cargo +nightly bench --bench iso`

Old:

test full_iso_bench            ... bench:         950.78 ns/iter (+/- 77.47)
test petersen_iso_bench        ... bench:         643.20 ns/iter (+/- 47.23)
test petersen_undir_iso_bench  ... bench:         508.70 ns/iter (+/- 29.86)
test praust_dir_no_iso_bench   ... bench:     590,866.19 ns/iter (+/- 23,428.15)
test praust_undir_no_iso_bench ... bench:     602,564.95 ns/iter (+/- 52,031.86)

New:

test full_iso_bench            ... bench:         934.26 ns/iter (+/- 52.24)
test petersen_iso_bench        ... bench:         622.69 ns/iter (+/- 24.05)
test petersen_undir_iso_bench  ... bench:         498.76 ns/iter (+/- 35.59)
test praust_dir_no_iso_bench   ... bench:     591,756.12 ns/iter (+/- 33,682.87)
test praust_undir_no_iso_bench ... bench:     620,409.33 ns/iter (+/- 27,801.96)

@starovoid starovoid added this to the 0.8.3 milestone May 20, 2025
@starovoid starovoid self-assigned this May 20, 2025
@starovoid starovoid self-requested a review May 20, 2025 11:40
@starovoid starovoid added the C-bugfix Category: PR with bug fix label May 20, 2025
@starovoid starovoid added this pull request to the merge queue Jul 5, 2025
Merged via the queue into petgraph:master with commit d33a613 Jul 5, 2025
11 checks passed
@github-actions github-actions bot mentioned this pull request Jun 29, 2025
RaoulLuque pushed a commit to RaoulLuque/petgraph that referenced this pull request Sep 21, 2025
…tgraph#780)

The newly added test fails with the old code, since initial state is
always complete and hence the iterator's return value will always be
`Some(_)`.

I fixed this by making `GraphMatcher` the only entrypoint to
`isomorphisms`, and moving that edge case logic into its `Iterator`
implementation. This is a bit awkward, but I am unsure how to adapt
`isomorphisms` itself, since it currently assumes having at least one
mapped node pair before returning a result.

Benchmark comparisons for the changed code:
<details><summary>Details</summary>
<p>
Command: `cargo +nightly bench --bench iso`

Old:
```
test full_iso_bench            ... bench:         950.78 ns/iter (+/- 77.47)
test petersen_iso_bench        ... bench:         643.20 ns/iter (+/- 47.23)
test petersen_undir_iso_bench  ... bench:         508.70 ns/iter (+/- 29.86)
test praust_dir_no_iso_bench   ... bench:     590,866.19 ns/iter (+/- 23,428.15)
test praust_undir_no_iso_bench ... bench:     602,564.95 ns/iter (+/- 52,031.86)
```

New:
```
test full_iso_bench            ... bench:         934.26 ns/iter (+/- 52.24)
test petersen_iso_bench        ... bench:         622.69 ns/iter (+/- 24.05)
test petersen_undir_iso_bench  ... bench:         498.76 ns/iter (+/- 35.59)
test praust_dir_no_iso_bench   ... bench:     591,756.12 ns/iter (+/- 33,682.87)
test praust_undir_no_iso_bench ... bench:     620,409.33 ns/iter (+/- 27,801.96)
```

</p>
</details>
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

C-bugfix Category: PR with bug fix

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants